Essay About Game Theory And Extensive Games

Game Theory
Essay title: 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.
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.
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.
Mixed strategy
A mixed strategy is an active randomization, with given probabilities, that determines the
players 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 players attitude towards
risk.
Perfect information
A game has perfect information when at any point in time only one player makes a move,