Prior-free mechanism

A prior-free mechanism (PFM) is a mechanism in which the designer does not have any information on the agents' valuations, not even that they are random variables from some unknown probability distribution.

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 his 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, and cannot even assume that the amounts are drawn from a probability distribution. The seller's goal is to design an auction that will produce a reasonable profit even in worst-case scenarios.

PFMs should be contrasted with two other mechanism types:

Bayesian-optimal mechanisms (BOM) assume that the agents' valuations are drawn from a known probability distribution. The mechanism is tailored to the parameters of this distribution (e.g., its median or mean value).
Prior-independent mechanisms (PIM) assume that the agents' valuations are drawn from an unknown probability distribution. They sample from this distribution in order to estimate the distribution parameters.

From the point-of-view of the designer, BOM is the easiest, then PIM, then PFM. The approximation guarantees of BOM and PIM are in expectation, while those of PFM are in worst-case.

What can we do without a prior? A naive approach is to use statistics: ask the potential buyers what their valuations are and use their replies to calculate an empirical distribution function. Then, apply the methods of Bayesian-optimal mechanism design to the empirical distribution function.

The problem with this naive approach is that the buyers may behave strategically. Since the buyers' answers affect the prices that they are going to pay, they may be incentivized to report false valuations in order to push the price down. The challenge in PFMD is to design truthful mechanisms. In truthful mechanisms, the agents cannot affect the prices they pay, so they have no incentive to report untruthfully.

Several approaches for designing truthful prior-free mechanisms are described below.

Deterministic empirical distribution

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.^[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:

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:^[1]^: 340

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:^[1]^: 341

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

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.

Consensus estimates

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.

References

^ ^a ^b ^c Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.

[agt-1] Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.

[1]