Prior-free mechanism

Last updated June 18, 2023

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.

Related Research Articles

Mechanism design is a field in economics and game theory that takes an objectives-first approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally. Because it starts at the end of the game, then goes backwards, it is also called reverse game theory. It has broad applications, from economics and politics in such fields as market design, auction theory and social choice theory to networked-systems.

In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about what the others do, you fare best or at least not worse by being truthful.

A Vickrey auction or sealed-bid second-price auction (SBSPA) is a type of sealed-bid auction. Bidders submit written bids without knowing the bid of the other people in the auction. The highest bidder wins but the price paid is the second-highest bid. This type of auction is strategically similar to an English auction and gives bidders an incentive to bid their true value. The auction was first described academically by Columbia University professor William Vickrey in 1961 though it had been used by stamp collectors since 1893. In 1797 Johann Wolfgang von Goethe sold a manuscript using a sealed-bid, second-price auction.

A double auction is a process of buying and selling goods with multiple sellers and multiple buyers. Potential buyers submit their bids and potential sellers submit their ask prices to the market institution, and then the market institution chooses some price p that clears the market: all the sellers who asked less than p sell and all buyers who bid more than p buy at this price p. Buyers and sellers that bid or ask for exactly p are also included. A common example of a double auction is stock exchange.

The Myerson–Satterthwaite theorem is an important result in mechanism design and the economics of asymmetric information, and named for Roger Myerson and Mark Satterthwaite. Informally, the result says that there is no efficient way for two parties to trade a good when they each have secret and probabilistically varying valuations for it, without the risk of forcing one party to trade at a loss.

Auction theory is an applied branch of economics which deals with how bidders act in auction markets and researches how the features of auction markets incentivise predictable outcomes. Auction theory is a tool used to inform the design of real-world auctions. Sellers use auction theory to raise higher revenues while allowing buyers to procure at a lower cost. The conference of the price between the buyer and seller is an economic equilibrium. Auction theorists design rules for auctions to address issues which can lead to market failure. The design of these rulesets encourages optimal bidding strategies among a variety of informational settings. The 2020 Nobel Prize for Economics was awarded to Paul R. Milgrom and Robert B. Wilson “for improvements to auction theory and inventions of new auction formats.”

The revelation principle is a fundamental principle in mechanism design. It states that if a social choice function can be implemented by an arbitrary mechanism, then the same function can be implemented by an incentive-compatible-direct-mechanism with the same equilibrium outcome (payoffs).

A first-price sealed-bid auction (FPSBA) is a common type of auction. It is also known as blind auction. In this type of auction, all bidders simultaneously submit sealed bids so that no bidder knows the bid of any other participant. The highest bidder pays the price that was submitted.

Revenue equivalence is a concept in auction theory that states that given certain conditions, any mechanism that results in the same outcomes also has the same expected revenue.

In mechanism design, a Vickrey–Clarke–Groves (VCG) mechanism is a generic truthful mechanism for achieving a socially-optimal solution. It is a generalization of a Vickrey–Clarke–Groves auction. A VCG auction performs a specific task: dividing items among people. A VCG mechanism is more general: it can be used to select any outcome out of a set of possible outcomes.

A random-sampling mechanism (RSM) is a truthful mechanism that uses sampling in order to achieve approximately-optimal gain in prior-free mechanisms and prior-independent mechanisms.

A Bayesian-optimal mechanism (BOM) is a mechanism in which the designer does not know the valuations of the agents for whom the mechanism is designed, but the designer knows that they are random variables and knows the probability distribution of these variables.

Consensus estimate is a technique for designing truthful mechanisms in a prior-free mechanism design setting. The technique was introduced for digital goods auctions and later extended to more general settings.

In mechanism design and auction theory, a profit extraction mechanism is a truthful mechanism whose goal is to win a pre-specified amount of profit, if it is possible.

A Prior-independent mechanism (PIM) is a mechanism in which the designer knows that the agents' valuations are drawn from some probability distribution, but does not know the distribution.

In auction theory, particularly Bayesian-optimal mechanism design, a virtual valuation of an agent is a function that measures the surplus that can be extracted from that agent.

Bayesian-optimal pricing is a kind of algorithmic pricing in which a seller determines the sell-prices based on probabilistic assumptions on the valuations of the buyers. It is a simple kind of a Bayesian-optimal mechanism, in which the price is determined in advance without collecting actual buyers' bids.

A sequential auction is an auction in which several items are sold, one after the other, to the same group of potential buyers. In a sequential first-price auction (SAFP), each individual item is sold using a first price auction, while in a sequential second-price auction (SASP), each individual item is sold using a second price auction.

The Price of Anarchy (PoA) is a concept in game theory and mechanism design that measures how the social welfare of a system degrades due to selfish behavior of its agents. It has been studied extensively in various contexts, particularly in auctions.

Regularity, sometimes called Myerson's regularity, is a property of probability distributions used in auction theory and revenue management. Examples of distributions that satisfy this condition include Gaussian, uniform, and exponential; some power law distributions also satisfy regularity. Distributions that satisfy the regularity condition are often referred to as "regular distributions".

References

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[agt-1] 1 2 3 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]