Prior-free mechanism

For every agent ${\displaystyle i}$, let ${\displaystyle F_{-i}}$ be the empirical distribution function calculated based on the valuations of all agents except ${\displaystyle i}$. Use the Bayesian-optimal mechanism with ${\displaystyle F_{-i}}$ to calculate price and allocation for agent ${\displaystyle i}$.

Obviously, the bid of agent ${\displaystyle i}$ affects only the prices paid by other agents and not his own price; therefore, the mechanism is truthful.[1]^{: 339–341}

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:

1. 51 buyers bid "$1"
2. 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:[1]^: 340

1. 10 buyers bid "$10";
2. 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:[1]^: 341

There do not exist constants ${\displaystyle b,c}$ and a symmetric deterministic truthful auction, that attains a profit of at least ${\displaystyle OPT/b-h\cdot c}$ in all cases in which the agents' valuations are in ${\displaystyle [1,h]}$.

In a typical random-sampling mechanism, the potential buyers are divided randomly to two sub-markets. Each buyer goes to each sub-market with probability 1/2, independently of the others. In each sub-market we compute an empirical distribution function, and use it to calculate the prices for the other sub-market. An agent's bid affects only the prices in the other market and not in his own market, so the mechanism is truthful. In many scenarios it provides a good approximation of the optimal profit, even in worst-case scenarios; see Random-sampling mechanism for references.

A consensus-estimate is a function that, with high probability, cannot be influenced by a single agent. For example, if we calculate the maximum profit that we can extract from a given set of buyers, then any buyer can influence the profit by reporting untruthfully. But if we round the maximum profit to the nearest $1000 below it, and the bids are bounded by e.g. $10, then, with high probability, a single bid will not affect the outcome at all. This guarantees that the mechanism is truthful. The consensus-estimate function should be selected carefully in order to guarantee a good profit approximation; see Consensus estimate for references.