text:
# Effectiveness of preference elicitation in combinatorial auctions

## 1 Introduction

Combinatorial auctions, where agents can submit bids on bundles of items, are economically efficient mechanisms for selling $`k`$ items to $`n`$ bidders, and are attractive when the bidders’ valuations on bundles exhibit complementarity (a bundle of items is worth more than the sum of its parts) and/or substitutability (a bundle is worth less than the sum of its parts). Determining the winners in such auctions is a complex optimization problem that has recently received considerable attention (e.g., ).

An equally important problem, which has received much less attention, is that of bidding. There are $`2^k1`$ bundles, and each agent may need to bid on all of them to fully express its preferences. This can be undesirable for any of several reasons: determining one’s valuation for any given bundle can be computationally intractable ; there is a huge number of bundles to evaluate; communicating the bids can incur prohibitive overhead (e.g., network traffic); and agents may prefer not to reveal all of their valuation information due to reasons of privacy or long-term competitiveness . Appropriate bidding languages  can solve the communication overhead in some cases (when the bidder’s utility function is compressible). However, they still require the agents to completely determine and transmit their valuation functions and as such do not solve all the issues. So in practice, when the number of items for sale is even moderate, the bidders will not bid on all bundles. Instead, they may wastefully bid on bundles which they will not win, and they may suffer reduced economic efficiency by failing to bid on bundles they would have won.

Selective incremental preference elicitation by the auctioneer was recently proposed to address these problems , but the idea was not evaluated. We implemented the most promising elicitation schemes from that paper, starting from a rigid search-based scheme and continuing to a general flexible elicitation framework. We evaluated the previous schemes, and also developed a host of new elicitation policies. Our experiments show that elicitation reduces revelation drastically, and that this benefit increases with problem size. We also provide theoretical results on elicitation policies. Finally, we introduce and evaluate a new query type that takes the incremental nature of elicitation to a new level by allowing agents to give approximate answers that are refined only on an as-needed basis.

## 2 Auction and elicitation setting

We model the auction as having a single auctioneer selling a set $`K`$ of items to $`n`$ bidder agents (let $`k=|K|`$). Each agent $`i`$ has a valuation function $`v_i:2^K`$ that determines a finite private value $`v_i(b)`$ for each bundle $`bK`$. We make the usual assumption that the agents have free disposal, that is, adding items to an agent’s bundle never makes the agent worse off because, at worst, the agent can dispose of extra items for free. Formally, $`bK,b^{}b`$, $`v_i(b)v_i(b^{})`$. The techniques of the paper could also be used without free disposal, although more elicitation would be required due to less a priori structure.

At the start of the auction, the auctioneer knows the items and the agents, but has no information about the agents’ value functions over the bundles—except that the agents have free disposal. The auction proceeds by having the auctioneer incrementally *elicit* value function information from the agents one query at a time until the auctioneer has enough information to determine an optimal allocation of items to agents. Therefore, we also call the auctioneer the *elicitor*. An allocation is optimal if it maximizes social welfare $`_{i=1}^nv_i(b_i)`$, where $`b_i`$ is the bundle that agent $`i`$ receives in the allocation.111 Social welfare can only be maximized meaningfully if bidders’ valuations can be compared to each other. We make the usual assumption that the valuations are measured in money (dollars) and thus can be directly compared.  The goal of the elicitor is to determine an optimal allocation with as little elicitation as possible. A recent theoretical result shows that even with free disposal, in the worst case, finding an (even only approximately) optimal allocation requires exponential communication . Therefore, we will judge the techniques successful if they reduce communication from full revelation by an asymptotic amount.

## 3 Elicitor’s inference and constraint network

The elicitor, as we designed it, never asks a query whose answer could be inferred from the answers to previous queries. To support the storing and propagation of information received from the agents, we have the elicitor store its information in a constraint network.222This was included in the *augmented order graph* of Conen & Sandholm . Specifically, the elicitor stores a graph for each agent. In each graph, there is one node for each bundle $`b`$. Each node is labeled by an interval $`[\text{LB}_i(b),\text{UB}_i(b)]`$. The lower bound $`\text{LB}_i(b)`$ is the highest lower bound the elicitor can prove on the true $`v_i(b)`$ given the answers received to queries so far. Analogously, $`\text{UB}_i(b)`$ is the lowest upper bound. We say a bound is tight when it is equal to the true value.

Each graph can also have directed edges. A directed edge $`(a,b)`$ encodes the knowledge that the agent prefers bundle $`a`$ over bundle $`b`$ (that is, $`v_i(a)v_i(b)`$). The elicitor may know this even without knowing $`v_i(a)`$ or $`v_i(b)`$. An edge $`(a,b)`$ lets the elicitor infer that $`\text{LB}_i(a)\text{LB}_i(b)`$, which allows it to tighten the lower bound on $`a`$ and on any of $`a`$’s ancestors in the graph. Similarly, the elicitor can infer $`\text{UB}_i(a)\text{UB}_i(b)`$, which allows it to tighten the upper bound on $`b`$ and its descendants in the graph.

We define the relation $`ab`$ (read “$`a`$ dominates $`b`$”) to be true if we can prove that $`v_i(a)v_i(b)`$. This is the case either if $`\text{LB}_i(a)\text{UB}_i(b)`$, or if there is a directed path from $`a`$ to $`b`$ in the graph. The free disposal assumption allows the elicitor to infer the following dominance relations before the elicitation begins: $`bK,b^{}b`$, $`bb^{}`$.

Because the $``$ relation is transitive, to encode the free disposal constraints, we only need to add edges from each bundle $`a`$ to the bundles $`b`$ that include all but one item in $`a`$. This allows us to encode all the free disposal information in $`k2^{k1}`$ edges per agent333There are $`\left(\genfrac{}{}{0pt}{}{k}{i}\right)`$ bundles with $`i`$ items. A bundle with $`i`$ items has $`i`$ outgoing edges (one for each item we leave out). Therefore, we have $`_{i=1}^ki\left(\genfrac{}{}{0pt}{}{k}{i}\right)=k2^{k1}`$ edges. rather than having to include in each graph one edge for each of the $`\frac{1}{2}(3^k1)`$ dominance relations.444Bundles with $`i`$ items have $`2^{i1}`$ children (every combination of $`i`$ items). So, there are $`_{i=1}^k2^{i1}\left(\genfrac{}{}{0pt}{}{k}{i}\right)=\frac{1}{2}(3^k1)`$ dominance relations.

## 4 Rank lattice based elicitation

The elicitor can make use of non-cardinal rank information. Let $`b_i(r_i)`$, $`1r_i2^k`$, be the bundle that agent $`i`$ has at rank $`r_i`$. In other words, $`b_i(1)`$ is the agent’s most preferred bundle, $`b_i(2)`$ is its second most preferred bundle, and so on until $`b_i(2^k)`$, which is the empty bundle.

For example, consider two agents 1 and 2 bidding on two items $`A`$ and $`B`$, and the following value functions:
$`v_1(AB)=8`$, $`v_1(A)=4`$, $`v_1(B)=3`$, $`v_1(\mathrm{})=0`$  $`v_2(AB)=9`$, $`v_2(A)=1`$, $`v_2(B)=6`$, $`v_2(\mathrm{})=0`$
So, agent 1 ranks $`AB`$ first, $`A`$ second, $`B`$ third, and the empty bundle last. Agent 2 ranks $`AB`$ first, $`B`$ second, $`A`$ third, and the empty bundle last.

The elicitor uses a *rank vector* $`r=r_1,r_2,\mathrm{},r_n`$ to represent allocating $`b_i(r_i)`$ to each agent $`i`$. Not all rank vectors are feasible: the $`b_i(r_i)`$’s might overlap in items, which would correspond to giving the same item to multiple agents. For instance in the example above, rank vector $`1,2`$ corresponds to allocating $`AB`$ to agent 1 and $`B`$ to agent 2, which is infeasible. Similarly, rank vector $`2,2`$ allocates $`A`$ to agent 1 and $`B`$ to agent 2, which is a feasible allocation. The value of a rank vector $`r`$ is $`v(b(r))=_iv_i(b_i(r_i))`$. Rank vector $`1,2`$ in our example has value $`8+6=14`$, while $`2,2`$ has value $`4+6=10`$.

The elicitor can put bounds on $`v_i(b_i(r_i))`$ using the constraint network as before. Even without knowing $`b_i(r_i)`$ (which bundle it is that agent $`i`$ values $`r_i`$th), it knows that $`v_i(b_i(r_i1))v_i(b_i(r_i))v_i(b_i(r_i+1))`$. Thus an upper bound on $`v_i(b_i(r_i1))`$ is an upper bound on $`v_i(b_i(r_i))`$, and a lower bound on $`v_i(b_i(r_i+1))`$ is a lower bound on $`v_i(b_i(r_i))`$. In our example, knowing only $`b_1(1)=AB`$ and $`v_1(AB)=8`$, the elicitor can infer $`v_1(b_1(2))8`$.

The set of all rank vectors defines a *rank lattice* (Figure 1). A key observation in the lattice is that the descendants of a node have lower (or equal) value to the node.

Given the rank lattice, we can employ search algorithms to find an optimal allocation. In particular, by starting from the root and searching in best-first order (always expanding the fringe node of highest value), we are guaranteed that the first feasible node that is reached is optimal.

