# All-pay auction

Last updated

In economics and game theory, an all-pay auction is an auction in which every bidder must pay regardless of whether they win the prize, which is awarded to the highest bidder as in a conventional auction.

## Contents

In an all-pay auction, the Nash equilibrium is such that each bidder plays a mixed strategy and their expected pay-off is zero. [1] The seller's expected revenue is equal to the value of the prize. However, some economic experiments have shown that over-bidding is common. That is, the seller's revenue frequently exceeds that of the value of the prize, and in repeated games even bidders that win the prize frequently will most likely take a loss in the long run. [2]

## Forms of all-pay auctions

The most straightforward form of an all-pay auction is a Tullock auction, sometimes called a Tullock lottery, in which everyone submits a bid but both the losers and the winners pay their submitted bids. This is instrumental in describing certain ideas in public choice economics.[ citation needed ] The dollar auction is a two player Tullock auction, or a multiplayer game in which only the two highest bidders pay their bids.

A conventional lottery or raffle can also be seen as a related process, since all ticket-holders have paid but only one gets the prize. Commonplace practical examples of all-pay auctions can be found on several "penny auction" / bidding fee auction websites.

Other forms of all-pay auctions exist, such as a war of attrition (also known as biological auctions [3] ), in which the highest bidder wins, but all (or more typically, both) bidders pay only the lower bid. The war of attrition is used by biologists to model conventional contests, or agonistic interactions resolved without recourse to physical aggression.

## Rules

The following analysis follows a few basic rules. [4]

• Each bidder submits a bid, which only depends on their valuation.
• Bidders do not know the valuations of other bidders.
• The analysis are based on an independent private value (IPV) environment where the valuation of each bidder is drawn independently from a uniform distribution [0,1]. In the IPV environment, if my value is 0.6 then the probability that some other bidder has lower value is also 0.6. Accordingly, the probability that two other bidders have lower value is ${\textstyle 0.6^{2}=0.36}$.

## Symmetry Assumption

In IPV bidders are symmetric because valuations are from the same distribution. These make the analysis focus on symmetric and monotonic bidding strategies. This implies that two bidders with the same valuation will submit the same bid. As a result, under symmetry, the bidder with the highest value will always win. [4]

## Using Revenue equivalence to predict bidding function

Consider the two-player version of the all-pay auction and ${\displaystyle v_{i},v_{j}}$ be the private valuations independent and identically distributed on a uniform distribution from [0,1]. We wish to find a monotone increasing bidding function, ${\displaystyle b(v)}$, that forms a symmetric Nash Equilibrium.

Note that if player ${\displaystyle i}$ bids ${\displaystyle b(x)}$, he wins the auction only if his bid is larger than player ${\displaystyle j}$'s bid ${\displaystyle b(v_{j})}$. The probability for this to happen is

${\displaystyle \mathbb {P} [b(x)>b(v_{j})]=\mathbb {P} [x>v_{j}]=x}$, since ${\displaystyle b}$ is monotone and ${\displaystyle v_{j}\sim }$ Unif[0,1]

Thus, the probability of allocation of good to ${\displaystyle i}$ is ${\displaystyle x}$. Thus, ${\displaystyle i}$'s expected utility when he bids as if his private value is ${\displaystyle x}$ is given by

${\displaystyle u_{i}(x|v_{i})=v_{i}x-b(x)}$.

For ${\displaystyle b}$ to be a Bayesian-Nash Equilibrium, ${\displaystyle u_{i}(x_{i}|v_{i})}$ should have it's maximum at ${\displaystyle x_{i}=v_{i}}$ so that ${\displaystyle i}$ has no incentive to deviate given ${\displaystyle j}$ sticks with his bid of ${\displaystyle b(v_{j})}$.

${\displaystyle \implies u_{i}'(v_{i})=0\implies v_{i}=b'(v_{i})}$

Upon integrating, we get ${\displaystyle b(v_{i})={\frac {v_{i}^{2}}{2}}}$.

