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 the designer knows that they are random variables and knows the probability distribution of these variables.
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 assumes that they are drawn from a certain known probability distribution.
The phrase "Bayesian optimal mechanism design" has the following meaning:[1]: 335–338 There is one item for sale.
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).
The Vickrey auction with a reservation price of 1/2 achieves an expected profit of 5/12, which in this case is optimal.
[2] We assume that the agents have single-parameter utility functions, such as a single-item auction.
the probability distribution function: 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.
; this means that the auctioneer takes all the surplus to themself and leaves zero utility to the agents.
This maximal profit cannot be attained because if the auctioneer will try to charge each winning agent their value
, the agents will lie and report a lower value in order to pay less.
Roger Myerson designed a Bayesian-optimal mechanism for single-parameter utility agents.
The key trick in Myerson's mechanism is to use virtual valuations.
A key theorem of Myerson says that:[1]: 336 [3] (the expectation is taken over the randomness in the agents' valuations).
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: 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.
Hence, the Myerson mechanism is truthful if the virtual-valuations are weakly-increasing in the real valuations.
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
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.
This means that the reservation price of Myerson's mechanism is exactly: So, if we know the probability distribution functions
In a digital goods auction, we have an unlimited supply of identical items.
The valuations of the agents to the item come from the same probability distribution, with functions
The VCG mechanism allocates an item to each agent with non-negative virtual-valuation, and charges the minimum winning price, which is: This exactly equals the optimal sale price - the price that maximizes the expected value of the seller's profit, given the distribution of valuations: Bayesian-optimal mechanism design requires knowing the distributions from which agents' valuations are drawn.