Introduction to Game Theory
Introduction
Chaikal Nuryakin
Economic theory
• Economic theory tries to predict or explain economic phenomena
using model
• Economic model is an abstraction of the real world
• Model sometimes very simplistic
• Taking only “the essentials”
• Remove the complexities
• In micro, we dealing with individual agents (consumers and
producers) on how they make their decision based on their own self
interest.
Economic Phenomenon
• Market equilibrium
• Demand and supply
• Perfect competition
• Could not explain the whole process
• Especially when there is a strategic inter-dependence
• In macroeconomics, we ”ignore” individual dynamics or assume there
is a representative agent.
Game Theory
• von Neumann and Morgenstern
• “We need essentially new mathematical theory to solve variety of problems
in social sciences.”
• Theory of Games and Economic Behavior (1944)
Strategic Thinking
• Example: US vs. China
• US’s (optimal) action depends on how US predicts the
China’s action.
• China’s action depends on how China predicts the
US’s action.
• US’s action depends on how US predicts how China
predicts the US’s action.
• US’s action depends on how US predicts how China
predicts how US predicts the China’s action.
• and so on… (this is called “infinite regress”)
Game Theory
• Game theory can solve the problem of strategic inter-dependence by
pinning down how to predict other players’ action.
• Therefore, game theory
• Provides us tools for analyzing important economic phenomena beyond
market economy (with perfect competition).
• Enables us to compare different resource allocation mechanisms.
vNM
• Every social problem can be formulated to a game
• Game consists of three elements:
• Players: relevant agents i=1,2,…,N
• i’s Strategy: possible choice of actions
• i’s Payoff: utility for each possible action profile
• vNM fails to develop a general solution concept of the game
John Nash
• John Nash develop a solution concept:
• In (Nash) equilibrium, no one can benefit if she unilaterally changes her
action.
• The solution always exists.
• John Harsanyi and Reinhard Selten significantly extended Nash
equilibrium.
• Triggered a thousands of applications of game theory.
Impact of Nash
• “Soon after Nash’s work, game-theoretic models began to be used in
economic theory and political science, and psychologists began
studying how human subjects behave in experimental games. In the
1970s game theory was first used as a tool in evolutionary biology.
Subsequently, game-theoretic methods have come to dominate
microeconomic theory and are used also in many other fields of
economics and a wide range of other social and behavioral sciences.”
(from an introduction to Game Theory (Osborne, 2004), page 2)
Two Frameworks
• Non-cooperative Game Theory
• examine individual decision making in strategic settings.
• assume a person decides her action on her own.
• does NOT rule out cooperative behaviors.
• Cooperative Game Theory
• examine group decision making in strategic settings.
• assume players can agree on their joint action, or can make
binding contracts.
• simplifies strategic analysis by NOT modeling the negotiation
process explicitly.
• The two tools are complements to one another, but this
lecture focuses mainly on Non-cooperative games.
Timing and Information
Complete Incomplete
Information Information
Static Nash Equilibrium (NE) Bayesian NE (BNE)
Dynamic Subgame Perfect Perfect Bayesian
Equilibrium (SPNE) Equilibrium
Games in two forms
• Static games
Analyses in a normal form
• Dynamic games
Mostly analyze in an extensive-form
Static Games
13
• We consider static situations in which each player
simultaneously and independently chooses a strategy,
and the combination of strategies determines a
payoff for each player.
• The players need not literally act simultaneously.
• Each chooses her own action without knowing others’
choices.
• We will discuss it more formally later
Prisoner’s Dilemma
• Two suspects are charged with a joint crime, and are held separately
by the police.
• Each prisoner is told the following (assume that a plea bargain is
allowed):
• If both confess, each receives 2 years imprisonment.
• If neither confesses, both receive 1 year.
• If one confesses and the other one does not, the former will be set free
immediately (0 payoff) and the latter receives 4 years.
Bi-Matrices
• Any two players game (with finite number of strategies) can be
expressed as a bi-matrix, called payoff bi-matrix or payoff matrix.
• The payoffs to the two players when a particular pair of strategies is chosen
are given in the appropriate cell.
• The payoff to the row player (player 1) is given first, followed by the payoff to
the column player (player 2).
Prisoners Dilemma
Player 2
NC C Strategic
Player 1
actions
NC -1 , -1 -4 , 0
Pay off:
C 0 , -4 -2 , -2 First pay-
off is for
player 1
• Are the elements of the game complete?
• How to solve?
Remarks
• Playing “Confess” is optimal no matter how the opponent takes
“Confess” or “Silent.”
• “Confess” is an optimal (dominant) strategy.
• Combination of dominant strategies is Nash equilibrium.
• There are many games where no dominant strategy exists.
• Individually best decision ≠ Socially efficient outcome
• Optimality for individuals does not necessary imply optimality (Pareto
efficiency) for a group or society.
Review
• A Nash equilibrium is not necessary Pareto efficient.
• Example: Prisoner’s Dilemma
• There can be multiple Nash equilibria.
• Example: Coordination game
• One equilibrium can be less efficient than (Pareto dominated by) the other
equilibrium.
• Called “coordination failure.”
Prisoners’ Dilemma
• N = {1,2}
• Si = {C,NC}, i = 1,2 P2
NC C
P1
NC -1 , -1 -4 , 0
C 0 , -4 -2 , -2
Hawk-Dove: Chicken Games
P2
D H
P1
D 3,3 1,5
H 5,1 0,0
N(HD) = {?}
Battle of Sexes
P2
B S
P1
B 2,1 0,0
S 0, 0 1,2
N(BS) = {?}
Stag Hunt
P2
S H
P1
S 2,2 0, 1
H 1,0 1, 1
N(SH) = {?}
Mixed Strategy: Matching Pennies
• Players may randomize over their pure strategies.
P2
H T
P1
H 1 , -1 -1 , 1
T -1 , 1 1 ,- 1
N(MP) = {?}
Think carefully
• Is there any a dominant strategy?
P2
L R
P1
U 10 , 1 0,4
M 4,2 4,3
D 0,5 10 , 2
Reference
• Robert Gibbons, Game Theory for Applied Economics, 1992
• [Link]
• [Link]