War of attrition (game)

For general use of this term, see War of attrition.

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 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). In Combat sports, an all-out brawl between the two competitors is often called a War of Attrition.

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 game. 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 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 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 $v_{i}>0$ . 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 $v_{i}/2$ 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:

$p(t)={\frac {1}{V}}e^{{(-t/V)}}$

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+ $\delta$ .

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.^[3]

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 to the conclusion in that 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.

References

↑ 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

Sources

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

External links

Exposition of the derivation of the ESS - From Ken Prestwich's Game Theory website at College of the Holy Cross

Topics in game theory

Definitions	Normal-form game Extensive-form game Escalation of commitment Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference

Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Screening game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global games Strictly determined game Potential game

Games	Prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock-paper-scissors Pirate game Dictator game Public goods game Blotto games War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Prisoners and hats puzzle Trust game Princess and monster game Monty Hall problem Rendezvous problem

Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key figures	Albert W. Tucker Amos Tversky Ariel Rubinstein Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey

See also	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons Tyranny of small decisions

This article is issued from Wikipedia - version of the 9/26/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.