Vickrey–Clarke–Groves auction

Consider an auction where a set of identical products are being sold. Bidders can take part in the auction by announcing the maximum price they are willing to pay to receive N products. Each buyer is allowed to declare more than one bid, since its willingness-to-pay per unit might be different depending on the total number of units it receives. Bidders cannot see other people's bids at any moment since they are sealed (only visible to the auction system). Once all the bids are made, the auction is closed.

All the possible combinations of bids are then considered by the auction system, and the one maximizing the total sum of bids is kept, with the condition that it does not exceed the total amount of products available and that at most one bid from each bidder can be used. Bidders who have made a successful bid then receive the product quantity specified in their bid. The price they pay in exchange, however, is not the amount they had bid initially but only the marginal harm their bid has caused to other bidders (which is at most as high as their original bid).

This marginal harm caused to other participants (i.e. the final price paid by each individual with a successful bid) can be calculated as: (sum of bids of the auction from the best combination of bids excluding the participant under consideration) − (what other winning bidders have bid in the current (best) combination of bids). If the sum of bids of the second best combination of bids is the same as that of the best combination, then the price paid by the buyers will be the same as their initial bid. In all other cases, the price paid by the buyers will be lower.

At the end of the auction, the total utility has been maximized since all the goods have been attributed to the people with the highest combined willingness-to-pay. If agents are fully rational and in the absence of collusion, we can assume that the willingness to pay have been reported truthfully since only the marginal harm to other bidders will be charged to each participant, making truthful reporting a weakly-dominant strategy. This type of auction, however, will not maximize the seller's revenue unless the sum of bids of the second best combination of bids is equal to the sum of bids of the best combination of bids.

The following is a proof that bidding one's true valuations for the auctioned items is optimal.[6]

For each bidder ${\displaystyle b_{i}}$, let ${\displaystyle v_{i}}$ be their true valuation of an item ${\displaystyle t_{i}}$, and suppose (without loss of generality) that ${\displaystyle b_{i}}$ wins ${\displaystyle t_{i}}$ upon submitting their true valuations. Then the net utility ${\displaystyle U_{i}}$ attained by ${\displaystyle b_{i}}$ is given by their own valuation of the item they've won, minus the price they've paid:

${\displaystyle {\begin{aligned}U_{i}&=v_{i}-\left(V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right)\\&=\sum _{j}v_{j}-\sum _{j\neq i}v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}-V_{N\setminus \{b_{i}\}}^{M}\\&=\sum _{j}v_{j}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}-V_{N\setminus \{b_{i}\}}^{M}\\&=\sum _{j}v_{j}-V_{N\setminus \{b_{i}\}.}^{M}\end{aligned}}}$

As ${\displaystyle V_{N\setminus \{b_{i}\}}^{M}}$ is independent of ${\displaystyle v_{i}}$, the maximization of net utility is pursued by the mechanism along with the maximization of corporate gross utility ${\displaystyle \sum _{j}v_{j}}$ for the declared bid ${\displaystyle v_{i}}$.

To make it clearer, let us form the difference ${\displaystyle U_{i}-U_{j}=\left[v_{i}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right]-\left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]}$ between net utility ${\displaystyle U_{i}}$ of ${\displaystyle b_{i}}$ under truthful bidding ${\displaystyle v_{i}}$ gotten item ${\displaystyle t_{i}}$, and net utility ${\displaystyle U_{j}}$ of bidder ${\displaystyle b_{i}}$ under non-truthful bidding ${\displaystyle v'_{i}}$ for item ${\displaystyle t_{i}}$ gotten item ${\displaystyle t_{j}}$ on true utility ${\displaystyle v_{j}}$.

${\displaystyle \left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]}$ is the corporate gross utility obtained with the non-truthful bidding. But the allocation assigning ${\displaystyle t_{j}}$ to ${\displaystyle b_{i}}$ is different from the allocation assigning ${\displaystyle t_{i}}$ to ${\displaystyle b_{i}}$ which gets maximum (true) gross corporate utility. Hence ${\displaystyle \left[v_{i}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right]-\left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]\geq 0}$ and ${\displaystyle U_{i}\geq U_{j}}$ q.e.d.

• Vickrey–Clarke–Groves mechanism
• Vickrey auction
• Preference revelation