There is one item for sale. There are two potential buyers. The valuation of each buyer is drawn i.i.d. from the uniform distribution on [0,1].
The Vickrey auction is a truthful mechanism and its expected profit, in this case, is 1/3 (the first-price sealed-bid auction is a non-truthful mechanism and its expected profit is the same).
This auction is not optimal. It is possible to get a better profit by setting a reservation price. The Vickrey auction with a reservation price of 1/2 achieves an expected profit of 5/12, which in this case is optimal.[2]
Roger Myerson designed a Bayesian-optimal mechanism for single-parameter utility agents. The key trick in Myerson's mechanism is to use virtual valuations. For every agent , define its virtual valuation as:
Note that the virtual valuation is usually smaller than the actual valuation. It is even possible that the virtual valuation be negative while the actual valuation is positive.
Define the virtual surplus of an allocation as:
Note that the virtual surplus is usually smaller than the actual surplus.
A key theorem of Myerson says that:[1]: 336 [3]
- The expected profit of any truthful mechanism is equal to its expected virtual surplus.
(the expectation is taken over the randomness in the agents' valuations).
This theorem suggests the following mechanism:
- Ask each agent to report their valuation
- Based on the answer and the known distribution functions , compute .
- Compute an allocation x that maximizes the virtual surplus .
To complete the description of the mechanism, we should specify the price that each winning agent has to pay. One way to calculate the price is to use the VCG mechanism on the virtual valuations . The VCG mechanism returns both an allocation that maximizes the virtual surplus and a price-vector. Since the price-vector corresponds to the virtual-valuations, we must convert it back to the real-valuation space. So the final step of the mechanism is:
- Take from each winning agent the price , where is the price determined by the VCG mechanism.
Single-item auction
Suppose we want to sell a single item, and we know that the valuations of all agents come from the same probability distribution, with functions . Then, all bidders have the same virtual-valuation function, . Suppose that this function is weakly-increasing. In this case, the VCG mechanism reduces to the Vickrey auction: it allocates the item to the agent with the largest valuation (highest bid). But Myerson's mechanism uses VCG with the virtual valuations, which may be negative. Hence, Myerson's mechanism, in this case, reduces to Vickrey auction with reservation price. It allocates the item to the agent with the largest valuation, but only if its virtual valuation is at least 0. This means that the reservation price of Myerson's mechanism is exactly:
So, if we know the probability distribution functions , we can calculate the function , and from it, find the optimal reservation price.