War of attrition (game)

In game theory, the war of attrition is a dynamic timing game in which players choose a time to stop, and fundamentally trade off the strategic gains from outlasting other players and the real costs expended with the passage of time. Its precise opposite is the pre-emption game, in which players elect a time to stop, and fundamentally trade off the strategic costs from outlasting other players and the real gains occasioned by the passage of time. The model was originally formulated by John Maynard Smith;[1] a mixed evolutionarily stable strategy (ESS) was determined by Bishop & Cannings.[2] An example is a second price all-pay auction, in which the prize goes to the player with the highest bid and each player pays the loser's low bid (making it an all-pay sealed-bid second-price auction).

Examining the game

edit

To see how a war of attrition works, consider the all pay auction: Assume that each player makes a bid on an item, and the one who bids the highest wins a resource of value V. Each player pays his bid. In other words, if a player bids b, then his payoff is -b if he loses, and V-b if he wins. Finally, assume that if both players bid the same amount b, then they split the value of V, each gaining V/2-b. Finally, think of the bid b as time, and this becomes the war of attrition, since a higher bid is costly, but the higher bid wins the prize.

The premise that the players may bid any number is important to analysis of the all-pay, sealed-bid, second-price auction. The bid may even exceed the value of the resource that is contested over. This at first appears to be irrational, being seemingly foolish to pay more for a resource than its value; however, remember that each bidder only pays the low bid. Therefore, it would seem to be in each player's best interest to bid the maximum possible amount rather than an amount equal to or less than the value of the resource.

There is a catch, however; if both players bid higher than V, the high bidder does not so much win, but loses less. The player who bid the lesser value b loses b and the one who bid more loses b -V (where, in this scenario, b>V). This situation is commonly referred to as a Pyrrhic victory. For a tie such that b>V/2, they both lose b-V/2. Luce and Raiffa referred to the latter situation as a "ruinous situation";[3] both players suffer, and there is no winner.

The conclusion one can draw from this pseudo-matrix is that there is no value to bid which is beneficial in all cases, so there is no dominant strategy. However, there are multiple asymmetric weak Nash Equilibria in pure strategies. For example, either player could commit to any bid bV. The other player's best response is to bid zero as there is no bid with which they can win the prize and receive a positive payoff.[4] The player with the positive bid pays nothing in equilibrium. So, they have no incentive to bid less. This equilibrium is subgame perfect.[5]

There is also a symmetric equilibrium in mixed strategies.

Symmetric Nash equilibrium

edit

Another popular formulation of the war of attrition is as follows: two players are involved in a dispute. The value of the object to each player is  . Time is modeled as a continuous variable which starts at zero and runs indefinitely. Each player chooses when to concede the object to the other player. In the case of a tie, each player receives   utility. Time is valuable, each player uses one unit of utility per period of time. This formulation is slightly more complex since it allows each player to assign a different value to the object. We assume that both players know the valuation of the other player. Thus, the game is a complete information game.

The unique symmetric Nash equilibrium is defined by the following survival function for t:[6]

 

The value  , for a player i whose opponent values the resource at   over time t, is the probability that t ≥ x. This strategy does not guarantee the win for either player. Rather, it is the optimal strategy given that your opponent also plays a strategy of the same form. Note that if  ,

 

So, the player with the lower value persists longer than the player with the higher value. This means that the player with the lower value has a higher probability of winning the war.[4] Note that there does not exist any x such that the survival function equals zero. So, the distribution of bids has full support. Moreover, both players receive an expected payoff of zero because their payoff is zero at t=0 and their expected payoff must be equal at every value of t.

Dynamic formulation and evolutionarily stable strategy

edit

The unique evolutionarily stable strategy coincides with the symmetric Nash equilibrium.[7] This follows from the fact that any ESS must be a Nash equilibrium and the fact that no pure persistence time can be an ESS. That no pure persistence time is an ESS can be demonstrated simply by considering a putative ESS bid of x, which will be beaten by a bid of x+ .

It has also been shown that even if the individuals can only play pure strategies, the time average of the strategy value of all individuals converges precisely to the calculated ESS. In such a setting, one can observe a cyclic behavior of the competing individuals.[8]

See also

edit

References

edit
  1. ^ Maynard Smith, J. (1974). "The theory of games and the evolution of animal conflicts" (PDF). Journal of Theoretical Biology. 47: 209–221. doi:10.1016/0022-5193(74)90110-6.
  2. ^ Bishop, D.T.; Cannings, C. (1978). "A generalized war of attrition". Journal of Theoretical Biology. 70 (1): 85–124. doi:10.1016/0022-5193(78)90304-1. PMID 564432.
  3. ^ Luce, R. D.; Raiffa, H. (1957). Games and Decisions: Introduction and Critical Survey (Paperback reprint ed.). New York: Wiley. MR 0087572.
  4. ^ a b Levin, Jonathan. "Wars of Attrition" (PDF).
  5. ^ Drew Fudenberg; Jean Tirole (1991). Game Theory. MIT Press. ISBN 978-0-262-06141-4.
  6. ^ Wildrick Thomas, Matthew (2021-03-22). "Nonlinear War of Attrition with Complete Information". Matthew Wildrick Thomas's Blog. Retrieved 2021-03-22.
  7. ^ Prestwich, Ken. "A Mixed ESS Solution to the War of Attrition".
  8. ^ Chatterjee, Krishnendu; Reiter, Johannes G.; Nowak, Martin A. (2012). "Evolutionary dynamics of biological auctions". Theoretical Population Biology. 81: 69–80. doi:10.1016/j.tpb.2011.11.003. PMC 3279759. PMID 22120126.