Since this function is indeed monotone increasing, this bidding strategy ${\displaystyle b}$ constitutes a Bayesian-Nash Equilibrium. The revenue from the all-pay auction in this example is

${\displaystyle R=b(v_{1})+b(v_{2})={\frac {v_{1}^{2}}{2}}+{\frac {v_{2}^{2}}{2}}}$

Since ${\displaystyle v_{1},v_{2}}$ are drawn iid from Unif[0,1], the expected  revenue is

${\displaystyle \mathbb {E} [R]=\mathbb {E} [{\frac {v_{1}^{2}}{2}}+{\frac {v_{2}^{2}}{2}}]=\mathbb {E} [v^{2}]=\int \limits _{0}^{1}v^{2}dv={\frac {1}{3}}}$.

Due to the revenue equivalence theorem, all auctions with 2 players will have an expected revenue of ${\displaystyle {\frac {1}{3}}}$ when the private valuations are iid from Unif[0,1]. [5]

## Examples

Consider a corrupt official who is dealing with campaign donors: Each wants him to do a favor that is worth somewhere between $0 and$1000 to them (uniformly distributed). Their actual valuations are $250,$500 and $750. They can only observe their own valuations. They each treat the official to an expensive present - if they spend X Dollars on the present then this is worth X dollars to the official. The official can only do one favor and will do the favor to the donor who is giving him the most expensive present. This is a typical model for all-pay auction. To calculate the optimal bid for each donor, we need to normalize the valuations {250, 500, 750} to {0.25, 0.5, 0.75} so that IPV may apply. According to the formula for optimal bid: ${\displaystyle b_{i}(v_{i})=\left({\frac {n-1}{n}}\right){v_{i}}^{n}}$ The optimal bids for three donors under IPV are: ${\displaystyle b_{1}(v_{1})=\left({\frac {n-1}{n}}\right){v_{1}}^{n}=\left({\frac {2}{3}}\right){0.25}^{3}=0.0104}$ ${\displaystyle b_{2}(v_{2})=\left({\frac {n-1}{n}}\right){v_{2}}^{n}=\left({\frac {2}{3}}\right){0.50}^{3}=0.0833}$ ${\displaystyle b_{3}(v_{3})=\left({\frac {n-1}{n}}\right){v_{3}}^{n}=\left({\frac {2}{3}}\right){0.75}^{3}=0.2813}$ To get the real optimal amount that each of the three donors should give, simply multiplied the IPV values by 1000: ${\displaystyle b_{1}real(v_{1}=0.25)=\10.4}$ ${\displaystyle b_{2}real(v_{2}=0.50)=\83.3}$ ${\displaystyle b_{3}real(v_{3}=0.75)=\281.3}$ This example implies that the official will finally get$375 but only the third donor, who donated \$281.3 will win the official's favor. Note that the other two donors know their valuations are not high enough (low chance of winning),  so they do not donate much, thus balancing the possible huge winning profit and the low chance of winning.

## Related Research Articles

In algebra, a valuation is a function on a field that provides a measure of size or multiplicity of elements of the field. It generalizes to commutative algebra the notion of size inherent in consideration of the degree of a pole or multiplicity of a zero in complex analysis, the degree of divisibility of a number by a prime number in number theory, and the geometrical concept of contact between two algebraic or analytic varieties in algebraic geometry. A field with a valuation on it is called a valued field.

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 to networked-systems.

A Vickrey auction 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.

The linkage principle is a finding of auction theory. It states that auction houses have an incentive to pre-commit to revealing all available information about each lot, positive or negative. The linkage principle is seen in the art market with the age-old tradition of auctioneers hiring art experts to examine each lot and pre-commit to provide a truthful estimate of its value.

In common valueauctions the value of the item for sale is identical amongst bidders, but bidders have different information about the item's value. This stands in contrast to a private value auction where each bidder's private valuation of the item is different and independent of peers' valuations.

