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:
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.
For every agent
i
F-i
i
F-i
i
Obviously, the bid of agent
i
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:
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:
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:
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
OPT/b-h ⋅ c
[1,h]
See main article: Random-sampling mechanism. 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.
See main article: Consensus estimate. 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.