War of attrition (game)

Last updated

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).

Contents

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:

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

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.

See also

Related Research Articles

An evolutionarily stable strategy (ESS) is a strategy which, if adopted by a population in a given environment, is impenetrable, meaning that it cannot be invaded by any alternative strategy that are initially rare. It is relevant in game theory, behavioural ecology, and evolutionary psychology. An ESS is an equilibrium refinement of the Nash equilibrium. It is a Nash equilibrium that is "evolutionarily" stable: once it is fixed in a population, natural selection alone is sufficient to prevent alternative (mutant) strategies from invading successfully. The theory is not intended to deal with the possibility of gross external changes to the environment that bring new selective forces to bear.

Game theory The study of mathematical models of strategic interaction between rational decision-makers

Game theory is the study of mathematical models of strategic interaction among rational decision-makers. It has applications in all fields of social science, as well as in logic, systems science and computer science. Originally, it addressed zero-sum games, in which each participant's gains or losses are exactly balanced by those of the other participants. Today, game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers.

Minimax is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case scenario. When dealing with gains, it is referred to as "maximin"—to maximize the minimum gain. Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision-making in the presence of uncertainty.

The prisoner's dilemma is a standard example of a game analyzed in game theory that shows why two completely rational individuals might not cooperate, even if it appears that it is in their best interests to do so. It was originally framed by Merrill Flood and Melvin Dresher while working at RAND in 1950. Albert W. Tucker formalized the game with prison sentence rewards and named it "prisoner's dilemma", presenting it as follows:

Two members of a criminal gang are arrested and imprisoned. Each prisoner is in solitary confinement with no means of communicating with the other. The prosecutors lack sufficient evidence to convict the pair on the principal charge, but they have enough to convict both on a lesser charge. Simultaneously, the prosecutors offer each prisoner a bargain. Each prisoner is given the opportunity either to betray the other by testifying that the other committed the crime, or to cooperate with the other by remaining silent. The possible outcomes are:

The game of chicken, also known as the hawk–dove game or snowdrift game, is a model of conflict for two players in game theory. The principle of the game is that while the outcome is ideal for one player to yield, but the individuals try to avoid it out of pride for not wanting to look like a 'chicken'. So each player taunts the other to increase the risk of shame in yielding. However, when one player yields, the conflict is avoided, and the game is for the most part over.

Evolutionary game theory (EGT) is the application of game theory to evolving populations in biology. It defines a framework of contests, strategies, and analytics into which Darwinian competition can be modelled. It originated in 1973 with John Maynard Smith and George R. Price's formalisation of contests, analysed as strategies, and the mathematical criteria that can be used to predict the results of competing strategies.

A Vickrey auction 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.

Solution concept formal rule for predicting how a strategic game will be played

In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium.

In game theory, normal form is a description of a game. Unlike extensive form, normal-form representations are not graphical per se, but rather represent the game by way of a matrix. While this approach can be of greater use in identifying strictly dominated strategies and Nash equilibria, some information is lost as compared to extensive-form representations. The normal-form representation of a game includes all perceptible and conceivable strategies, and their corresponding payoffs, for each player.

"A population is said to be in an evolutionarily stable state if its genetic composition is restored by selection after a disturbance, provided the disturbance is not too large. Such a population can be genetically monomorphic or polymorphic." —Maynard Smith (1982).

The Bishop–Cannings theorem is a theorem in evolutionary game theory. It states that (i) all members of a mixed evolutionarily stable strategy (ESS) have the same payoff, and (ii) that none of these can also be a pure ESS. The usefulness of the results comes from the fact that they can be used to directly find ESSes algebraically, rather than simulating the game and solving it by iteration.

The dollar auction is a non-zero sum sequential game designed 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 completely on a sequence of apparently rational choices made throughout the game.

A double auction is a process of buying and selling goods with multiple sellers and multiple buyers. Potential buyers submit their bids and potential sellers submit their ask prices to the market institution, and then the market institution chooses some price p that clears the market: all the sellers who asked less than p sell and all buyers who bid more than p buy at this price p. Buyers and sellers that bid or ask for exactly p are also included. A common example of a double auction is stock exchange.

Auction theory is an applied branch of economics which deals with how people act in auction markets and researches the properties of auction markets. There are many possible designs for an auction and typical issues studied by auction theorists include the efficiency of a given auction design, optimal and equilibrium bidding strategies, and revenue comparison. Auction theory is also used as a tool to inform the design of real-world auctions; most notably auctions for the privatization of public-sector companies or the sale of licenses for use of the electromagnetic spectrum.

The revelation principle is a fundamental principle in mechanism design. It states that if a social choice function can be implemented by an arbitrary mechanism, then the same function can be implemented by an incentive-compatible-direct-mechanism with the same equilibrium outcome (payoffs).

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 they submitted.

Risk dominance and payoff dominance are two related refinements of the Nash equilibrium (NE) solution concept in game theory, defined by John Harsanyi and Reinhard Selten. A Nash equilibrium is considered payoff dominant if it is Pareto superior to all other Nash equilibria in the game. When faced with a choice among equilibria, all players would agree on the payoff dominant equilibrium since it offers to each player at least as much payoff as the other Nash equilibria. Conversely, a Nash equilibrium is considered risk dominant if it has the largest basin of attraction. This implies that the more uncertainty players have about the actions of the other player(s), the more likely they will choose the strategy corresponding to it.

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.

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.

In auction theory, jump bidding is the practice of increasing the current price in an English auction, substantially more than the minimal allowed amount.

References

  1. Maynard Smith, J. (1974) Theory of games and the evolution of animal conflicts. Journal of Theoretical Biology 47: 209-221.
  2. Bishop, D.T. & Cannings, C. (1978) A generalized war of attrition. Journal of Theoretical Biology 70: 85-124.
  3. K. Chatterjee, J.G. Reiter, M.A. Nowak: "Evolutionary dynamics of biological auctions". Theoretical Population Biology 81 (2012), 69 - 80

Sources