HOME

TheInfoList



OR:

In
economics Economics () is the social science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services. Economics focuses on the behaviour and intera ...
and
game theory Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has appli ...
, an all-pay auction is an
auction An auction is usually a process of buying and selling goods or services by offering them up for bids, taking bids, and then selling the item to the highest bidder or buying the item from the lowest bidder. Some exceptions to this definition ex ...
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), 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. In the simplest version, there is complete information. The
Nash equilibrium In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
is such that each bidder plays a
mixed strategy In game theory, a player's strategy is any of the options which they choose in a setting where the outcome depends ''not only'' on their own actions ''but'' on the actions of others. The discipline mainly concerns the action of a player in a game ...
and expected pay-offs are zero.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 The seller's expected revenue is equal to the value of the prize. However, some
economic experiments Experimental economics is the application of experimental methods to study economic questions. Data collected in experiments are used to estimate effect size, test the validity of economic theories, and illuminate market mechanisms. Economic expe ...
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. 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.


Forms of all-pay auctions

Several types of all-pay auctions exist; the most common form is a raffle. During a raffle, an object is placed up for bid. Each person pays to bid on the item, which in most cases involves buying a raffle ticket. Only one of the ticket holders, or bidders, will win the item. Similarly, a lottery is another form of an all-pay auction since each person who purchases a lottery ticket is paying for a chance to win. However, unlike the standard all-pay auction, some lotteries award more than one winner. The most straightforward form of an all-pay auction is a Tullock auction, sometimes called a Tullock lottery after
Gordon Tullock Gordon Tullock (; February 13, 1922 – November 3, 2014) was an economist and professor of law and Economics at the George Mason University School of Law. He is best known for his work on public choice theory, the application of economic thinkin ...
, 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 Public choice, or public choice theory, is "the use of economic tools to deal with traditional problems of political science". Gordon Tullock, 9872008, "public choice," ''The New Palgrave Dictionary of Economics''. . Its content includes the s ...
economics. One of the examples is the United States Housing and Urban Development (HUD) grants. Cities vie for these grants to get money to improve public parks, develop housing projects for the poor, maintain rail systems, etc. HUD reviews the grant applications very carefully to ensure that only the city with the best application gets the money. Ideally, no city will spend money trying to get the grant, so the entire value of the grant is obtained for ‘free’. Now, if a well-meaning councilman wants his city to win a $5 million grant, he might not mind paying $1 million to hire people to write the grant application well. This money will come out of taxes and public funds, but if it helps the city win the grant, there is $4 million to be gained. What if there are 10 cities that think this way? All 10 cities will take $1million out of public funds – $10 million. Only 1 city wins the $5 million grant. Net result: $5 million of tax-payers money is lost. In fact, according to the podcast, nearly a quarter of the grant money that cities win is spent trying to obtain the grant in the first place. Presumably the same amount is spent by cities that don’t win the grant. These cities would like to get the grants for free, but the competition inherent in the HUD evaluation means that they have to engage in a Tullock auction and risk running losses in order to win. The
dollar auction The dollar auction is a non-zero sum sequential game explored by economist Martin Shubik to illustrate a paradox brought about by traditional rational choice theory in which players are compelled to make an ultimately irrational decision based com ...
is a two player Tullock auction, or a multiplayer game in which only the two highest bidders pay their bids. Another practical example is the
bidding fee auction A bidding fee auction, also called a penny auction, is a type of all-pay auction in which all participants must pay a non-refundable fee to place each small incremental bid. The auction is extended each time a new bid is placed, typically by 10 to 2 ...
, also known as “penny auction”. Other forms of all-pay auctions exist, such as a
war of attrition The War of Attrition ( ar, حرب الاستنزاف, Ḥarb al-Istinzāf; he, מלחמת ההתשה, Milhemet haHatashah) involved fighting between Israel and Egypt, Jordan, the Palestine Liberation Organisation (PLO) and their allies from ...
(also known as biological auctions). An example is a second price all-pay auction, 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. The all pay auction is widely used in economics because it captures the essential elements of contests. It has been used to model (1) the lobbying for rents in regulated and trade protected industries, (2) technological competition and R&D races, and (3) a host of other situations including political campaigns, tournaments and job promotion. Essentially, these economic problems boil down to a contest that is an all-pay auction in effort; the player putting forth the greatest efforts the prize, while the efforts of other contestants go unrewarded.


