# Truthful multi-unit auctions that guarantee selling all items

Suppose an auctioneer has $k$ units for sale. There are $n$ bidders, each of whom are interested in a single good, and have value $v_i$ for it. If bidder $i$ has to pay $p_i$ and gets the good, he obtains utility $u_i = v_i - p_i$. A truthful mechanism is an allocation rule together with a payment rule that maps bids to winning bidders and payments. A mechanism is truthful if every bidder $i$. maximizes his utility by bidding his true valuation $v_i$.

Suppose that we sort the values so that $v_1 > v_2 > \ldots > v_n$. The standard VCG mechanism sells the $k$ goods to the $k$ highest bidders $1, 2, \ldots, k$, and charges them each the $k+1$st highest bid $v_{k+1}$ -- i.e. it obtains revenue $k\cdot v_{k+1}$.

Depending on the particular values, the auctioneer may be able to make more money by not selling every item: i.e. he could sell only a single item to the highest bidder and charge him $v_2$. This would be an improvement if $v_2 \geq k\cdot v_{k+1}$. But what if we add the constraint that the auctioneer must allocate all $k$ items?

Question: Must it be the case that any truthful mechanism which always allocates all $k$ items and guarantees revenue at least $k \cdot v_{k+1}$ for any collection of bidder valuations must always allocate the items to the $k$ highest bidders?

• What do you mean see what happens? The question is whether some mechanism is optimal. Are you suggesting attempting a search over all possible truthful mechanisms? – Jack Oct 29 '10 at 19:59
• For the curious readers: VCG=Vickrey–Clarke–Groves auction. en.wikipedia.org/wiki/… – Thierry Zell Oct 29 '10 at 23:15
• Hmm... If you don't allocate the items to the k highest bidders, who gets them? If the items don't go to the highest bidders, where is the incentive to bid high? Could this be turned into a proof? – Thierry Zell Oct 29 '10 at 23:21

The answer is No. There exists a truthful auction for $k=2$ items and 3 players meeting the standard assumptions (non-negative payments, and payments must not exceed bids) which always has revenue at least two times the minimum bid, but where the winners do not correspond to the top two bids.

For clarity in contrast to the subscripts in the question, I'll denote indices for players using superscripts.

Here is the auction.

1. If $b^1=b^2$, then players 1 and 2 win.
2. Otherwise, the two players with the top two bids win, breaking ties arbitrarily.
3. Charge both winners $\mathrm{min}\{b^1, b^2, b^3\}$.

Clearly, the payments are non-negative, the prices never exceed the bids, and for a bid $b^1=b^2=x, b^3=y$ with $x < y$ we have that player 3 loses, despite having the unique highest bid.

To show it is truthful, we need to show that for each player $i$, and each pair of bids $b^{-i}$ by her opponents, the set $\{b^i \mid i \textrm{ wins for bids } (b^i, b^{-i})\}$ is up-closed.

• $i=3$ and in $b^{-3}$, $b^1=b^2$: there are no $b^i$ for which $i$ wins in $(b^i, b^{-i})$
• $i=3$ and in $b^{-3}$, $b^1\neq b^2$: $i$ wins in $(b^i, b^{-i})$ when $b^i > \min(b^{-i})$ and loses when $b^i < \min(b^{-i})$
• $i=1$ and in $b^{-1}$, $b^2 > b^3$: $i$ wins in $(b^i, b^{-i})$ when $b^i > b^3$, and loses when $b^i < b^3$
• $i=1$ and in $b^{-1}$, $b^2 = b^3$: $i$ wins in $(b^i, b^{-i})$ when $b^i \ge b^2$, and loses when $b^i < b^2$
• $i=1$ and in $b^{-1}$, $b^2 < b^3$: $i$ wins in $(b^i, b^{-i})$ when $b^i \ge b^2$, and loses when $b^i < b^2$
• The case $i=2$ is symmetric to $i=1$. So, we are done.

Note that it seems some sort of "weird tie-breaking" is necessary: I think one can show that in every profile with distinct bids, the top two bids necessarily win.

Yes. There are only k+1 bidders willing to pay that much, so you have to sell to them (I'm assuming you are talking about mechanism satisfying the participation constraint). If the k bidders getting the goods get charged different prices, the mechanism wouldn't be truthful anymore. The only price for which you can sell all k goods and that satisfy your revenue constraint lie between $v_k$ and $v_{k+1}$. If your price is above $v_{k+1}$, bidder k could force the price to be lower by announcing a smaller valuation. Your constraint forces you then to lower the price. So the price must be $v_{k+1}$.

• Its not true that truthful mechanisms must charge all winners the same price. For example, I could split the bidders into two groups and sell k/2 units in each group using the same auction, resulting in 2 different sale prices. This isn't a better mechanism, but in arguing that the original mechanism is optimal, you have to keep mechanisms like this in mind. – Jack Oct 29 '10 at 19:30
• Yeah, that's too simple. I guess a formal proof would have the following steps: You show that such a mechanism must allocate the good to the k bidders with the highest valuation. Then the auction is pareto optimal and truthful and therefore a VCG-mechanism. Then you show that the Vickrey auction is the only one generating enough revenue for sure. – Michael Greinecker Oct 29 '10 at 19:46
• Your first step is exactly the question being asked... – Jack Oct 29 '10 at 20:16