War of attrition (game) source: en.wikipedia.org/wiki/War_of_attrition_(game)
This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (December 2010) (Learn how and when to remove this template message)
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; a mixed evolutionarily stable strategy (ESS) was determined by Bishop & Cannings. An example is an 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
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 as lose 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"; 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. Also, there is no Nash Equilibrium in pure strategies in this game indicated as follow:
- If there is a lower bidder and a higher bidder, the rational strategy for the lower bidder is to bid zero knowing that it will lose. The higher bidder will bid a value slightly higher and approaches zero in order to maximize its payoff, in which case the lower bidder has the incentive to outbid the higher bidder to win.
- If the two players equally bid, the equalized value of the bid cannot exceed V/2 or the expected payoff for both players will be negative. For any equalized bid less than V/2, either player will have the incentive to bid higher.
With the two cases mentioned above, it can be proved that there is no Nash Equilibrium in pure strategies for the game since either player has the incentive to change its strategy in any reasonable situation.
Dynamic formulation and evolutionarily stable strategy
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. Its equilibria are not as obvious as the other formulation. The evolutionarily stable strategy is a mixed ESS, in which the probability of persisting for a length of time t is:
The evolutionarily stable strategy below represents the most probable value of a. The value p(t) for a contest with a resource of value V over time t, is the probability that t = a. This strategy does not guarantee the win; rather it is the optimal balance of risk and reward. The outcome of any particular game cannot be predicted as the random factor of the opponent's bid is too unpredictable.
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.
The ESS in popular culture
The evolutionarily stable strategy when playing this game is a probability density of random persistence times which cannot be predicted by the opponent in any particular contest. This result has led to the prediction that threat displays ought not to evolve, and the conclusion that the optimal military strategy is to behave in a completely unpredictable, and therefore insane, manner. Neither of these conclusions appear to be truly quantifiably reasonable applications of the model to realistic conditions.
- Maynard Smith, J. (1974) Theory of games and the evolution of animal conflicts. Journal of Theoretical Biology 47: 209-221.
- Bishop, D.T. & Cannings, C. (1978) A generalized war of attrition. Journal of Theoretical Biology 70: 85-124.
- K. Chatterjee, J.G. Reiter, M.A. Nowak: "Evolutionary dynamics of biological auctions". Theoretical Population Biology 81 (2012), 69 - 80
- Bishop, D.T., Cannings, C. & Maynard Smith, J. (1978) The war of attrition with random rewards. Journal of Theoretical Biology 74:377-389.
- Maynard Smith, J. & Parker, G. A. (1976). The logic of asymmetric contests. Animal Behaviour. 24:159-175.
- Luce,R.D. & Raiffa, H. (1957) "Games and Decisions: Introduction and Critical Survey"(originally published as "A Study of the Behavioral Models Project, Bureau of Applied Social Research") John Wiley & Sons Inc., New York
- Rapaport,Anatol (1966) "Two Person Game Theory" University of Michigan Press, Ann Arbor
- Exposition of the derivation of the ESS - From Ken Prestwich's Game Theory website at College of the Holy Cross