Strategic Game Theory -- Glossary
This is a glossary of introductory game-theory terms, roughly in the order in which they were used first in class.
- game: an interaction between (or among) mutually aware players
-
simultaneous moves:
players move together, in ignorance of the others' moves
Each player must try to reason what his opponent will do now, knowing that she will be asking the same question herself, and so on. -
sequential moves:
players do not move together
Each player must think: If I do this, how will my opponents react? - zero-sum (or constant-sum) game: one player's winnings are the others' losses, so the net gain is zero across all players
- positive-sum (or non-zero-sum or variable-sum) game: players have some common interests; not constant-sum, which means that win-win or lose-lose is possible in two-person games
- cooperative game: when joint-action agreements, pre-game contracts, etc. are enforceable
- non-cooperative game: when agreements are not enforceable (although players may still have common goals, such as the Battle of the Sexes)
-
strategies:
simply the choices available to the players
In a once-off simultaneous game, simply the action taken on that single occasion. With sequential moves, a strategy could be "If he chooses X, then I'll choose B, but if he chooses Y, then I'll choose A" -- a complete plan of action. - outcome: the consequence for a player of a specific combination of all players' strategies
-
payoff:
the number (ordinal or cardinal) attached to an outcome
Reflects all that is important to a player about the game. For example: profits, market share, envy of rivals' positions, etc. -
expected payoff:
the weighted average of all possible outcomes, where each weight is the
probability of that outcome's occurring
The payoffs must be cardinal, not ordinal, in this case. - rational behaviour: players are perfect calculators and flawless followers of their best strategies
- equilibrium: each player is using the strategy that is his best response to the strategies chosen by the other players
So strategic games are distinguished from individual decision making by the presence of significant interactions among the players. Games can be classified according to a variety of categories, including the timing of the play, the common or conflicting interests of the players, the number of times an interaction occurs, the amount of information available to the players, the type of rules, and the feasibility of coordinated action.
Players have strategies that lead to different outcomes with different associated payoffs. Payoffs incorporate everything that is important to a player about a game, and are calculated using probabilistic averages or expected values if outcomes are random or involve some risk. Rationality, or consistent, behaviour is assumed of all players, who must also be aware of all of the relevant rules of conduct. Equilibrium arises when all players use strategies that are best responses to others' strategies; some classes of games allow learning from experience and the study of dynamic movements towards equilibrium.
-
payoff (or game) matrix (or table):
for two players, an m by n table, where one player has m strategies and the
other has n strategies; each cell within the table lists the payoffs to all
players arising from the associated combination of strategies
Also called the normal form or strategic form of the game. - Nash equilibrium: an equilibrium in which each player's action is a best response to the actions of the other players
- pure strategies: specify non-random courses of action for players: no uncertainty
- mixed strategies: specify that an action will be chosen randomly from a set of pure strategies with specific probabilities
- strictly (or strongly) dominant strategy: outperforms (in its payoffs) all other strategies, no matter what any opposing players do
- weakly dominant strategy: at least as good (in its payoffs) as all other strategies, no matter what any opposing players do
- D & N's Rule 2: If you have a dominant strategy, then use it
-
dominated strategy:
no combination of others' strategies makes this the best
When only two strategies, if one is dominant, the other must be dominated. -
iterated (or successive) elimination of dominated strategies:
a method of analysing the game by successively eliminating strategies that
will never be used
After one of player A's moves has been eliminated as dominated, a move of player B's may now have become dominated, etc.
D & N's Rule 3: Eliminate dominated strategies from consideration -
arrow method:
for each player in turn, use arrows to indicate the best response to each of
the combination of her opponents' actions
Helps to identify Nash equilibria, or their absence.
D & N's Rule 4: Look for an equilibrium, a pair of strategies in which each player's action is the best response to the other's -
efficient combination:
of strategies occurs when there is no other other combination of all players'
strategies which makes all
players better, when there is no other combination which each would prefer
Thus, in the Prisoner's Dilemma, {Defect, Defect} is the Nash equilibrium, but it is inefficient, since each player would prefer {C, C}. Of course, the essence of the dilemma is that neither player can get from {D, D} to {C, C} by herself.
Note: it is wrong to add up the players' payoffs to determine efficiency or not.
-
game tree (or extensive form of the game):
joint decision tree for all the players in the game
Illustrates all of the possible actions that can be taken by all of the players, as well as including all possible outcomes and payoffs. Made up of nodes (initial, decision, and terminal) and branches. -
rollback (or backwards induction):
looking forward and reasoning backwards
D & N's Rule 1: Look forward and reason backwards - rollback (or backwards induction) equilibrium: the equilibrium outcome, after rollback, described by the set of strategies that lead to it
-
first-mover advantage:
when the first-moving player would do better than she would if second
For example, Chicken! if sequential. -
second-mover advantage:
when being able to react to the first mover would be beneficial
For example, Scissors/Paper/Rock if sequential.
- strategic moves: manipulate the rules of the game to a player's advantage
- There are three types of strategic moves: commitments, threats, and promises.
- Only a credible strategic move will have the desired effect.
- To move first, one's action must be observable to the other players, and irreversible.
-
a commitment:
P1 states (observed and irreversibly): "In the game to follow, I shall make a particular move, X."
If credible, this statement in effect changes the order of the game so that
P1
moves first with X, and then P2 follows.
Commitment is a simple seizing of the first-mover advantage when it exists. It is an unconditional strategic move. -
a response rule:
P1 states: "In the game to follow, if you choose Y, I shall do A; if you
choose Z, I shall do B, ..."
P1's move is conditional on P2's move, if he is able to wait and see what
P2's move is.
It is a conditional strategic move; in effect, seizing of the second-mover advantage when it exists. - deterrent moves: to stop the opponent from doing something
- compellent moves: to induce the opponent to do something
- a threat: committing to an action that hurts the opponent unless she accedes
- a promise: committing to an action that rewards the opponent if she accedes
- brinkmanship: a threat which creates a risk but not a certainty of hurt to the opponent
- salami tactics: defeating a compellent threats by taking small steps, none of which is large enough to trigger the punishment
- reputation: becoming known as a player who carries out threats and delivers on promises can aid in making credible commitments, threats, and promises
Actions taken by players to fix the rules of later play are known as strategic moves. These first moves must be observable and irreversible to be true first moves, and they must be credible if they are to have their desired effect in altering the equilibrium outcome of the game. Commitment is an unconditional first move used to seize a first-mover advantage when one exists. Such a move usually entails committing to a strategy that would not have been one's equilibrium strategy in the original version of the game, so there may exist an incentive to renege later.
Conditional first moves such as threats and promises are response rules designed either to deter rivals' actions and preserve the status quo, or to compel rivals' actions and alter the status quo. Threats carry the possibility of mutual harm but cost nothing if they work; threats that create only the risk of a bad outcome are known as acts of brinkmanship. Promises are costly only to the maker and only if they are successful. Threats can be arbitrarily large, although excessive size compromises credibility, but promises are usually kept just large enough to be effective.
Credibility must be established for any strategic move. There are a number of general principles to consider in making moves credible, and a number of specific devices that can be used to acquire credibility. These generally work either by reducing one's own future freedom to choose or by altering one's own payoffs from future actions. Specific devices of this kind include establishing a reputation, using teamwork, demonstrating apparent irrationality, burning bridges, and making contracts, although the acquiring of credibility is often context-specific. Similar devices exist for countering strategic moves made by rival players.
- repeated play can help sustain cooperation (collusion) of the Prisoner's Dilemma
- end-game behaviour: in the final round defection is dominant; so in the second-last round defection is dominant; so in the third-last round defection is dominant; so etc.
- contingent strategies occur when players adopt strategies that depend on behaviour in previous plays of the (repeated) game
- trigger strategies: play cooperatively so long as your rival does so, but any defection by her will "trigger" a period of punishment (non-cooperative play) in response
- grim trigger strategy: play cooperatively so long as your rival does so, but defect for ever in response to any defection by her
- tit-for-tat: play cooperatively at first, then echo your rival's play in the last round
The Prisoner's Dilemma is probably the most famous game of strategy; each play has a dominant strategy (to Defect), but the equilibrium is worse for all players than when each users her dominated strategy (to Cooperate). The most well known solution to the dilemma is repetition of play. In a finite game of known length, the present value of cooperation is eventually zero and backwards induction yields an equilibrium with no cooperative behaviour (end-game behaviour). With infinite play (or an unknown end date), cooperation can be achieved using an appropriate contingent strategy such as tit-for-tat (TFT) or the grim trigger strategy; in either case, cooperation is possible if the present value of cooperation exceeds the present value of defecting. More generally, the prospect of "no tomorrow" or of short-term relationships leads to increased competition among players.
Experimental evidence suggests that players often cooperate longer than theory might predict.
Tit-for-tat has been observed to be a simple, nice, provocable, and forgiving strategy that performs very well on the average in repeated Prisoner's Dilemmas.
Prisoner's Dilemmas arise in a variety of contexts: policy setting, labour
arbitration, evolutionary biology, product pricing, and environmental
decision-making are some in which the Prisoner's Dilemma can help explain actual
behaviour.
Up
Last Updated 26 April 2000 Robert Marks, bobm@agsm.edu.au