| FindOptimal$`()`$ | |
| --- | --- |
| 1 | $`\text{FRINGE}\{1,1,\mathrm{},1\}`$ |
| 2 | $`\text{while }\text{FRINGE}\mathrm{}`$ |
| 3 | $`r=\text{FindBestNode}(\text{FRINGE})`$ |
| 4 | $`\text{FRINGE}\text{FRINGE}\{r\}`$ |
| 5 | if $`r`$ is feasible |
| 6 | $`\text{return }r`$ |
| 7 | $`\text{for }\text{each }r^{}\text{children}(r)`$ |
| 8 | $`\text{if }r^{}\text{FRINGE}`$ |
| 9 | $`\text{FRINGE}\text{FRINGE}\{r^{}\}`$ |

Unlike in typical best-first search, algorithm FindOptimal does not necessarily know which node of the fringe has highest value and thus should be expanded next. Determining this often requires more elicitation. We implemented the following algorithm for doing this. It corresponds to an elicitation policy where as long as we cannot prove which node on the fringe is the best, we pick an arbitrary node and elicit just enough information to determine its value.

| FindBestNode$`(\text{FRINGE})`$ | |
| --- | --- |
| 1 | $`S\text{FRINGE}`$ |
| 2 | remove from $`S`$ all $`r`$ dominated by some $`r^{}`$ in $`S`$ |
| 3 | if all $`rS`$ have the same value |
| 4 | $`\text{return }\text{arbitrary}rS`$ |
| 5 | choose $`rS`$ whose value we don’t know exactly |
| 6 | $`\text{for }\text{each }\text{agent }i`$ |
| 7 | if elicitor does not know $`b_i(r_i)`$ |
| 8 | ask agent $`i`$ what bundle it ranks $`r_i`$th |
| 9 | if elicitor does not know $`v_i(b_i(r_i))`$ exactly |
| 10 | ask agent $`i`$ for its valuation on bundle $`b_i(r_i)`$ |
| 11 | $`\text{goto }2`$ |

In some cases, FindBestNode can return a rank vector $`r`$ although not all bundles $`b_i(r_i)`$ are known to the elicitor. This can occur, for example, if the known valuations in the rank vector already sum up to a large enough number. In that case, checking the feasibility in step 5 of FindOptimal requires eliciting the unknown bundles $`b_i(r_i)`$.

## 5 Experimental setup

While the idea and some algorithms for preference elicitation in combinatorial auctions have been presented previously , they have not been validated. To evaluate the usefulness of the idea, we conducted a host of experiments. We present the results in the rest of the paper. Each plot shows how many queries were needed to find an optimal allocation and prove that it is optimal (that no other allocation is better). In each plot, each point represents an average over 10 runs, where each run is on a different problem instance (different draw of valuations for the agents). Each algorithm was tested on the same set of problem instances.

Because the evaluation is based on the amount of information asked rather than real-time, we did not optimize our algorithm implementations for time or space efficiency, but only for elicitation efficiency. Generating all the plots in this paper took two days of computer time on a 1 GHz Pentium III.

Unfortunately, real data for combinatorial auctions are not publicly available.555Furthermore, even if the data were available, they would only have some bids, not the full valuation functions of the agents (because not all agents bid on all bundles). Therefore, as in all of the other academic work on combinatorial auctions so far, we used randomly generated data. We first considered using existing benchmark distributions. However, the existing problem generators output instances with sparse bids, that is, each agent bids on a relatively small number of bundles. This is the case for the CATS suite of economically-motivated random problem instances  as well as for the other prior benchmarks . In such cases, the communication is a non-issue, which undermines the purpose of elicitation. In addition, the instances generated by many of the earlier benchmarks do not honor the free disposal constraints (because for an agent, the value of a bundle can be less than that of a sub-bundle).

In many real settings, each bidder has a nonzero valuation for every bundle. For example in spectrum auctions, each bidder has positive value for every bundle because each item is of positive value to every bidder (at least due to renting and reselling possibilities). In other settings, there may exist worthless items for some bidders. Even in such cases, under the free disposal assumption, the bidders have positive valuations for almost all bundles—except bundles that only contain worthless items (because, at worst, they can throw away the extra items in any bundle for free).

To capture these considerations, we developed a new benchmark problem generator. In each problem instance we generate, each bidder has a nonzero valuation for almost every bundle, and all valuations honor free disposal. Specifically, the generator assigns, for each agent in turn, integer valuations using the following routine. We impose an arbitrary maximum bid value $`\mathrm{MAXBID}=10^7`$ in order to avoid integer arithmetic overflow issues, while at the same time allowing a wide range of values to be expressed. Valuations generated with this routine exhibit both complementarity and substitutability.

| GenerateBids$`(k)`$ | |
| --- | --- |
| 1 | $`G\text{new constraint network}`$ |
| 2 | $`S2^K\text{ (the set of all bundles)}`$ |
| 3 | impose free disposal constraints on $`G`$ |
| 4 | $`\text{UB}(K)\mathrm{MAXBID}`$ |
| 5 | $`\text{while }S\mathrm{}`$ |
| 6 | pick $`b`$ uniformly at random from $`S`$ |
| 7 | $`SSb`$ |
| 8 | pick $`v(b)`$ uniformly at random from $`[\text{LB}(b),\text{UB}(b)]`$ |
| 9 | propagate $`\text{LB}(b)=\text{UB}(b)=v(b)`$ through $`G`$ |

## 6 Experiments on rank lattice based elicitation

The first experiment evaluates the efficiency of rank lattice based elicitation, see Figure 2. We plot the number of rank queries made (the number of value queries is never greater because a value query is only ever asked after the corresponding rank query). For comparison, we plot the total number of value queries we could have made: $`n(2^k1)`$ (that is, for each agent, one query for each of the $`2^k`$ bundles except the empty bundle). This corresponds to full revelation of each agent’s valuation function. Because this number grows exponentially in the number of items $`k`$, we use a log scale on the vertical axis of the plot that shows performance as a function of the number of items. The other plot has a linear-scale vertical axis because full revelation increases linearly in the number of agents $`n`$.

Define the elicitation ratio to be the number of queries asked divided by the number of queries asked in full revelation. Figure 2 Left shows that as the number of items increases, the elicitation ratio approaches zero, that is, only a vanishingly small fraction of the possible queries are asked.

Figure 2 Right shows that as the number of agents $`n`$ grows, the advantage from rank lattice based elicitation decreases. This is not as important because even under full revelation, the number of queries increases only linearly. Nevertheless, this behavior might be explained by the observation that while the size of the lattice grows exponentially in $`n`$, the number of feasible nodes only grows polynomially. Specifically, the total number of rank vectors is $`(2^k)^n=2^{nk}`$ while the number of feasible rank vectors is $`n^k`$ (each of the $`k`$ items can independently go to any of the $`n`$ agents). Therefore, as $`n`$ increases, this rank lattice based search procedure encounters an increasing fraction of infeasible rank vectors before finally finding an optimal allocation.

A very recent theoretical result shows that the algorithm here is as good as any rank lattice based elicitation algorithm . Specifically, this algorithm is a member of the EBF (efficient best-first) family of algorithms, and the result proves that no algorithm based on the rank lattice can guarantee asking fewer queries than an EBF algorithm over all problem instances (unless it sacrifices economic efficiency).

## 7 General elicitation framework

Given that no rank lattice based algorithm can do better than the one outlined above, we now move to a more general elicitation framework. As we will show, this allows us to develop algorithms that ask significantly fewer queries.

The framework allows a richer set of query types (to accommodate for different settings where answering some types of queries is easier than answering other types); allows more flexible ordering of the queries at run time; and never considers infeasible solutions. We could implement rank queries in this framework, but did not do so in this work, because rank queries are somewhat unrealistic: to answer them would likely require the bidder to evaluate and sort its entire valuation function.

The general algorithm template is a slightly modified version of that of Conen & Sandholm :   Solve$`()`$  1 $`C\text{InitialCandidates}(n,k)`$  2  $`\text{while }\text{not }\text{Done}(C)`$  3 $`q\text{SelectQuery}(C)`$  4 $`\text{AskQuery}(q)`$  5 $`C\text{Prune}(C)`$

Here, $`C`$ is a set of candidates, where a *candidate* is a vector $`c=c_1,c_2,\mathrm{},c_n`$ of bundles where the bundles contain no items in common. Unlike with rank vectors, all candidates are feasible. The value of a candidate is $`v(c)=_iv_i(c_i)`$; $`\text{UB}(c)=_i\text{UB}_i(c_i)`$ is an upper bound, and $`\text{LB}(c)=_i\text{LB}_i(c_i)`$ a lower bound. A candidate $`c`$ dominates another candidate $`c^{}`$ if the elicitor can prove that the value of $`c`$ is at least as high as that of $`c^{}`$.666This is the case if $`\text{LB}(c)\text{UB}(c^{})`$. Even if not, the elicitor can use the edges in the graph. If there is a subset of the agents $`I`$ such that $`iI`$, $`c_ic_i^{}`$, and that for the remaining agents, $`_{jI}\text{LB}_j(c_j)_{jI}\text{UB}_j(c_j)`$, then this also constitutes a proof that $`c`$ has value at least as high as $`c^{}`$.

