Game Theory

Game Theoryƒ

Theodore L. Turocy

Texas A&M University

Bernhard von Stengel

London School of Economics

CDAM Research Report LSE-CDAM-2001-09

October 8, 2001

Contents

1 What is game theory? 4

2 Definitions of games 6

3 Dominance 8

4 Nash equilibrium 12

5 Mixed strategies 17

6 Extensive games with perfect information 22

7 Extensive games with imperfect information 29

8 Zero-sum games and computation 33

9 Bidding in auctions 34

10 Further reading 38

ƒThis is the draft of an introductory survey of game theory, prepared for the Encyclopedia of Information

Systems, Academic Press, to appear in 2002.

1

Glossary

Backward induction

Backward induction is a technique to solve a game of perfect information. It first considers

the moves that are the last in the game, and determines the best move for the player

in each case. Then, taking these as given future actions, it proceeds backwards in time,

again determining the best move for the respective player, until the beginning of the game

is reached.

Common knowledge

A fact is common knowledge if all players know it, and know that they all know it, and

so on. The structure of the game is often assumed to be common knowledge among the

players.

Dominating strategy

A strategy dominates another strategy of a player if it always gives a better payoff to

that player, regardless of what the other players are doing. It weakly dominates the other

strategy if it is always at least as good.

Extensive game

An extensive game (or extensive form game) describes with a tree how a game is played.

It depicts the order in which players make moves, and the information each player has at

each decision point.

Game

A game is a formal description of a strategic situation.

Game theory

Game theory is the formal study of decision-making where several players must make

choices that potentially affect the interests of the other players.

2

Mixed strategy

A mixed strategy is an active randomization, with given probabilities, that determines the

player's decision. As a special case, a mixed strategy can be the deterministic choice of

one of the given pure strategies.

Nash equilibrium

A Nash equilibrium, also called strategic equilibrium, is a list of strategies, one for each

player, which has the property that no player can unilaterally change his strategy and get

a better payoff.

Payoff

A payoff is a number, also called utility, that reflects the desirability of an outcome to a

player, for whatever reason. When the outcome is random, payoffs are usually weighted

with their probabilities. The expected payoff incorporates the player's attitude towards

risk.

Perfect information

A game has perfect information when at any point in time only one player makes a move,

and knows all the actions that have been made until then.

Player

A player is an agent who makes decisions in a game.

Rationality

A player is said to be rational if he seeks to play in a manner which maximizes his own

payoff. It is often assumed that the rationality of all players is common knowledge.

Strategic form

A game in strategic form, also called normal form, is a compact representation of a game

in which players simultaneously choose their strategies. The resulting payoffs are presented

in a table with a cell for each strategy combination.

3

Strategy

In a game in strategic form, a strategy is one of the given possible actions of a player. In

an extensive game, a strategy is a complete plan of choices, one for each decision point

of the player.

Zero-sum game

A game is said to be zero-sum if for any outcome, the sum of the payoffs to all players is

zero. In a two-player zero-sum game, one player's gain is the other player's loss, so their

interests are diametrically opposed.

1 What is game theory?

Game theory is the formal study of conflict and cooperation. Game theoretic concepts

apply whenever the actions of several agents are interdependent. These agents