All-pay auction

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.

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

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