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. As shown by Riley and Samuelson (1981), [1] equilibrium bidding in an all pay auction with private information is revenue equivalent to bidding in a sealed high bid or open ascending price auction.

Contents

In the simplest version, there is complete information. The Nash equilibrium is such that each bidder plays a mixed strategy and expected pay-offs are zero. [2] The seller's expected revenue is equal to the value of the prize. However, some economic experiments and studies have shown that over-bidding is common. That is, the seller's revenue frequently exceeds that of the value of the prize, in hopes of securing the winning bid. In repeated games even bidders that win the prize frequently will most likely take a loss in the long run. [3]

The all-pay auction with complete information does not have a Nash equilibrium in pure strategies, but does have a Nash equilibrium in mixed-strategies. [4]

Forms of all-pay auctions

The most straightforward form of an all-pay auction is a Tullock auction, sometimes called a Tullock lottery after Gordon Tullock, in which everyone submits a bid but both the losers and the winners pay their submitted bids. [5] 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. Another practical examples are the bidding fee auction and the penny raffle (pejoratively known as a "Chinese auction" [6] ).

Other forms of all-pay auctions exist, such as a war of attrition (also known as biological auctions [7] ), 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. [8]

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. [8]

Using revenue equivalence to predict bidding function

Consider the two-player version of the all-pay auction and be the private valuations independent and identically distributed on a uniform distribution from [0,1]. We wish to find a monotone increasing bidding function, , that forms a symmetric Nash Equilibrium.

If player bids , he wins the auction only if his bid is larger than player 's bid . The probability for this to happen is

, since is monotone and

Thus, the probability of allocation of good to is . Thus, 's expected utility when he bids as if his private value is is given by

.

For to be a Bayesian-Nash Equilibrium, should have its maximum at so that has no incentive to deviate given sticks with his bid of .

Upon integrating, we get .

We know that if player has private valuation , then they will bid 0; . We can use this to show that the constant of integration is also 0.

Thus, we get .

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

Since are drawn iid from Unif[0,1], the expected  revenue is

.

Due to the revenue equivalence theorem, all auctions with 2 players will have an expected revenue of when the private valuations are iid from Unif[0,1]. [9]

Bidding Function in the Generic Symmetric Case

Suppose the auction has risk-neutral bidders. Each bidder has a private value drawn i.i.d. from a common smooth distribution . Given free disposal, each bidder's value is bounded below by zero. Without loss of generality, then, normalize the lowest possible value to zero.

Because the game is symmetric, the optimal bidding function must be the same for all players. Call this optimal bidding function . Because each player's payoff is defined as their expected gain minus their bid, we can recursively define the optimal bid function as follows:

Note because F is smooth the probability of a tie is zero. This means the probability of winning the auction will be equal to the CDF raised to the number of players minus 1: i.e., .

The objective now satisfies the requirements for the envelope theorem. Thus, we can write:

This yields the unique symmetric Nash Equilibrium bidding function .

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:

The optimal bids for three donors under IPV are:

To get the real optimal amount that each of the three donors should give, simply multiplied the IPV values by 1000:

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

<span class="mw-page-title-main">Fokker–Planck equation</span> Partial differential equation

In statistical mechanics and information theory, the Fokker–Planck equation is a partial differential equation that describes the time evolution of the probability density function of the velocity of a particle under the influence of drag forces and random forces, as in Brownian motion. The equation can be generalized to other observables as well. The Fokker-Planck equation has multiple applications in information theory, graph theory, data science, finance, economics etc.

In mechanics and geometry, the 3D rotation group, often denoted SO(3), is the group of all rotations about the origin of three-dimensional Euclidean space under the operation of composition.

Multi-index notation is a mathematical notation that simplifies formulas used in multivariable calculus, partial differential equations and the theory of distributions, by generalising the concept of an integer index to an ordered tuple of indices.

<span class="mw-page-title-main">Vickrey auction</span> Auction priced by second-highest sealed bid

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.

The equilibrium constant of a chemical reaction is the value of its reaction quotient at chemical equilibrium, a state approached by a dynamic chemical system after sufficient time has elapsed at which its composition has no measurable tendency towards further change. For a given set of reaction conditions, the equilibrium constant is independent of the initial analytical concentrations of the reactant and product species in the mixture. Thus, given the initial composition of a system, known equilibrium constant values can be used to determine the composition of the system at equilibrium. However, reaction parameters like temperature, solvent, and ionic strength may all influence the value of the equilibrium constant.