InitialCandidates generates the set of all candidates, which is the set of all $`n^k`$ allocations of the $`k`$ items to the $`n`$ agents (some agents might get no items). In our experiments, the candidate set is represented explicitly. To scale the implementation to large $`k`$ and $`n`$ would require representing it more intelligently in an implicit way.

Prune removes, one candidate at a time, each candidate that is dominated by a remaining candidate. This may eliminate some optimal allocations, but it will never eliminate all optimal allocations—one will always remain. If strict domination were to be used as the criterion, then Solve would find *all* optimal allocations, at the cost of requiring more elicitation.

Done returns true if $`C`$ is a set of candidates, each of which is provably optimal. This is the case either if $`C`$ has only one element, or if all candidates in $`C`$ have known value (that is, $`cC,\text{UB}(c)=\text{LB}(c)`$). Because the algorithm has just pruned, it knows that if all candidates have known value, then they have equal value.

SelectQuery selects the next query to be asked. This function can be instantiated in different ways to implement different elicitation policies, as we will show.

AskQuery takes a query, asks the corresponding agent for the information, and appropriately updates the constraint network. The details of updating the network are discussed in conjunction with each query type below.

### 7.1 Value queries

The most basic query asks an agent $`i`$ to reveal $`v_i(c_i)`$ exactly. We call such queries value queries. Upon receiving the answer, AskQuery sets $`\text{LB}_i(c_i)=\text{UB}_i(c_i)=v_i(c_i)`$ and propagates the new bounds upstream and downstream through the constraint network as described earlier.

Any policy that asks only value queries relies on there being edges in the constraint network, for instance due to free disposal. Otherwise, it needs to ask every query: any value the elicitor has not asked for might be infinite.

#### 7.1.1 Random elicitation policy

The first policy we investigate simply asks random value queries. In the beginning, we generate the set of all $`n(2^k1)`$ value queries. Whenever it is time to ask a query, the policy chooses a random query from the set, ignoring those it has already asked or for which the value can already be inferred.

We can actually show that if any policy saves elicitation, then this policy also saves elicitation:

###### Proposition 1

Let $`Q=n(2^k1)`$ be the total number of queries, and let $`q_{\mathrm{𝑚𝑖𝑛}}`$ be the number of queries asked by an optimal elicitation policy. For any given problem instance, the expected number of queries that the random elicitation policy asks is at most $`\frac{q_{\mathrm{𝑚𝑖𝑛}}}{q_{\mathrm{𝑚𝑖𝑛}}+1}(Q+1)`$.

Proof: Assume pessimistically that a query is either required to prove the optimal allocation or useless. Under this assumption, the analysis reduces to the following problem. We have $`r`$ red “necessary” balls and $`b`$ blue “useless” balls in a bag. We then randomly draw one ball at a time without replacement. The question is how many balls we expect to draw before all red balls have been drawn. Let $`e(r,b)`$ be this number. The base case is $`e(0,b)=0`$, because there are no red balls to draw. In the general case, we pick one ball from the bag. With probability $`r/(r+b)`$, it is red, so the bag now has $`r1`$ red balls and $`b`$ blue balls. Similarly, with probability $`b/(r+b)`$, it is blue, so the bag now has $`r`$ red balls and $`b1`$ blue balls. Therefore, $`e(r,b)=1+\frac{r}{r+b}e(r1,b)+\frac{b}{r+b}e(r,b1)`$. It is easy to verify that $`e(r,b)=\frac{r}{r+1}(b+r+1)`$ solves this recurrence. In the elicitation setting, $`r=q_{\mathrm{𝑚𝑖𝑛}}`$ and $`r+b=Q`$. The result follows.

The upper bound given in the above proposition only guarantees relatively minor savings in elicitation (especially because $`q_{\mathrm{𝑚𝑖𝑛}}`$ increases when the number of agents and items increases). This could be due to either the bound being loose, or due to this elicitation policy being poor, or both. The experiment in Figure 3 shows that this elicitation policy is poor—even in the average case. The policy asks almost all of the queries.

#### 7.1.2 Random allocatable bundle elicitation policy

Essentially, the random elicitation policy asks many queries which, as it turns out, are not useful. We will now present a useful restriction on the set of queries from which the elicitation policy should choose. The key observation is that the elicitor might already know that a bundle is not going to be allocated to a particular bidder—even before the elicitor knows the bidder’s valuation for the bundle. This can occur if the elicitor knows that it cannot obtain enough value from the other bidders for the items not in that bundle. On the other hand, if the elicitor cannot (yet) determine this, then the bundle-agent pair is called an allocatable.

###### Definition 1

A bundle-agent pair $`(b,i)`$ is allocatable if there exists a remaining candidate allocation $`cC`$ such that $`c_i=b`$. In some places, the reference to the agent is obvious from the context, so we sometimes talk about allocatable bundles $`b`$ rather than $`(b,i)`$.

Now we can refine our random elicitation policy to ask queries on allocatable $`(b,i)`$ only (and queries that have already been asked or whose answer can be inferred are again never asked).

This restriction is intuitively appealing, and we can characterize cases where it cannot hurt. We define the notation $`x,y`$ to mean that revealing the value of a non-allocatable pair $`(b,i)`$ would raise the lower bound on $`x`$ allocatable super-bundles of $`b`$ (that is, there are $`x`$ allocatable pairs $`(b^{},i)`$ such that $`b^{}b`$), and lower the upper bound on $`y`$ allocatable sub-bundles of $`b`$. To affect a lower bound, $`v_i(b)`$ must be strictly greater than the currently-proven lower bound on any of the $`x`$ super-bundles. Similarly, $`v_i(b)`$ must be strictly less than the currently-proven upper bound on the $`y`$ sub-bundles.

Given this notation, we can examine the cases where eliciting a non-allocatable $`(b,i)`$ is no more useful than eliciting some allocatable $`(b^{},i)`$. Because the elicitor does not know $`v_i(b)`$, it cannot know what case actually applies.

###### Proposition 2

No matter what value queries the elicitor has asked so far, querying a non-allocatable $`(b,i)`$ in case $`x,y`$ with $`x+y<2`$ cannot help the unrestricted random elicitation policy ask fewer queries than the restricted random elicitation policy.

Proof: We analyze each case separately.

Case $`0,0`$: In this case, $`b`$ has no allocatable sub- or super-bundles, so obtaining values for those bundles cannot be useful. So, if $`b`$ itself is not allocatable, eliciting a value for $`b`$ cannot be useful. (Here, “useful” means that it helps prove that an allocation is optimal or it helps prove that an allocation is not optimal.)

Cases $`0,1`$ and $`1,0`$: The two cases are symmetric; we assume $`0,1`$ here. Let the single allocatable sub-bundle of $`b`$ be called $`b^{}`$. By eliciting $`v_i(b)`$, the upper bound on $`v_i(b^{})`$ will be tightened. However, eliciting $`v_i(b^{})`$ would reveal an upper bound on $`b^{}`$ that is at least as tight. So eliciting the allocatable bundle $`b^{}`$ would have been no worse. In fact, it might have been strictly better: with the same number of queries, eliciting $`v_i(b^{})`$ also reveals a lower bound on $`b^{}`$ and any super-bundle of $`b^{}`$ (in particular, any allocatable super-bundle).

While the idea of restricting the queries to allocatable bundles is intuitively appealing and can never hurt in the cases above, there are cases where this restriction forces the elicitor to ask a larger number of queries:

###### Proposition 3

Querying a non-allocatable $`(b,i)`$ in case $`x,y`$ with $`x+y2`$ may help the unrestricted random elicitation policy ask fewer queries than the restricted random elicitation policy.

Proof: Assume there are two bidders. Further assume that given the information elicited previously, there are only three allocations that could be optimal ($`|C|=3`$). One allocation involves giving bidder 1 the items in bundle $`b^{}`$, and the other items to bidder 2, and bidder 2 places a value of 50 on those items. Similarly, the second allocation gives bidder 1 the items in bundle $`b^{\prime \prime }`$, and the other items to bidder 2, who again places a value of 50 on those items. Bundle $`b^{}`$ is neither a super-bundle nor a sub-bundle of $`b^{\prime \prime }`$. Given the information elicited so far, the elicitor knows $`\text{UB}_i(b^{})=\text{UB}_i(b^{\prime \prime })=100`$. A third allocation gives bidder 2 all the items, and bidder 2 places a value of 100 on this outcome; bidder 1 gets no items. Finally, assume the true value agent 1 has on bundle $`b`$ is 40 ($`v_1(b)=40`$), and that $`b`$ is not allocatable for agent 1. This means that $`(b,1)`$ is in case $`0,2`$.

In this situation, by eliciting just $`v_1(b)`$, the elicitor would prove that the third allocation (giving bidder 2 all the items) is optimal. Restricted to revealing allocatable bundles $`b^{}`$ and $`b^{\prime \prime }`$ but not $`b`$, the elicitor will instead need to use two queries instead of just one.

Proposition 3 does not mean that all cases $`x,y`$ with $`x+y2`$ are bad. Indeed, it could be that eliciting the non-allocatable $`(b,i)`$ gives insufficiently tight bounds on the allocatable bundles it affects, and therefore the allocatable bundles need to be elicited anyway. An open problem is whether, in the case of an oracle that chose the best bundle to elicit every time, the bad cases would ever happen.

