For every agent i, let F_{-i} be the empirical distribution function calculated based on the valuations of all agents except i. Use the Bayesian-optimal mechanism with F_{-i} to calculate price and allocation for agent i. Obviously, the bid of agent i affects only the prices paid by other agents and not his own price; therefore, the mechanism is truthful. This "empirical
Myerson mechanism" works in some cases but not in others. Here is a case in which it works quite well. Suppose we are in a
digital goods auction. We ask the buyers for their valuation of the good, and get the following replies: • 51 buyers bid "$1" • 50 buyers bid "$3". For each of the buyers in group 1, the empirical distribution is 50 $1-buyers and 50 $3-buyers, so the empirical distribution function is "0.5 chance of $1 and 0.5 chance of $3". For each of the buyers in group 2, the empirical distribution is 51 $1-buyers and 49 $3-buyers, so the empirical distribution function is "0.51 chance of $1 and 0.49 chance of $3". The Bayesian-optimal price in both cases is $3. So in this case, the price given to all buyers will be $3. Only the 50 buyers in group 2 agree to that price, so our profit is $150. This is an optimal profit (a price of $1, for example, would give us a profit of only $101). In general, the empirical-Myerson mechanism works if the following are true: • There are no feasibility constraints (no issues of incompatibility between allocations to different agents), like in a
digital goods auction; • The valuations of all agents are drawn independently from the same unknown distribution; • The number of the agents is large. Then, the profit of the empirical Myerson mechanism approaches the optimum. If some of these conditions are not true, then the empirical-Myerson mechanism might have poor performance. Here is an example. Suppose that: • 10 buyers bid "$10"; • 91 buyers bid "$1". For each buyer in group 1, the empirical distribution function is "0.09 chance of $10 and 0.91 chance of $1" so the Bayesian-optimal price is $1. For each buyer in group 2, the empirical distribution function is "0.1 chance of $10 and 0.9 chance of $1" so the Bayesian-optimal price is $10. The buyers in group 1 pay $1 and the buyers in group 2 do not want to pay $10, so we end up with a profit of $10. In contrast, a price of $1 for everyone would have given us a profit of $101. Our profit is less than %10 of the optimum. This example can be made arbitrarily bad. Moreover, this example can be generalized to prove that: ::There do not exist constants b,c and a symmetric deterministic truthful auction, that attains a profit of at least OPT/b - h\cdot c in all cases in which the agents' valuations are in [1,h]. == Random sampling ==