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 i, define its virtual valuation as: :w_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)} 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 x as: :S^*(x) = \sum_i x_i\cdot w_i(v_i) - c(x) Note that the virtual surplus is usually smaller than the actual surplus. A key theorem of Myerson says that: :::
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 i to report their valuation v_i • Based on the answer and the known distribution functions F_i,f_i, compute w_i. • Compute an allocation x that maximizes the virtual surplus S^*(x). 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 w_i. 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 i the price p_i = w_i^{-1}(p'_i), where p'_i is the price determined by the VCG mechanism.
Truthfulness The Myerson mechanism is truthful whenever the allocation rule satisfies the
weak monotonicity property, i.e, the allocation function is weakly increasing in the agents' valuations. The VCG allocation rule is indeed weakly-increasing in the valuations, but we use it with the virtual-valuations rather than the real valuations. Hence, the Myerson mechanism is truthful if the virtual-valuations are weakly-increasing in the real valuations. I.e, if for all i: w_i is a weakly-increasing function of v_i. If w_i is not a weakly-increasing function of v_i, then
Myerson ironing can be used. Myerson's mechanism can be applied in various settings. Two examples are presented below.
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 F,f. Then, all bidders have the same virtual-valuation function, w. 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: :w^{-1}(0) So, if we know the probability distribution functions F,f, we can calculate the function w, and from it, find the optimal reservation price.
Digital-goods auction In a
digital goods auction, we have an unlimited supply of identical items. Each agent wants at most one item. The valuations of the agents to the item come from the same probability distribution, with functions F,f and virtual-valuation function w. The VCG mechanism allocates an item to each agent with non-negative virtual-valuation, and charges the minimum winning price, which is: :w^{-1}(0) This exactly equals the optimal sale price - the price that maximizes the
expected value of the seller's profit, given the distribution of valuations: :\arg\max_z {z\cdot (1-F(z))} == Alternatives ==