A continuous-time Markov chain (CTMC) is a continuous stochastic process in which, for each state, the process will change state according to an exponential random variable and then move to a different state as specified by the probabilities of a stochastic matrix. An equivalent formulation describes the process as changing state according to the least value of a set of exponential random variables, one for each possible state it can move to, with the parameters determined by the current state.

<span class="mw-page-title-main">Gauss–Newton algorithm</span> Mathematical algorithm

The Gauss–Newton algorithm is used to solve non-linear least squares problems, which is equivalent to minimizing a sum of squared function values. It is an extension of Newton's method for finding a minimum of a non-linear function. Since a sum of squares must be nonnegative, the algorithm can be viewed as using Newton's method to iteratively approximate zeroes of the components of the sum, and thus minimizing the sum. In this sense, the algorithm is also an effective method for solving overdetermined systems of equations. It has the advantage that second derivatives, which can be challenging to compute, are not required.

<span class="mw-page-title-main">Linkage principle</span>

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 tradition of auctioneers hiring art experts to examine each lot and pre-commit to provide a truthful estimate of its value.

In mathematics, in particular in algebraic geometry and differential geometry, Dolbeault cohomology (named after Pierre Dolbeault) is an analog of de Rham cohomology for complex manifolds. Let M be a complex manifold. Then the Dolbeault cohomology groups depend on a pair of integers p and q and are realized as a subquotient of the space of complex differential forms of degree (p,q).

In mathematics and economics, the envelope theorem is a major result about the differentiability properties of the value 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.

<span class="mw-page-title-main">Auction theory</span> Branch of applied economics regarding the behavior of bidders in auctions

Auction theory is an applied branch of economics which deals with how bidders act in auctions and researches how the features of auctions 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.”

<span class="mw-page-title-main">First-price sealed-bid auction</span> Auction where all participants concurrently submit undisclosed bids

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.

Competitive equilibrium is a concept of economic equilibrium, introduced by Kenneth Arrow and Gérard Debreu in 1951, 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.

In mathematics and mathematical physics, raising and lowering indices are operations on tensors which change their type. Raising and lowering indices are a form of index manipulation in tensor expressions.

<span class="mw-page-title-main">Revenue equivalence</span>

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.

<span class="mw-page-title-main">Vickrey–Clarke–Groves auction</span> Type of sealed-bid multiple-item auction

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 can be undermined by bidder collusion and in particular in some circumstances by a single bidder making multiple bids under different names. It is a generalization of a Vickrey auction for multiple items.

<span class="mw-page-title-main">Market design</span>

Market design is a practical methodology for creation of markets of certain properties, which is partially based on mechanism design. 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.

In finance, indifference pricing is a method of pricing financial securities with regard to a utility function. The indifference price is also known as the reservation price or private valuation. In particular, the indifference price is the price at which an agent would have the same expected utility level by exercising a financial transaction as by not doing so. Typically the indifference price is a pricing range for a specific agent; this price range is an example of good-deal bounds.

In mathematics, the Kodaira–Spencer map, introduced by Kunihiko Kodaira and Donald C. Spencer, is a map associated to a deformation of a scheme or complex manifold X, taking a tangent space of a point of the deformation space to the first cohomology group of the sheaf of vector fields on X.

<span class="mw-page-title-main">Price of anarchy in auctions</span>

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.

References

  1. Riley, John; Samuelson, William (1981). "Optimal Auctions". American Economic Review. 71 (3): 381–392.
  2. 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
  3. Gneezy, Uri; Smorodinsky, Rann (2006). "All-pay auctions—an experimental study". Journal of Economic Behavior & Organization. 61 (2): 255–275. doi:10.1016/j.jebo.2004.09.013.
  4. Hillman, Arye L.; Riley, John G. (March 1989). "Politically Contestable Rents and Transfers". Economics and Politics. 1 (1): 17–39. doi:10.1111/j.1468-0343.1989.tb00003.x. ISSN   0954-1985.
  5. Dimitri, Nicola (29 November 2011). "Mirror Revelation" in Second-PRice Tullock Auctions. SIDE - ISLE 2011 - Seventh Annual Conference.
  6. Carlin, Blair (5 August 2020). "What's a Chinese Auction? Overview & Modern Alternatives". OneCause. Retrieved 2 May 2024.
  7. Chatterjee, Krishnendu; Reiter, Johannes G.; Nowak, Martin A. (2012). "Evolutionary dynamics of biological auctions". Theoretical Population Biology. 81 (1): 69–80. doi:10.1016/j.tpb.2011.11.003. PMC   3279759 . PMID   22120126.
  8. 1 2 Auctions: Theory and Practice: The Toulouse Lectures in Economics; Paul Klemperer; Nuffield College, Oxford University, Princeton University Press, 2004
  9. 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