A Japanese auction is a dynamic auction format. It proceeds in the following way.

The envelope theorem is a result about the differentiability properties of the objective function of a parameterized optimization problem. As we change parameters of the objective, the envelope theorem shows that, in a certain sense, changes in the optimizer of the objective do not contribute to the change in the objective function. The envelope theorem is an important tool for comparative statics of optimization models.

Auction theory is an applied branch of economics which deals with how people act in auction markets and researches the properties of auction markets. There are many possible designs for an auction and typical issues studied by auction theorists include the efficiency of a given auction design, optimal and equilibrium bidding strategies, and revenue comparison. Auction theory is also used as a tool to inform the design of real-world auctions; most notably auctions for the privatization of public-sector companies or the sale of licenses for use of the electromagnetic spectrum.

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 they submitted.

Competitive equilibrium is the traditional concept of economic equilibrium, appropriate for the analysis of commodity markets with flexible prices and many traders, and serving as the benchmark of efficiency in economic analysis. It relies crucially on the assumption of a competitive environment where each trader decides upon a quantity that is so small compared to the total quantity traded in the market that their individual transactions have no influence on the prices. Competitive markets are an ideal standard by which other market structures are evaluated.

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.

A Vickrey–Clarke–Groves (VCG) auction is a type of sealed-bid auction of multiple items. Bidders submit bids that report their valuations for the items, without knowing the bids of the other bidders. The auction system assigns the items in a socially optimal manner: it charges each individual the harm they cause to other bidders. It gives bidders an incentive to bid their true valuations, by ensuring that the optimal strategy for each bidder is to bid their true valuations of the items. It is a generalization of a Vickrey auction for multiple items.

In game theory, decision-makers deduce strategies for how to behave within the constraints of a game. Market design is the flip side of that coin: given a set of agents, market design seeks to identify the game rules a market designer might implement that would produce the desired behaviors in the players. In some markets, prices may be used to induce the desired outcomes—these markets are the study of auction theory. In other markets, prices may not be used—these markets are the study of matching theory.

The generalized second-price auction (GSP) is a non-truthful auction mechanism for multiple items. Each bidder places a bid. The highest bidder gets the first slot, the second-highest, the second slot and so on, but the highest bidder pays the price bid by the second-highest bidder, the second-highest pays the price bid by the third-highest, and so on. First conceived as a natural extension of the Vickrey auction, it conserves some of the desirable properties of the Vickrey auction. It is used mainly in the context of keyword auctions, where sponsored search slots are sold on an auction basis. The first analyses of GSP are in the economics literature by Edelman, Ostrovsky, and Schwarz and by Varian. It is used by Google's AdWords technology, and it was employed by Facebook, which has now switched to Vickrey–Clarke–Groves auction

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 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.

In auction theory, jump bidding is the practice of increasing the current price in an English auction, substantially more than the minimal allowed amount.

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. Jehiel P, Moldovanu B (2006) Allocative and informational externalities in auctions and related mechanisms. In: Blundell R, Newey WK, Persson T (eds) Advances in Economics and Econometrics: Volume 1: Theory and Applications, Ninth World Congress, vol 1, Cambridge University Press, chap 3
2. Gneezy and Smorodinsky (2006), All-pay auctions - An experimental study, Journal of Economic Behavior & Organization, Vol 61, pp. 255–275
3. Chatterjee, Reiter, and Nowak (2012), Evolutionary Dynamics of Biological Auctions, Theoretical Population Biology, Vol 81, pp. 69–80
4. Auctions: Theory and Practice: The Toulouse Lectures in Economics; Paul Klemperer; Nuffield College, Oxford University, Princeton University Press, 2004
5. Algorithmic Game Theory. Vazirani, Vijay V; Nisan, Noam; Roughgarden, Tim; Tardos, Eva; Cambridge, UK: Cambridge University Press, 2007.  Complete preprint on-line at http://www.cs.cmu.edu/~sandholm/cs15-892F13/algorithmic-game-theory.pdf