Rules

The following analysis follows a few basic rules.Auctions: Theory and Practice: The Toulouse Lectures in Economics; Paul Klemperer; Nuffield College, Oxford University, Princeton University Press, 2004 * Each bidder submits a bid, which only depends on their valuation. * Bidders do not know the valuations of other bidders. * The analyses are based on an independent private value (IPV) environment where the valuation of each bidder is drawn independently from a uniform distribution ,1 In the IPV environment, if my value is 0.6 then the probability that some other bidder has a lower value is also 0.6. Accordingly, the probability that two other bidders have lower value is 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.


Using revenue equivalence to predict bidding function

Consider the two-player version of the all-pay auction and v_i, v_j be the private valuations independent and identically distributed on a uniform distribution from ,1 We wish to find a monotone increasing bidding function, b(v), that forms a symmetric Nash Equilibrium. Note that if player i bids b(x), he wins the auction only if his bid is larger than player j's bid b(v_j). The probability for this to happen is \mathbb (x) > b(v_j)= \mathbb > v_j= x , since b is monotone and v_j \sim \mathrm ,1/math> Thus, the probability of allocation of good to i is x. Thus, i's expected utility when he bids as if his private value is x is given by u_i(x, v_i)=v_ix-b(x). For b to be a Bayesian-Nash Equilibrium, u_i(x_i, v_i) should have its maximum at x_i = v_i so that i has no incentive to deviate given j sticks with his bid of b(v_j). \implies u_i'(v_i) = 0 \implies v_i = b'(v_i) Upon integrating, we get b(v_i) = \frac + c. We know that if player i has private valuation v_i = 0, then they will bid 0; b(0) = 0. We can use this to show that the constant of integration is also 0. Thus, we get b(v_i) = \frac. Since this function is indeed monotone increasing, this bidding strategy b constitutes a Bayesian-Nash Equilibrium. The revenue from the all-pay auction in this example is R=b(v_1)+b(v_2)=\frac+\frac Since v_1, v_2 are drawn ''
iid In probability theory and statistics, a collection of random variables is independent and identically distributed if each random variable has the same probability distribution as the others and all are mutually independent. This property is us ...
'' from Unif ,1 the expected  revenue is \mathbb \mathbb frac+\frac\mathbb ^2\int\limits_^ v^2dv =\frac. Due to the
revenue equivalence theorem Revenue equivalence is a concept in auction theory that states that given certain conditions, any mechanism that results in the same outcomes (i.e. allocates items to the same bidders) also has the same expected revenue. Notation There is a set ...
, all auctions with 2 players will have an expected revenue of \frac when the private valuations are ''
iid In probability theory and statistics, a collection of random variables is independent and identically distributed if each random variable has the same probability distribution as the others and all are mutually independent. This property is us ...
'' from Unif ,1Algorithmic 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


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 to so that IPV may apply. According to the formula for optimal bid: b_i(v_i)=\left(\frac\right)^ The optimal bids for three donors under IPV are: b_1(v_1)=\left(\frac\right)^=\left(\frac\right)^ = 0.0104 b_2(v_2)=\left(\frac\right)^=\left(\frac\right)^ = 0.0833 b_3(v_3)=\left(\frac\right)^=\left(\frac\right)^ = 0.2813 To get the real optimal amount that each of the three donors should give, simply multiplied the IPV values by 1000: b_1real(v_1=0.25)= $10.4 b_2real(v_2=0.50)= $83.3 b_3real(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

{{Game theory Non-cooperative games Types of auction Mathematical economics