The case-by-case analysis of Propositions 2 and 3 indicates that restricting the elicitation policy to choosing only allocatable bundles will often help, but may sometimes also cause harm. However, the harm is limited, as we now show.

###### Proposition 4

Any bad case $`x,y`$ with $`x+y2`$ causes the random query policy that restricts itself to allocatable queries to ask at most twice as many queries (in expectation) as the unrestricted random policy. This bound is tight.

Proof: Assume that to prove an optimal allocation, it is necessary either to reveal the single non-allocatable bundle, or *all* of the $`x+y`$ allocatable bundles. If fewer than all $`x+y`$ bundles are needed, or if there is more than one subset of the $`x+y`$ that is sufficient, this only reduces the advantage of being allowed to ask the bad-case query.

In the restricted policy, which cannot ask the bad-case query, the elicitor will ask $`x+y`$ queries. In the unrestricted policy, the elicitor’s task corresponds to removing balls one at a time from a bag that has 1 red ball and $`b=x+y`$ blue balls until either the red ball has been removed, or all the blue balls have been removed. Let $`e(b)`$ be the number of balls we expect to pick until we are done. We pick a red ball with probability $`1/(b+1)`$ and are done immediately. Otherwise, we pick a blue ball with probability $`b/(b+1)`$. Therefore, $`e(b)=\frac{1}{b+1}+\frac{b}{b+1}(1+e(b1))`$. If only one blue ball is left, whether we pick the red ball or the blue ball, we are done, so $`e(1)=1`$. It can be verified that $`e(b)=\frac{b(3+b)}{2(1+b)}`$ solves the recurrence relation. Therefore, the ratio of queries asked in the restricted policy to queries asked in the unrestricted policy is $`(x+y)/e(x+y)2`$.

Summarizing, restricting value elicitation to allocatable bundles either helps, does not hurt, or at worst only causes the elicitor to ask (in expectation) twice as many queries. We ran experiments (Figure 4) to determine whether the restriction helps in practice. The results are clear: at $`k=10`$, the elicitation ratio is $`17\%`$. That is, the random elicitation policy restricted to eliciting only allocatable $`(b,i)`$ avoids the vast majority of the elicitation needed in full revelation or in the unrestricted random elicitation policy. Most importantly, as the number of items increases, the elicitation ratio continues to decrease (unlike with the random elicitation policy without the restriction). Also, unlike with rank lattice based elicitation, as the number of agents increases, the elicitation ratio stays constant or may even decrease.

This policy is simpler than the value-query policy previously proposed by Conen & Sandholm . That policy counted the number of remaining candidates in which a given bundle $`b`$ is allocated to agent $`i`$, and elicited the value of the $`(b,i)`$ pair with the highest count. We ran the same experiment with that policy. Interestingly, that policy does far less well: depending on the tie-breaking scheme, it asked exactly all the queries (when breaking ties in favor of the smaller bundle, arbitrarily choosing among equal-size bundles), or it converged to about half the queries (when breaking ties in favor of the larger bundle). A randomized tie-breaking scheme did slightly worse than breaking ties in favor of larger bundles.

#### 7.1.3 The grand bundle is (almost) always revealed

Intuitively it is appealing to elicit from every agent the value for the grand bundle because that sets an upper bound on all bundle-agent pairs (via the free disposal assumption). In this section we analyze whether this indeed is a good idea.

###### Proposition 5

In order to determine the optimal allocation, any elicitation policy must prove an upper bound on $`v_i(K)`$ for every $`i`$ to which $`K`$ is not allocated.

Proof: The lower bound on the optimal allocation is finite (say, $`L`$) because we require each bundle to have non-negative and finite value for every bidder. Therefore, unless the auctioneer provides an upper bound on $`v_i(K)`$, the possibility is open that allocating $`K`$ to $`i`$ is worth more than $`L`$. Because allocating $`K`$ to $`i`$ possibly has value greater than implementing the allocation that is, in fact, optimal, the elicitation policy cannot terminate.

In particular, using value queries only (and with no extra structure beyond free disposal), the only way the auctioneer can establish an upper bound on $`v_i(K)`$ is by eliciting the value.

###### Theorem 1

Assume there are at least 2 bidders. There is a policy (possibly requiring an oracle for choosing the queries) using value queries that asks $`v_i(K)`$ for every $`i`$ and that asks the fewest possible questions.

Proof: If the optimal allocation involves allocating items to at least two bidders, then we are not allocating the full bundle to any agent, so by the proposition above, the auctioneer must elicit $`v_i(K)`$ for every $`i`$.

Otherwise, the optimal allocation involves allocating all items to a single agent $`i`$. For all $`ji`$, the proposition applies and therefore the auctioneer must elicit $`v_j(K)`$. What is left to prove is that the auctioneer is at least as well off also eliciting $`v_i(K)`$.

If all other bidders have zero value on all sub-bundles (that is, the full bundle has positive value to them, but anything less has zero value), then the auctioneer need only place a lower bound on $`v_i(K)`$ that is higher than any other bidder’s, which it can do by eliciting $`v_i(K)`$.

If any other bidder $`j`$ has nonzero value on some bundle $`Kb`$, the auctioneer needs to prove that $`v_j(Kb)+v_i(b)v_i(K)`$. In other words, the auctioneer needs to provide a lower bound on $`v_i(K)`$ that is sufficiently greater than the upper bound on $`v_i(b)`$. Using value queries and assuming free disposal, the auctioneer can prove an upper bound on $`v_i(b)`$ by eliciting $`b`$ or any super-bundle $`b^{}`$. Similarly, it can prove a lower bound on $`K`$ by eliciting $`K`$ or any sub-bundle. However, it cannot prove sufficiently tight bounds to separate the optimal allocation (of $`K`$ to $`i`$) from the suboptimal one by eliciting a single bundle: by eliciting a single bundle, it would prove $`\text{UB}_i(b)=\text{LB}_i(K)`$. Given that it must elicit two bundles, it may as well elicit $`v_i(K)`$ to provide the lower bound on that value.

The argument in the paragraph above generalizes to settings where there are many bidders $`j`$ who have nonzero value for several bundles $`Kb`$. The auctioneer must prove a sufficiently tight lower bound on $`K`$, and sufficiently tight upper bounds on each of the bundle-agent pairs $`(b,i)`$. Since not all the elicitations that support sufficiently tight upper bounds on $`b`$’s can also support a sufficiently tight lower bound on $`K`$, the auctioneer must elicit at least one other bundle to support that lower bound. There may be more than one choice for this; however, one possible choice is simply to elicit $`v_i(K)`$.

If $`n=1`$, the statement does not hold because without revealing anything, we already know by free disposal that giving the bidder all of $`K`$ is an optimal allocation.

### 7.2 Order queries

In some applications, agents might not know the values of bundles, and might need to expend a lot of effort to determine them , but might easily be able to see that one bundle is preferable over another. In such settings, it would be sensible for the elicitor to ask order queries, that is, ask an agent $`i`$ to order two given bundles $`c_i`$ and $`c_i^{}`$ (to say which of the two it prefers). The agent will answer $`c_ic_i^{}`$ or $`c_i^{}c_i`$ or both. AskQuery will then create new edges in the constraint network to represent these new dominates relations. By asking only order queries, the elicitor cannot compare the valuations of one agent against those of another, so it cannot determine a social welfare maximizing allocation. However, order queries can be helpful when interleaved with other types of queries.

### 7.3 Using value and order queries

We developed an elicitation policy that uses both value and order queries. It mixes them in a straightforward way, simply alternating between the two, starting with an order query. Whenever an order query is to be asked, the elicitor picks an arbitrary pair $`(c,c^{})`$ of remaining candidates that cannot be compared due to lack of information, chooses an agent $`i`$ whose ranking of $`c_i`$ and $`c_i^{}`$ is unknown, and asks that agent to order bundles $`c_i`$ and $`c_i^{}`$. (This is the policy for choosing order queries that was proposed by Conen & Sandholm .) Whenever a value query is to be asked, the query is chosen using the policy described in the value query section above.

To evaluate the mixed policy, we need a way of comparing the cost of an order query to the cost of a value query. The plots in this section correspond to a cost model where an order query costs 10% of the cost of a value query.

Figure 5 shows that the amount of elicitation grows linearly with the number of agents. Also, as the number of items increases, the cost of the queries is a vanishing fraction of the cost of full elicitation.

The policy saves elicitation cost compared to the policy that only uses value queries. For example, at 2 agents and 10 items, its elicitation cost averages 324 while the elicitation cost of the value-only policy averages 361. As the relative cost of an order query is decreases, the benefit of interleaving value queries with order queries increases. Also, if order queries are inexpensive, the policy should probably ask more than one order query per value query.

While this mixed policy appears to provide only a modest benefit over using value queries only, its advantage is that it does not depend as critically on free disposal. Without free disposal, the policy that uses value queries only would have to elicit all values. The order queries in the mixed policy, on the other hand, can create useful edges in the constraint network which the elicitor can use to prune candidates.

### 7.4 Bound-approximation queries

