A Bayesian-optimal mechanism (BOM) is a mechanism in which the designer does not know the valuations of the agents for whom the mechanism is designed, but he knows that they are random variables and he knows the probability distribution of these variables.
Contents
- Example
- Notation
- The Myerson mechanism
- Truthfulness
- Single item auction
- Digital goods auction
- Alternatives
- References
A typical application is a seller who wants to sell some items to potential buyers. The seller wants to price the items in a way that will maximize their profit. The optimal prices depend on the amount that each buyer is willing to pay for each item. The seller does not know these amounts, but he assumes that they are drawn from a certain known probability distribution. The phrase "Bayesian optimal mechanism design" has the following meaning:
Example
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.
Notation
We assume that the agents have single-parameter utility functions, such as a single-item auction. Each agent
and by
An allocation is a vector
The surplus of an allocation is defined as:
This is the total gain of the agents, minus the cost of the auctioneer.
The surplus is the largest possible profit. If each winning agent
This maximal profit cannot be attained, because if the auctioneer will try to charge each winning agent his value
The Myerson mechanism
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
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:
Note that the virtual surplus is usually smaller than the actual surplus.
A key theorem of Myerson says that:
(the expectation is taken over the randomness in the agents' valuations).
This theorem suggests the following mechanism:
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
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
If
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
So, if we know the probability distribution functions
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
This exactly equals the optimal sale price - the price that maximizes the expected value of the seller's profit, given the distribution of valuations:
Alternatives
Bayesian-optimal mechanism design requires to know the distributions from which agents' valuations are drawn. This requirement is not always feasible. There are some other alternatives: