Strategy (game theory)
Encyclopedia
In game theory
, a player's strategy in a game
is a complete plan of action for whatever situation might arise; this fully determines the player's behaviour. A player's strategy will determine the action the player will take at any stage of the game, for every possible history of play up to that stage.
A strategy profile (sometimes called a strategy combination) is a set of strategies for each player which fully specifies all actions in a game. A strategy profile must include one and only one strategy for every player.
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 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.
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)}.
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, even if their strategy set is finite.
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
.)
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 she is said to be playing a mixed strategy, and not a pure strategy.
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.
In 1991, game theorist Ariel Rubinstein
described alternative ways of understanding the concept. The first, due to Harsanyi (1973),
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.
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),
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.
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, a player's strategy in a game
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
is a complete plan of action for whatever situation might arise; this fully determines the player's behaviour. A player's strategy will determine the action the player will take at any stage of the game, for every possible history of play up to that stage.
A strategy profile (sometimes called a strategy combination) is a set of strategies for each player which fully specifies all actions in a game. A strategy profile must include one and only one strategy for every player.
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
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for playing the game, telling a player what to do for every possible situation throughout the game.
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
Rock-paper-scissors
Rock-paper-scissors is a hand game played by two people. The game is also known as roshambo, or another ordering of the three items ....
, each player has the finite strategy set {rock, paper, scissors}.
A strategy set is infinite otherwise. For instance, an auction
Auction
An auction is a process of buying and selling goods or services by offering them up for bid, taking bids, and then selling the item to the highest bidder...
with mandated bid increments may have an infinite number of discrete strategies in the strategy set {$10, $20, $30, ...}. Alternatively, the Cake cutting game
Fair division
Fair division, also known as the cake-cutting problem, is the problem of dividing a resource in such a way that all recipients believe that they have received a fair amount...
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
Robot
A robot is a mechanical or virtual intelligent agent that can perform tasks automatically or with guidance, typically by remote control. In practice a robot is usually an electro-mechanical machine that is guided by computer and electronic programming. Robots can be autonomous, semi-autonomous or...
or agent
Software agent
In computer science, a software agent is a piece of software that acts for a user or other program in a relationship of agency, which derives from the Latin agere : an agreement to act on one's behalf...
on how to play the game. For instance, in the Ultimatum game
Ultimatum game
The ultimatum game is a game often played in economic experiments in which two players interact to decide how to divide a sum of money that is given to them. The first player proposes how to divide the sum between the two players, and the second player can either accept or reject this proposal. ...
, 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
Bayesian game
In game theory, a Bayesian game is one in which information about characteristics of the other players is incomplete. Following John C. Harsanyi's framework, a Bayesian game can be modelled by introducing Nature as a player in a 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
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
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, even if their strategy set is finite.
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
Trembling hand perfect equilibrium
There are two possible ways of extending the definition of trembling hand perfection to extensive form games.* One may interpret the extensive form as being merely a concise description of a normal form game and apply the concepts described above to this normal form game. In the resulting perturbed...
.)
Illustration
Consider the payoff matrix pictured to the right (known as a coordination game
Coordination game
In game theory, coordination games are a class of games with multiple pure strategy Nash equilibria in which players choose the same or corresponding strategies...
). 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 she is said to be playing a mixed strategy, and not a pure strategy.
Significance
In his famous paper, John Forbes NashJohn Forbes Nash
John Forbes Nash, Jr. is an American mathematician whose works in game theory, differential geometry, and partial differential equations have provided insight into the forces that govern chance and events inside complex systems in daily life...
proved that there is an equilibrium
Nash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
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
Matching pennies
Matching pennies is the name for a simple example game used in game theory. It is the two strategy equivalent of Rock, Paper, Scissors. Matching pennies is used primarily to illustrate the concept of mixed strategies and a mixed strategy Nash equilibrium....
. However, many games do have pure strategy Nash equilibria (e.g. the Coordination game
Coordination game
In game theory, coordination games are a class of games with multiple pure strategy Nash equilibria in which players choose the same or corresponding strategies...
, the Prisoner's dilemma
Prisoner's dilemma
The prisoner’s dilemma is a canonical example of a game, analyzed in game theory that shows why two individuals might not cooperate, even if it appears that it is in their best interest to do so. It was originally framed by Merrill Flood and Melvin Dresher working at RAND in 1950. Albert W...
, the Stag hunt
Stag hunt
In game theory, the stag hunt is a game which describes a conflict between safety and social cooperation. Other names for it or its variants include "assurance game", "coordination game", and "trust dilemma". Jean-Jacques Rousseau described a situation in which two individuals go out on a 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". 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.In 1991, game theorist Ariel Rubinstein
Ariel Rubinstein
Ariel Rubinstein is an Israeli economist who works in game theory. He was educated at the Hebrew University of Jerusalem, 1972–1979, in both mathematics and economics...
described alternative ways of understanding the concept. The first, due to Harsanyi (1973),
is called purification
Purification theorem
In game theory, the purification theorem was contributed by Nobel laureate John Harsanyi in 1973. The theorem aims to justify a puzzling aspect of mixed strategy Nash equilibria: that each player is wholly indifferent amongst each of the actions he puts non-zero weight on, yet he mixes them so as...
, 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.
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),
re-interpreted Nash equilibrium as an equilibrium in beliefs, rather than actions. For instance, in Rock-paper-scissors
Rock-paper-scissors
Rock-paper-scissors is a hand game played by two people. The game is also known as roshambo, or another ordering of the three items ....
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.