In many settings, the bidders can roughly estimate valuations easily, but the more accurate the estimate, the more costly it is to determine. In this sense, the bidders determine their valuations using anytime algorithms . For this reason, we introduce a new query type: a bound-approximation query. In such a query, the elicitor asks an agent $`i`$ to tighten the agent’s upper bound $`\text{UB}_i(b)`$ (or lower bound $`\text{LB}_i(b)`$) on the value of a given bundle $`b`$. This query type leads to more incremental elicitation in that queries are not answered with exact information, and the information is refined incrementally on an as-needed basis.

The elicitor can provide a hint $`t`$ to the agent as to how much additional time the agent should devote to tightening the bound in the query. Smaller values of the hint $`t`$ make elicitation more incremental, but cause additional communication overhead and computation by the elicitor. Therefore, the hint can be tailored to the setting, depending on the relative costs of communication, bundle evaluation by the bidders, and computation by the elicitor. The hint could also be adjusted at run-time, but in the experiments below, we use a fixed hint $`t=0.2`$.

To evaluate this elicitation method, we need a model on how the agents’ computation refines the bounds. We designed the details of our elicitation policy motivated by the following specific scenario, although the elicitation policy can be used generally. Let each agent have two anytime algorithms which it can run to discover its value of any given bundle: one gives a lower bound, the other gives an upper bound. Spending time $`d`$, $`0d1`$ will yield a lower bound $`v_i(b)\sqrt{d}`$ or an upper bound $`(2\sqrt{d})v_i(b)`$. This means that there are diminishing returns to computation, as is the case with most anytime algorithms.777The square root is arbitrary, but captures the case of diminishing returns to additional computation. Running experiments with $`d`$ in place of $`\sqrt{d}`$ did not significantly change the results. Finally, we assume that the algorithms can be restarted from the best solution found so far with no penalty: having spent $`d`$ time tightening a bound, we can get the bound we would have gotten spending $`d^{}>d`$ by only spending an additional time $`d^{}d`$.

The model of agents’ computation cost here opens the possibility to cheat in the evaluation of the elicitor. As the model is stated, the elicitor could ask an agent to spend $`t`$ time each on the upper and lower bound. Based on the answers, the elicitor would know the exact value (it would be in the middle between the lower and upper bound). To check that our results do not inadvertently depend on such specifics of the agents’ computation model, we ran experiments using an asymmetric cost function (linear for lower bounds, square root for upper bounds). This did not appreciably change the results.

Using arbitrarily picked bound-approximation queries as the elicitation policy would work, but the more sophisticated elicitation policy that we developed chooses the query that maximizes the expected benefit. This is the amount by which we expect the upper and lower bounds on bundle-agent pairs to be tightened when we propagate the new bound that the queried agent will return (only counting bundle-agent pairs that are included in the set of remaining candidates). To compute the expected benefit, the elicitor assumes that $`v_i(b)`$ is drawn uniformly at random in $`[\text{LB}_i(b),\text{UB}_i(b)]`$. To estimate the expected change in bounds, the elicitor samples 10 equally spaced values $`\widehat{v_i}(b)`$ in that interval. For each value, the elicitor computes (using the cost model described in the previous paragraph) what bound $`z`$ it would receive if the agent spent additional time $`t`$ working on that bound and the true value were $`\widehat{v_i}(b)`$. Finally, the elicitor observes by how much the values in the constraint network would change if the elicitor were to propagate $`z`$ through the network (only bundle-agent pairs that are included in the set of remaining candidates are counted).888A minor detail comes in estimating the worth of reducing an upper bound from $`\mathrm{}`$. We dodge this question by initially asking each agent for an upper bound on the grand bundle—which is almost always required as shown in Proposition 5. By free disposal, that is also an upper bound on all other bundles.

We evaluated bound-approximation queries using the elicitation policy and agents’ computation model described above. Figure 6 shows that as the number of items increases, only a vanishingly small fraction of the overall computation cost is actually incurred because the optimal allocation is determined while querying only very approximate valuations on most bundle-agent pairs. The method also maintains its benefit as the number of agents increases.

#### 7.4.1 Using bound-approximation and order queries

As in the policy that mixed value and order queries, we can alternate between bound-approximation queries and order queries. Figure 7 presents the results when bound-approximation queries are charged as in the previous section, and order queries are charged $`\frac{1}{10}`$. As the number of agents increases, only a vanishingly small fraction of the cost of full revelation ends up being paid. The method also maintains its benefit as the number of agents grows. The policy saves elicitation cost compared to the policy that only uses value queries. For example, at 2 agents and 8 items, its elicitation cost averages 172 while the elicitation cost of the policy that only uses bound-approximation queries averages 230. Furthermore, as the relative cost of order queries is lowered, the mixed method becomes increasingly superior to using bound-approximation queries alone.

## 8 Conclusions and future research

In all of the elicitation schemes in this paper (except the unrestricted random one), as the number of items for sale increases, the amount of information elicited is a vanishing fraction of the information collected in traditional “direct revelation mechanisms” where bidders reveal all their valuation information. Each of the elicitation schemes (except the rank lattice based one) also maintains its benefit as the number of agents increases.

While the straightforward policies we analyzed work well, some policies that attempt to be more intelligent actually perform poorly (for example, the value query policy described by Conen & Sandholm , and some other policies we tried). These poorly-performing policies have in common that they use a heuristic that maximizes the number of candidates that would be affected by the query. In contrast, the bound-approximation query policy that we introduced benefits from the heuristic of maximizing the change in bounds. Future work includes designing additional useful heuristics for selecting queries.

We showed theoretically that if it is possible to save revelation using an elicitation policy, the simple unrestricted random elicitation policy saves revelation. We also presented theoretical and experimental results that suggest that restricting value elicitation to allocatable bundles is beneficial—which was assumed by Conen & Sandholm  but is by no means obvious. For the other elicitation policies, our results were experimental. Future work includes studying their performance theoretically as well.

By using the Clarke tax mechanism  to determine the payments that the bidders have to pay, we can ensure that in a Bayes-Nash equilibrium, each agent is motivated to answer the queries truthfully, and is not less happy after the auction than before it  (under the usual assumption that the agents have quasilinear preferences). These payments can be computed by determining an optimal allocation $`n+1`$ times: once overall, and once for each agent removed in turn. Even under the highly pessimistic assumption that answers to queries in one of these problems do not help on the other problems, determining the payments entails only an $`n`$-fold increase in the number of queries. Given that our results show that we have a significantly better than $`n`$-fold benefit as the number of items grows, this would not change the fact that only a vanishingly small fraction of queries is asked.

Our bound-approximation queries take the incremental nature of elicitation to a new level. The agents are only asked for rough bounds on valuations first, and more refined approximations are elicited only on an as-needed basis. A related approach would be to propose a bound, and ask whether the agent’s valuation is above or below the bound. This suggest a relationship between preference elicitation and ascending combinatorial auctions where the auction proceeds in rounds, and in each round the bidders react to price feedback by revealing demand (e.g., ).

#### Acknowledgments

The authors thank Maverick Woo for his help on the proofs of Propositions 1 and 4.


format: text

text:
# Possible Formation Scenario of the Quark Star of Maximum Mass around 0.7 𝑀_☉

## 1 Introduction

Recently Drake et al.  (2002) have made Deep Chandra LETG+HRC-S observations of the isolated neutron star candidate RXJ185635-3754 and found that the X-ray spectrum is well-represented by a $``$ 60eV black body. Their data contain no evidence for pulsation. The derived column density favors the distance to RXJ185635-3754 to be $`D`$ 140pc instead of $`D`$ 60pc (Walter, 2001). Although Walter & Lattimer (2002) claim that the distance is $`D120`$pc and the heavy-element atmosphere of Pons et al.  (2002) should be taken, we here follow the arguments by Drake et al.  (2002).

From the observed flux, the distance and the observed temperature of RXJ185635-3754, only the radiation radius defined by $`R_{\mathrm{}}R/\sqrt{1R_g/R}`$ is determined since the observed luminosity and the observed temperature suffer from the gravitational redshift. For the given $`R_{\mathrm{}}`$, $`M`$ is given as a function of $`R`$ as

$$R_g=\frac{2GM}{c^2}=R(1(\frac{R}{R_{\mathrm{}}})^2).$$
(1)
$`M`$ is positive only for $`0<R<R_{\mathrm{}}`$ and has the maximum value $`R_{\mathrm{}}c^2/G3\sqrt{3}=0.7M_{\mathrm{}}(R_{\mathrm{}}/5.6km)`$ at $`R=R_{\mathrm{}}/\sqrt{3}`$. If $`R_{\mathrm{}}`$ is $`5.6`$km$`D_{140}`$ as suggested by Drake et al.  (2002), the maximum mass is $`0.7M_{\mathrm{}}D_{140}`$ where $`D_{140}`$ is $`D`$ in the unit of 140pc. Therefore $`R_{\mathrm{}}`$ can not determine the radius of the star but gives us the upper limit of the mass as well as the upper limit of the radius of RXJ185635-3754.

X-ray luminosity of RXJ185635-3754 is $`6\times 10^{31}`$erg/s$`D_{140}^2`$. If this is due to the accretion from a uniform medium (Bondi & Hoyle, 1944) we have the relation as

