Strategy (game theory)

In game theory, player's strategy is any of the options he or she can choose in a setting where the outcome depends not only on his own actions but on the action of others.^[1] A player's strategy will determine the action the player will take at any stage of the game.

The strategy concept is sometimes (wrongly) confused with that of a move. A move is an action taken by a player at some point during the play of a game (e.g., in chess, moving white's Bishop a2 to b3). A strategy on the other hand is a complete algorithm for playing the game, telling a player what to do for every possible situation throughout the game.

A strategy profile (sometimes called a strategy combination) is a set of strategies for all players which fully specifies all actions in a game. A strategy profile must include one and only one strategy for every player.

Strategy set

A player's strategy set defines what strategies are available for them to play.

A player has a finite strategy set if they have a number of discrete strategies available to them. For instance, in a single game of rock-paper-scissors, each player has the finite strategy set {rock, paper, scissors}.

A strategy set is infinite otherwise. For instance, an auction with mandated bid increments may have an infinite number of discrete strategies in the strategy set {$10, $20, $30, ...}. Alternatively, the cake cutting game has a bounded continuum of strategies in the strategy set {Cut anywhere between zero percent and 100 percent of the cake}.

In a dynamic game, the strategy set consists of the possible rules a player could give to a robot or agent on how to play the game. For instance, in the ultimatum game, the strategy set for the second player would consist of every possible rule for which offers to accept and which to reject.

In a Bayesian game, the strategy set is similar to that in a dynamic game. It consists of rules for what action to take for any possible private information.

Choosing a strategy set

In applied game theory, the definition of the strategy sets is an important part of the art of making a game simultaneously solvable and meaningful. The game theorist can use knowledge of the overall problem to limit the strategy spaces, and ease the solution.

For instance, strictly speaking in the Ultimatum game a player can have strategies such as: Reject offers of ($1, $3, $5, ..., $19), accept offers of ($0, $2, $4, ..., $20). Including all such strategies makes for a very large strategy space and a somewhat difficult problem. A game theorist might instead believe they can limit the strategy set to: {Reject any offer ≤ x, accept any offer > x; for x in ($0, $1, $2, ..., $20)}.

Pure and mixed strategies

A pure strategy provides a complete definition of how a player will play a game. In particular, it determines the move a player will make for any situation he or she could face. A player's strategy set is the set of pure strategies available to that player.

A mixed strategy is an assignment of a probability to each pure strategy. This allows for a player to randomly select a pure strategy. Since probabilities are continuous, there are infinitely many mixed strategies available to a player.

Of course, one can regard a pure strategy as a degenerate case of a mixed strategy, in which that particular pure strategy is selected with probability 1 and every other strategy with probability 0.

A totally mixed strategy is a mixed strategy in which the player assigns a strictly positive probability to every pure strategy. (Totally mixed strategies are important for equilibrium refinement such as trembling hand perfect equilibrium.)

Mixed strategy

Illustration

	A	B
A	1, 1	0, 0
B	0, 0	1, 1
Pure coordination game

Consider the payoff matrix pictured to the right (known as a coordination game). Here one player chooses the row and the other chooses a column. The row player receives the first payoff, the column player the second. If row opts to play A with probability 1 (i.e. play A for sure), then he is said to be playing a pure strategy. If column opts to flip a coin and play A if the coin lands heads and B if the coin lands tails, then he is said to be playing a mixed strategy, and not a pure strategy.

Significance

In his famous paper, John Forbes Nash proved that there is an equilibrium for every finite game. One can divide Nash equilibria into two types. Pure strategy Nash equilibria are Nash equilibria where all players are playing pure strategies. Mixed strategy Nash equilibria are equilibria where at least one player is playing a mixed strategy. While Nash proved that every finite game has a Nash equilibrium, not all have pure strategy Nash equilibria. For an example of a game that does not have a Nash equilibrium in pure strategies, see Matching pennies. However, many games do have pure strategy Nash equilibria (e.g. the Coordination game, the Prisoner's dilemma, the Stag hunt). Further, games can have both pure strategy and mixed strategy equilibria.

A disputed meaning

During the 1980s, the concept of mixed strategies came under heavy fire for being "intuitively problematic".^[2] Randomization, central in mixed strategies, lacks behavioral support. Seldom do people make their choices following a lottery. This behavioral problem is compounded by the cognitive difficulty that people are unable to generate random outcomes without the aid of a random or pseudo-random generator.^[2]

In 1991,^[3] game theorist Ariel Rubinstein described alternative ways of understanding the concept. The first, due to Harsanyi (1973), ^[4] is called purification, and supposes that the mixed strategies interpretation merely reflects our lack of knowledge of the players' information and decision-making process. Apparently random choices are then seen as consequences of non-specified, payoff-irrelevant exogeneous factors. However, it is unsatisfying to have results that hang on unspecified factors.^[3]

A second interpretation imagines the game players standing for a large population of agents. Each of the agents chooses a pure strategy, and the payoff depends on the fraction of agents choosing each strategy. The mixed strategy hence represents the distribution of pure strategies chosen by each population. However, this does not provide any justification for the case when players are individual agents.

Later, Aumann and Brandenburger (1995), ^[5] re-interpreted Nash equilibrium as an equilibrium in beliefs, rather than actions. For instance, in rock-paper-scissors an equilibrium in beliefs would have each player believing the other was equally likely to play each strategy. This interpretation weakens the predictive power of Nash equilibrium, however, since it is possible in such an equilibrium for each player to actually play a pure strategy of Rock.

Ever since, game theorists' attitude towards mixed strategies-based results have been ambivalent. Mixed strategies are still widely used for their capacity to provide Nash equilibria in games where no equilibrium in pure strategies exists, but the model does not specify why and how players randomize their decisions.

Behavior strategy

While a mixed strategy assigns a probability distribution over pure strategies, a behavior strategy assigns at each information set a probability distribution over the set of possible actions. While the two concepts are very closely related in the context of normal form games, they have very different implications for extensive form games. Roughly, a mixed strategy randomly chooses a deterministic path through the game tree, while a behavior strategy can be seen as a stochastic path.

The relationship between mixed and behavior strategies is the subject of Kuhn's theorem. The result establishes that in any finite extensive-form game with perfect recall, for any player and any mixed strategy, there exists a behavior strategy that, against all profiles of strategies (of other players), induces the same distribution over terminal nodes as the mixed strategy does. The converse is also true.

A famous example of why perfect recall is required for the equivalence is given by Piccione and Rubinstein (1997) with their Absent-Minded Driver game.

References

↑ Ben Polak Game Theory: Lecture 1 Transcript ECON 159, 5 September 2007, Open Yale Courses.
1 2 Aumann, R. (1985). "What is Game Theory Trying to accomplish?" (PDF). In Arrow, K.; Honkapohja, S. Frontiers of Economics. Oxford: Basil Blackwell. pp. 909–924.
1 2 Rubinstein, A. (1991). "Comments on the interpretation of Game Theory". Econometrica 59 (4): 909–924. JSTOR 2938166.
↑ Harsanyi, John (1973), "Games with randomly disturbed payoffs: a new rationale for mixed-strategy equilibrium points", Int. J. Game Theory 2: 1–23, doi:10.1007/BF01737554
↑ Aumann, Robert; Brandenburger, Adam (1995), "Epistemic Conditions for Nash Equilibrium", Econometrica (The Econometric Society) 63 (5): 1161–1180, doi:10.2307/2171725, JSTOR 2171725

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 Perfect Bayesian Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency 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 Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global games Strictly determined 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 Screening 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 Tragedy of the commons Tyranny of small decisions

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