## 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 playerssimultaneous 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 playerspositive-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 gamescooperative game:when joint-action agreements, pre-game contracts, etc. are enforceablenon-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' strategiespayoff: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 strategiesequilibrium: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

strategiesthat lead to differentoutcomeswith different associatedpayoffs.Payoffs incorporate everything that is important to a player about a game, and are calculated using probabilistic averages orexpected valuesif 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.Equilibriumarises 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, anmbyntable, where one player hasmstrategies and the other hasnstrategies; each cell within the table lists the payoffs to all players arising from the associated combination of strategies

Also called thenormal formorstrategic formof the game.Nash equilibrium:an equilibrium in which each player's action is a best response to the actions of the other playerspure strategies:specify non-random courses of action for players: no uncertaintymixed strategies:specify that an action will be chosen randomly from a set of pure strategies with specific probabilitiesstrictly (or strongly) dominant strategy:outperforms (in its payoffs) all other strategies, no matter what any opposing players doweakly dominant strategy:at least as good (in its payoffs) as all other strategies, no matter what any opposing players doD & N's Rule 2:If you have a dominant strategy, then use itdominated 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 considerationarrow 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'sefficient 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 thePrisoner'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 backwardsrollback (or backwards induction) equilibrium:the equilibrium outcome, after rollback, described by the set of strategies that lead to itfirst-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,andpromises.- Only a
crediblestrategic move will have the desired effect.- To move first, one's action must be
observableto the other players, andirreversible.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.deterrentmoves: to stop the opponent from doing somethingcompellentmoves: to induce the opponent to do somethinga threat:committing to an action that hurts the opponent unless she accedesa promise:committing to an action that rewards the opponent if she accedesbrinkmanship:a threat which creates a risk but not a certainty of hurt to the opponentsalami tactics:defeating a compellent threats by taking small steps, none of which is large enough to trigger the punishmentreputation: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 asstrategic moves.These first moves must beobservableandirreversibleto 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.Commitmentis 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 torenegelater.Conditional first moves such as threats and promises are

response rulesdesigned either todeterrivals' actions and preserve the status quo, or tocompelrivals' actions and alter the status quo.Threatscarry 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 ofbrinkmanship.Promisesare 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.

Credibilitymust 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 areputation,using teamwork, demonstrating apparent irrationality, burning bridges, and makingcontracts,although the acquiring of credibility is often context-specific. Similar devices exist for countering strategic moves made by rival players.

repeated playcan help sustain cooperation (collusion) of the Prisoner's Dilemmaend-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 strategiesoccur when players adopt strategies that depend on behaviour in previous plays of the (repeated) gametrigger 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 responsegrim trigger strategy:play cooperatively so long as your rival does so, but defect for ever in response to any defection by hertit-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 isrepetition of play.In a finite game of known length, thepresent valueof 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 appropriatecontingent strategysuch astit-for-tat (TFT)or thegrim 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 2000Robert Marks, bobm@agsm.edu.au