$$\pi (\frac{2GM}{V^2})^2\rho Vϵ=6\times 10^{31}\mathrm{ergs}^1D_{140}^2,$$
(2)
where $`V`$ is the velocity of RXJ185635-3754 and $`ϵ`$ is the conversion efficiency of the accreting matter to the radiation and is $`0.3c^2`$ for the quark star with the maximum mass $`0.7M_{\mathrm{}}`$(Witten, 1984). From the above equation we have

$$(\frac{M}{M_{\mathrm{}}})^2(\frac{V}{200\mathrm{k}\mathrm{m}\mathrm{s}^1})^3(\frac{n}{10^4\mathrm{cm}^3})(\frac{ϵ}{0.3c^2})=0.5D_{140}^2$$
(3)
Since the proper motion of RXJ185635-3754 is 0.3 arc-second/y $`200D_{140}\mathrm{kms}^1`$ (Walter, 2001) 111 Here we assume that the optical counterpart is the same object as RXJ185635-3754 although the luminosity in the optical band can not be explained by the Rayleigh-Jeans tail of $`60`$eV black body spectrum of RXJ185635-3754 (Pons et al. , 2002; Drake et al. , 2002; Walter & Lattimer, 2002). the required number density of the interstellar matter is rather high even for $`MM_{\mathrm{}}`$ . While the column density to RXJ185635-3754 is estimated as $`10^{20}cm^2`$ (Drake et al. , 2002) so that the high density region should be local with the maximum size of $`100`$AU. Such a local high density region of the size $`<100`$AU is observed in the interstellar medium using 21cm HI line by Frail et al.  (1994) so that RXJ185635-3754 may be passing through the high density region now.

If $`M`$ is $`0.1M_{\mathrm{}}`$, the required density of the interstellar matter is so high that the column density may be in conflict with the observed one or we need very small( $``$AU) high density region in the interstellar matter. In the latter case we expect the change of the luminosity in a time scale of 10 days or so, while only $``$2% change of the luminosity has been observed in the 19 months (Drake et al. , 2002) so that the mass is much greater than $`0.1M_{\mathrm{}}`$. In this Letter, assuming the mass and the radius of RXJ185635-3754 are $`0.7M_{\mathrm{}}`$ and $`3.2`$km, we propose a possible formation scenario of such an object.

## 2 Spherically Symmetric Model

First such a small radius object can not be the neutron star (Lattimer & Prakash, 2000). Even for the softest equation of state of the high density nuclear matter, $`R_{\mathrm{}}`$ is larger than 10km (Lattimer & Prakash, 2000). Except for the free neutron case (Oppenheimer & Volkoff, 1939), the maximum mass of the neutron star is greater than $`0.7M_{\mathrm{}}`$ (Lattimer & Prakash, 2000), which is in conflict with the maximum mass of RXJ185635-3754 from the observed $`R_{\mathrm{}}`$. The strange quark star is one of the candidate for such an object like RXJ185635-3754. In the quark star the baryon number is distributed among three quarks $`u,d`$ and $`s`$ so that the degenerate energy decreases by a factor of 0.89 compared with the proton and neutron nuclear matter (Witten, 1984). In this sense the strange quark matter is stable although it contains unstable strange quarks. This reason is essentially the same as that the unstable neutron exists stably in the stable nucleus. In MIT bag model with the large bag constant $`B=(245\mathrm{M}\mathrm{e}\mathrm{V})^4`$ suggested from the finite-temperature QCD lattice data (Peshier, Kampfer & Soff, 2001) , the maximum mass of the quark star $`M_{\mathrm{MAX}}`$ is given by

$`M_{\mathrm{MAX}}`$ $`=`$ $`0.7M_{\mathrm{}}({\displaystyle \frac{B}{(245\mathrm{M}\mathrm{e}\mathrm{V})^4}})^{1/2},`$ (4)
$`R`$ $`=`$ $`3.9km({\displaystyle \frac{B}{(245\mathrm{M}\mathrm{e}\mathrm{V})^4}})^{1/2},`$ (5)
$`\rho _c`$ $`=`$ $`1.5\times 10^{16}\mathrm{gcm}^3({\displaystyle \frac{B}{(245\mathrm{M}\mathrm{e}\mathrm{V})^4}}),`$ (6)
where $`R`$ and $`\rho _c`$ are the radius and the central density of the maximum mass quark star (Witten, 1984). Note here that the central density of the quark star with $`M_{\mathrm{MAX}}0.7M_{\mathrm{}}`$ is much higher than the central density of the neutron star $`10^{15}\mathrm{gcm}^3`$. Therefore to make a quark star from the neutron star we must consider how to increase the central density of the neutron star. If the bag constant is smaller, for example $`B=(145\mathrm{M}\mathrm{e}\mathrm{V})^4`$ as usual , the maximum mass and the radius are $`2M_{\mathrm{}}`$ and 11km, respectively. However, in this case with $`R_{\mathrm{}}=`$5.6km , $`M`$ becomes small $`0.15M_{\mathrm{}}`$ which is in conflict with the X-ray luminosity of RXJ185635-3754 as stated in §2 so that we prefer the larger bag constant.

A naive way to increase the central density of the neutron star is to add the mass to the maximum mass neutron star by accretion from the companion star or the fall back gas in the supernova event (MacFadyen , Woosley , & Heger, 2001). However the maximum mass of the neutron star is $`1.4M_{\mathrm{}}2M_{\mathrm{}}`$ (Lattimer & Prakash, 2000), which is at least two times larger than the putative maximum mass of the quark star relevant to RXJ185635-3754. The most plausible outcome of such a collapse is not the formation of the quark star but the black hole. In a sense the soft equation of state of the strange quark matter ($`P=(\rho 4B)/3`$) is favorable to the formation of the strong shock in the supernova explosion as shown by Takahara & Sato (1988). If the equation of state is soft, the large density gradient is accumulated to produce the strong shock while for the hard equation of state, the small density gradient is enough to produce the pressure gradient to support the falling gas in the collapse. However the shock is the strongest just before the formation of the black hole, that is, when the mass of the collapsing star is just a bit smaller than the maximum mass of the neutron star in the spherically symmetric model (Van Riper & Arnett, 1978). Since in our case of the formation of the quark star, the mass of the collapsing matter is much larger than the maximum mass of the quark star so that we expect the formation of the black hole. The detailed numerical simulations might be needed to confirm that the shock can not explode the outer envelope and the black hole is formed.

## 3 Rotating Model

I propose another promising scenario. First let us review the simulations of general relativistic collapse of rotating stars. Nakamura (1981) first performed the numerical simulations of general relativistic collapse of axially symmetric stars of mass $`10M_{\mathrm{}}`$ leading to the formation of rotating black holes. In these simulations the equation of state is hard with $`\gamma =2`$ in the limit of $`\rho \rho _{nuc}`$ and the rotation is differential with various values of initial angular momentum (Nakamura, 1981). Nakamura & Sato (1981a) performed similar simulations with soft equation of state of $`\gamma =4/3`$ for two kinds of rotation laws with various values of angular momentum. The results of these simulations crucially depend on one parameter $`q`$ defined by

$$q=\frac{cJ}{GM^2},$$
(7)
where $`J`$ and $`M`$ are the total angular momentum and the gravitational mass of the initial rotating star, respectively. When $`q1`$ the black hole is formed irrespective of initial rotation laws, the equation of state and the initial density distribution (Nakamura & Sato, 1981b). If $`q1`$ , the black hole is not formed but the expanding ring, the expanding disk or the jets appear depending on initial rotation laws, equation of state and initial density distribution. This conclusion was confirmed by Stark & Piran (1985) and Shibata (2000).

Physical reason for the above result is as follows; Let us consider the collapsing star of mass $`M`$ and the angular momentum $`J`$. The radius $`R_b`$ when the centrifugal force balances the gravitational force is given by

$$\frac{GM}{R_b^2}\frac{J^2}{M^2R_b^3}.$$
(8)
Using $`q`$, we can express $`R_b`$ as

$$R_b\frac{GM}{c^2}q^2.$$
(9)
Equation (9) means that if $`q1`$, $`R_b`$ is smaller than the black hole, which suggests that when the rotation becomes important, the star itself is already inside the black hole. Therefore it is natural that the black hole is formed irrespective of initial rotation laws, the equation of state and the initial density distribution.

In the sense of general relativity, the results of the simulations support the cosmic censorship hypothesis (Penrose, 1973) which says that the singularity does not exist outside the event horizon in nature. Under this hypothesis, the Kerr metric with $`a/m=q<1`$ is known to be unique as the ultimate space-time of the gravitational collapse (Robinson, 1975). Note here that $`q`$ defined in Eq. (7) and $`a/m`$ in Kerr metric are the same quantity. If the whole of the collapsing star with $`q1`$ becomes a black hole, that is the counter example of the cosmic censorship hypothesis. However numerical simulations have not yet found such a case.

In relation to the formation of the quark star, Nakamura & Sato (1981a, b) showed an interesting case of the jet formation. In their model of A146 which is the general relativistic collapse of the rotating star with $`\gamma =4/3`$ equation of state and the initial $`q=1.46`$, the jet appeared in the final phase of the collapse. This is in accord with the result of Van Riper & Arnett (1978); Takahara & Sato (1988). In the rotating collapse, when the size of the star becomes $`R_b`$ in Eq. (9), the collapse perpendicular to the rotation axis halts while the collapse along the rotation axis proceeds. When the equation of state is soft, the large density gradient accumulates to produce the jet. While if the equation of state is hard, this is not so. In reality Nakamura, Oohara & Kojima (1987) performed the simulations of the accreting neutron star with rotation. They used the equation of state with the maximum mass $`1.4M_{\mathrm{}}`$ and simulated the collapse of the rotating neutron star of mass $`1.9M_{\mathrm{}}`$. They found no jets. The final result was the differentially rotating neutron star.

