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?

khighest 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? $\endgroup$ – Thierry Zell Oct 29 '10 at 23:21