Prior-free mechanism

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Prior-free mechanism" – news · newspapers · books · scholar · JSTOR (May 2021)

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.