Recently Baumgarte, Shapiro & Shibata (2000) computed the equilibria of differentially rotating neutron stars. They stated that some of the models exceed the Kerr limit, that is , $`q>1`$. If we add certain amount of matter to exceed the maximum mass neutron star keeping $`q>1`$, the collapse will start. At $`R_b`$, the density is estimated as

$$\rho _b\frac{M}{fR_b^3}=6.7\times 10^{16}\mathrm{gcm}^3f^1q^6(\frac{M}{3M_{\mathrm{}}})^2,$$
(10)
where $`f1`$ is the form factor of the rotating star. Since $`\rho _b`$ can be in the quark phase for appropriate parameters, the equation of state in the central core can be soft at the centrifugal bounce. Then the matter will collapse along the rotational axis to form the jet like A146 in Nakamura & Sato (1981a, b). If the jet is strong enough to explode the outer envelope and leave the central core of mass $`0.7M_{\mathrm{}}`$, the strange quark star might be formed. The important point here is that if the cosmic censorship hypothesis is correct as suggested by numerical simulations, the whole of the rotating neutron star of mass greater than the maximum mass of the neutron star with $`q>1`$ can not be a black hole directly while if $`q=0`$ it is possible to be a black hole directly.

The detailed numerical simulations are urgent to confirm or refute the present scenario of formation of the strange quark star of maximum mass around 0.7 $`M_{\mathrm{}}`$.

## 4 Discussion

Olinto (1987) showed that a seed of strange matter in a neutron star will convert the star into a strange star. As a seed, the quark nugget formed at the QCD phase transition in the early universe (Witten, 1984) can be considered. Then the capture cross section of the quark nugget by the neutron star is given by

$$\sigma \pi R_{\mathrm{NS}}(\frac{GM_{\mathrm{NS}}}{V_{\mathrm{rel}}^2})10^{18}\mathrm{cm}^2(\frac{V_{\mathrm{rel}}}{100\mathrm{k}\mathrm{m}\mathrm{s}^1})^2,$$
(11)
where $`R_{\mathrm{NS}}`$, $`M_{\mathrm{NS}}`$ and $`V_{\mathrm{rel}}`$ are the radius of the neutrons star, the mass of the neutron star and the relative velocity, respectively. In order that at least a single quark nugget should be captured in the age of the universe ($`t_U`$) for a certain neutron star , the number density of the quark nugget ($`n_{\mathrm{nugget}}`$) should be

$$n_{\mathrm{nugget}}>\frac{1}{\sigma V_{\mathrm{rel}}t_U}=10^{42}\mathrm{cm}^3(\frac{V_{\mathrm{rel}}}{100\mathrm{k}\mathrm{m}\mathrm{s}^1})(\frac{t_U}{10^{10}y})^1.$$

Since the mass density of the quark nugget is at most the same as the dark matter density, each mass of the quark nugget $`m_{\mathrm{nugget}}`$ should be smaller than $`10^{12}`$g. However such a small mass quark nugget may not be formed due to the evaporation ($`m_{\mathrm{nugget}}>10^{20}`$g for survival; Bhattacharjee et al.  (1993)). Therefore to explain the possible strange quark star of RXJ185635-3754, the quark nugget should have been captured by chance by the progenitor neutron star.

The putative mass of $`0.7M_{\mathrm{}}`$ is just the mass of the typical white dwarf (Bragaglia Renzi & Bergeron, 1995). Therefore if we can compress the white dwarf of density $`10^7\mathrm{gcm}^3`$ to $`10^{16}\mathrm{gcm}^3`$ , the strange quark star of mass $`0.7M_{\mathrm{}}`$ might be formed. A possible process is the tidal pinching proposed by Luminet & Pichon (1989). If the moderate massive black hole of mass $`2000M_{\mathrm{}}`$ exists, a white dwarf passing inside the tidal radius of the black hole may be pinched and the density increases by more than a factor 50 (Luminet & Pichon, 1989). Although the existence of such an intermediate mass black hole has been suggested (Matsumoto et al. , 2002), the number density of the white dwarfs is small $`0.01\mathrm{pc}^3`$ so that the pinching number in the age of the universe for a single intermediate mass black hole is very small as

$`N_{pinch}n_{WD}({\displaystyle \frac{6GM_{BH}}{c^2}})({\displaystyle \frac{GM_{BH}}{V_{\mathrm{rel}}^2}})V_{\mathrm{rel}}t_U`$
$`10^8({\displaystyle \frac{n_{WD}}{0.01\mathrm{pc}^^3}})({\displaystyle \frac{M_{BH}}{2000M_{\mathrm{}}}})^2({\displaystyle \frac{V_{\mathrm{rel}}}{100\mathrm{k}\mathrm{m}\mathrm{s}^1}})^1({\displaystyle \frac{t_U}{10^{10}y}}).`$
Therefore to explain the possible strange quark star of RXJ185635-3754, the white dwarf should have been tidally pinched by the intermediate mass black hole by chance.

In any scenario, if the quark star of mass $`M_{qs}0.7M_{\mathrm{}}`$ is formed, the huge binding energy $`4\times 10^{53}`$erg is liberated. The major part of this energy may be used to explode the outer envelope of the progenitor neutron star. If , however, only $`10\%`$ of this energy is deposited as the kinetic energy, it is enough to explain the luminous supernova such as SN1998bw. In the rotating model, the remnant quark star should have an initial value of $`q_{qs}1`$. Then the rotational energy is estimated as $`E_{rot}(GM_{qs}/Rc^2)^2q_{qs}^2M_{qs}c^210^{53}`$erg. This energy is larger than or comparable to the energy needed for GRB so that the formation of the quark star may be related to the central engine of GRB.

I would like to thank Chiba, Inutsuka, Tatsumi and Tsuru for useful comments. This work was supported in part by Grant-in-Aid of Scientific Research of the Ministry of Education, Culture, and Sports, No.14047212 and No.14204024.


text:
# Direct visualization of iron sheath shielding effect in MgB2 superconducting wires

(3 May 2002, Revised 9 May 2003)

## Abstract

Local magneto-optical imaging and global magnetization measurement techniques were used in order to visualize shielding effects in the superconducting core of MgB2 wires sheathed by ferromagnetic iron (Fe). The magnetic shielding can provide a Meissner-like state in the superconducting core in applied magnetic fields up to $`1`$ T. The maximum shielding fields are shown to correlate with the saturation fields of magnetization in Fe-sheaths. The shielding has been found to facilitate the appearance of an overcritical state, which is capable of achieving a critical current density ($`J_c`$) in the core which is larger than $`J_c`$ in the same wire without the sheath by a factor of $`2`$. Other effects caused by the magnetic interaction between the sheath and the superconducting core are discussed.

preprint: submitted to Supercond. Sci. Technol.

New promising horizons for applications of superconducting wires were opened up by the discovery of MgB2 superconductor discovery . MgB2 wires have been reported to have high values of the critical current density $`J_c`$, in particular in wires sheathed by mechanically hard and magnetically soft materials such as iron (Fe) said . In spite of an initial fear of local superconductivity suppression in the vicinity of the sheath-core interface, the ferromagnetic iron sheath has been found to cause a magnetic shielding effect which provided an extended range of a constant critical current $`I_c`$ in an externally applied magnetic field $`B_a`$, $`0.2B_a0.6`$ T at $`T=32`$ K joseph . The same screening effect led to either negligibly small or significantly reduced AC losses in the sheathed wires, in contrast to the high level of the losses in the wires without the screening sumpt2 . However, it is yet unclear to what extent this shielding affects the superconducting behaviour and critical currents in the wires. In fact, the high permeability of the sheath, enabling the screening classic , prevents magnetic flux entry into the superconducting core. This means that the magnetic field range of the Meissner state can be effectively extended (or shifted) to higher $`B_a`$ (a pseudo-Meissner effect sumpt ). Moreover, the interaction between soft magnetic and superconductor can enable an overcritical state carrying $`J>J_c`$ gen  without introducing additional pinning centers. In this work, by employing magneto-optical (MO) imaging and magnetization measurement techniques we directly visualize the iron shielding in MgB2 wires and show a number of effects that are the consequences of this shielding.

Fe-sheathed MgB2 mono-core (MC) and multi-filamentary (MF) superconducting wires were investigated. A detailed description of the wire manufacturing procedure and its characterization is given elsewhere pan . The MC and MF wire cross sections are shown in Fig. 1. Transport measurements of the wires provided the critical currents $`I_c=78.1`$ A and 110 A at temperature $`T=4.2`$ K in self-field for the MC and MF wires, respectively. To obtain a magnetic flux distribution over the wires with the help of the MO technique, the samples were polished down to the final longitudinal cross sections which are indicated by the black lines in Fig. 1. In the case of the MF wire, only two filaments denoted by arrows were exposed for taking MO images. An epitaxial ferrite-garnet magneto-optical indicator film with in-plane magnetization was used for the imaging. Since both kinds of the wires have exhibited a similar qualitative picture, MO observations will be shown only for the MC wire. Global magnetization measurements as a function of the applied field within $`|B_a|5`$ T at different temperatures were performed with the help of a Quantum Design MPMS SQUID magnetometer. The field was applied perpendicular to the polished planes of the wires for both, local and global, kinds of measurements.

