Truthful multi-unit auctions that guarantee selling all items

Question

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?

Answer 1

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.

Answer 2

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}$.