Two sets of MO images shown in Fig. 2 were taken at different $`B_a`$ in the normal state at room temperature (RT) and in the zero-field cooled superconducting state at $`T=19`$ K. The critical temperature $`T_c`$ of the samples is $`38.6`$ K. At $`B_a90`$ mT, there is almost no differences between the MO images taken in the normal (Fig. 2(a)) and superconducting (Fig. 2(b)) states, except in the vicinity of the sheath-core interface. Generally, the darker the area on the MO images, the lower the magnetic flux density $`B_i`$ in that region; the brighter the area, the higher the flux. As can be seen, the flux is the highest in the Fe-sheath ($`B_i>B_a`$) and the lowest within the core ($`B_a>B_i0`$).

At $`B_a>90`$ mT, discrepancies between images taken at RT and 19 K (Fig. 2c, d) become obvious. The bright stripe of the flux in the middle of the core at RT and $`B_a=190`$ mT is due to the geometry of the open sheath cavity (Fig. 1a) and because in the normal state, MgB2 material is “transparent” to the magnetic flux, having no influence on its distribution. On the contrary, the stripe is absent in the images taken in the superconducting state at $`T=19`$ K, because the core is strongly diamagnetic, in particular, below the lower critical field $`B_{c1}=(B_c\mathrm{ln}\kappa )/(\kappa \sqrt{2})`$, where $`\kappa `$ is the Ginzburg-Landau parameter and $`B_c`$ \- the thermodynamic critical field. In MgB2 $`B_{c1}60`$ mT bc1 . Therefore, the magnetic flux is expelled from the interior of the core $`B_i0`$ T, so that no stripe is observed (Fig. 2d). In spite the fact that the wire is placed in $`B_a>B_{c1}`$, the core remains entirely diamagnetic at $`T<T_c`$, with the exception of some regions along the sheath (Fig. 2b, d). In these regions $`B_i0`$ could be either due to some trapped flux in cracks and voids in the core or, most probably, due to Meissner shielding currents. The shielding currents in the vicinity of the sheath-core interface arise because of the geometry of the iron sheath cylinder which, in contrast to the complete screening case of a soft magnetic sphere or infinite cylinder classic , was polished to open the core for the MO experiments. The fact that at $`B_a>B_{c1}`$ and $`T<T_c`$, $`B_i`$ within the core is $`0`$ T, we refer to as the extended Meissner-like state enabled by the shielding.

Global magnetization measurement results are shown in Fig. 3 for both MC and MF wires. Figs. 3(a) and (c) show curves measured for the same Fe-sheathed wires investigated by the MO technique. The ferromagnetic signal of the sheath dominates for both types of the wires below and above $`T_c`$. If we now subtract the sheath contribution measured above $`T_c`$ at 45 K from the curves measured below $`T_c`$, we obtain the superconducting contribution shown in Fig. 3(b) by solid circles for $`T=20`$ K for the MC wire and in (d) for 10 K and 20 K for the MF wire. A striking feature observed in these curves is the strongly suppressed (vanishing) signal at low applied fields: $`|B_a|0.5`$ T for the MC wire and $`|B_a|1`$ T for MF wire. These field intervals we attribute to the full operational range of the extended Meissner-like state in the wires. Apparently, the ranges go far beyond the maximum field available for our MO experiments ($`B_a^{\mathrm{max}}0.2`$ T). Note that the region of the suppressed magnetic moment is independent of temperature (Fig. 3(d)), indicating its non-superconducting origin. Instead, this region is well correlated with the ferromagnetic response of iron, showing the saturation of the magnetic moment at $`|B_s|=0.42`$ T and 1.12 T for the MC and MF wires, respectively. $`B_s`$ is defined at the crossing of the lines as shown in Figs. 3(a) and (c). The saturation occurs when the magnetic domains in the iron become aligned along the applied magnetic field. Below $`|B_s|`$ the flux is accumulated in the highly permeable Fe-sheath. Therefore, the filaments are effectively screened from the applied field. Above $`|B_s|`$ the screening is no longer complete. The smaller amount of the Fe-sheath material around the MC wire and the weaker stress in the sheath caused by the fabrication procedure are likely to be the factors responsible for the smaller $`B_s`$ value and, correspondingly, the narrower field range of the shielding compared to the MF wire. For the field applied along the axis of the wires we have measured pan2  one order of magnitude smaller $`B_s`$ values and narrower shielding ranges than in the transverse case presented in this work. This can be explained by the mechanical processing of the wires which creates an easy-axis in the Fe-sheath along the direction of the wire drawing.

To visualize the difference in the global magnetic behaviour of the wires which is provided by the Fe-shielding, we carefully removed the Fe-sheath from the MC wire so that the superconducting volume of the core remained unchanged after the removal. Magnetization measurements were carried out on this bare superconducting core. In Fig. 3(b) we compare two magnetic moment curves for the Fe-sheathed and bare superconducting wires measured at $`T=20`$ K. Strikingly, the magnetic moment of the Fe-sheathed wire can be larger than that for the bare wire by a factor of up to about 2 for increasing $`|B_a|`$. The magnetic moment of the sheathed wire becomes larger than that of the bare wire at $`B_aB_s`$ and remains larger up to $`B_a1.5`$ T. Since the width of a superconducting magnetic moment loop is proportional to the critical current density $`J_c`$, it is straightforward to conclude that the Fe-sheath can provide a significantly higher $`J_c`$ than that in the wires without shielding for certain fields. This is an analog of the overcritical state discussed in Ref. gen  for superconducting strips. In the case of the strips the magnetic interaction between certain geometries of a soft magnetic environment and a superconducting strip led to super-current redistribution over the strip resulting in a significant total critical current enhancement gen . In our case, the soft magnetic environment, which is the Fe-cylinder (sheath), interacts with the superconducting MgB2 core. The flux distribution over the strip with a transport current applied gen  and over the round wire with the field applied transversely to the wire sumpt  are similar, enabling the comparison. $`B_i`$ is higher at the sides than in the middle for both cases. This implies that at $`B_a`$ slightly larger than $`B_s`$, the Meissner shielding super-currents, flowing perpendicular to $`B_a`$, should be expected to be stronger at the sides of the core (A and B areas marked in Fig. 1(a)). As in the case considered for the strips gen , the magnetic interaction between the sheath and the superconducting core redistributes the super-currents so that an overcritical state is achieved (Fig. 3(b)). In contrast to the strips, magnetically sheathed wires may offer a simpler technological approach to the fabrication of long superconductors with magnetically enhanced current-carrying abilities. It is worth noting that in the case of the field applied parallel to the wire, no overcritical state was measured pan2 . In the parallel case, the shielding super-currents are evenly distributed within the core with the well-known Bean-like profile which is similar to that in the bare wire at the same conditions. Therefore, no redistribution should be expected.

Above 1.5 T in increasing $`|B_a|`$, the magnetic moment of the Fe-sheathed wire appears to be slightly suppressed compared to the bare wire (Fig. 3(b)). This can be explained as follows. The sheath, being a permeable material, accumulates $`B_i`$ that is higher than $`B_a`$. Therefore, as the superconductivity weakens in the increased field, one can expect a rapid magnetization drop in fields approaching to the irreversibility field $`B_{\mathrm{irr}}`$, defined at the merger of the descending and ascending magnetic moment branches. Eventually (above $`B_a1.5`$ T), the magnetized sheath starts to suppress the superconductivity inside the core. The magnetic moment of the sheathed wire is also slightly suppressed in decreasing $`|B_a|`$ up to $`B_s`$. This is also caused by the magnetized sheath having $`B_i>B_a`$, which along with pinning delays the exit of the frozen flux from the core. This magnetic history dependence is in agreement with the prediction of gen . As a result of the superconductivity suppression, $`B_{\mathrm{irr}}`$ is smaller in the sheathed sample than in the bare wire. Indeed, $`B_{\mathrm{irr}}^{\mathrm{sheathed}}3.0`$ T, whereas $`B_{\mathrm{irr}}^{\mathrm{bare}}4.7`$ T.

In conclusion, we visualized both locally and globally the magnetic shielding of the superconducting MgB2 filaments in the MC and MF wires sheathed by iron. A Meissner-like state with $`B_i0`$ T can exist up to the saturation field of the ferromagnetic iron. Depending on the Fe-sheath properties, $`B_s`$ was measured as large as $`1.12`$ T. The overcritical state observed in the sheathed wire can have $`J_c`$ twice as large as in the same wire after removal of the sheath. However, $`B_{\mathrm{irr}}^{\mathrm{sheathed}}<B_{\mathrm{irr}}^{\mathrm{bare}}`$. Unlike the bare wire, the magnetization of the sheathed wire strongly depends on magnetic history.

###### Acknowledgements.

We thank J. Horvat and T. Silver for careful reading of the manuscript and critical remarks. We also benefited from fulfilling discussions with Yu. A. Genenko. This work is financially supported by the Australian Research Council.