Game Theory Basics

• Game theory is designed to model

• How rational (payoff-maximizing) ``agents” will behave
• When individual outcomes are determined by collective behavior.
• Rules of a game specify agent payoffs as a function of actions taken by
different agents.
Let’s play the median game
• On the index card, write down
• Your name
• An integer between 0 and 100 (inclusive).

• After we collect all the index cards, the person (or people) whose
selected number is closest to 2/3 of the median of all the numbers
(rounded down) wins a prize.

• E.g., if the numbers are 3, 4, 5, 38, 60, 70, 70, 90, 100
 Prisoner's Dilemma

Prisoner
prison

Confessbetray is bestresponse no matter what

dominates
staysilent
Betray Betray is a dominant strategy

Not a Pareto optimal strategy pair

Gamer ofplayers n
for each player Si setof actions that playerI 8 represents
can take
A strategy profiles s s n si es Vi setgsaeeigesdlstmkg.es

Ui 5 is payoff to playeri when

the players
play strategyprofiles
 esin
8 i i strategyprofile
for all players but i

strictly
 S

Is P l s t t2
ISP 2 So to
it
 Another setting P2P networks
each have ahh that
free reeding try desired by other
is
decision to upload desired
B file or not

benefit of recovery file 3

A cost ofuploading file
not uploading is a dominant strategy

pollution Game n countries

no to legislationto
control
Yes or

Downtoncontrol costs 3 pollutionemissions

each country that pollutes odds cost to all countries
gk aren't
k countries are polluting n I
pollute don'tpollute dominant strategy
Its Icts to pollute
 whether to enter aantain
Startup Game Q Market or not

Startup
for Microsoft
Microsoft f dominates
Entering
out
staying
Therefore startup can safely
assume that Microsoft
will do so
Microsoft stamp
Enter Stay out is a
Nasheguilitium
i.e each player is best respondingto
the other
players plays
si e Si
n
 b is weaklydominated
a
by

ipuilb
andFs
O
www.nfafs i yuiCb5 i

bis strongly dominated

by a if Vs
iaifa.si
uicb.si

deleted only
caveat
only good predicting dominated
strongly
otherwise retunigus strategies
 deepens

Back to the median game

• On the index card, write down
• Your name
• An integer between 0 and 100 (inclusive).
• After we collect all the index cards, the
person (or people) whose selected
number is closest to 2/3 of the median
of all the numbers (rounded down)
wins a prize.

most median Yzmed 66

 Coordination Game

Bob

c
Hia f G
Network coordination games
each node is
person
achonset useheappornot

kw 2
l
ky
OP.sn
n
O
fiIfYSITE
dgsheEitaEog

O's all around

all used

network cascade
ProgProji T W As Qu Ssi
Nys gratify neo ueu

maffine bsmynofrgy

us news highest quality

synergist highest synergy
holist highest quality synergy
random
 Parking Game

Inspector

i
s

loci p z p Ga p 9 I9
Effect inspect 0
p 344 p Fete
4 log aoa g
P sp
l p p legalbetterthan illegal
0
loci p p dtp log 90kg
p p 90 loog
45 is a Nasihnf9mixedshatg.es 9
Patent o alwin rob al wihnprbtg mspeetargjnspezf.io
 Xi G Probthat
playeri plays
s
strategy

mixedstrategy
play Xj
payef utilityof players
Expected
JPY9
when he plays s
 Nash
This game has 2pm equilibria
also has a mixed NE
It
where each player parties
home
with
prob's b stays
ofprob 42

sp
I II
lowerthan
410 2 p I exp payoff L both
pneeg
 Summary so far
• A Nash equilibrium is a set of stable (possibly mixed) strategies.
• Stable means that no player has an incentive to deviate given what the
other players are doing.
• Pure equilibrium: there may be none, unique or multiple. Can be identified
with “best response diagrams”.
• A joint mixed strategy for n players:
• A probability distribution for each player (possibly different)
• It is an equilibrium if
• For each player, their distribution is a best response to the others.
• Only consider unilateral deviations.
• Everyone knows all the distributions (but not the outcomes of the coin flips).
• Nash’s famous theorem: every game has a mixed strategy equilibrium.
Issues
• Does not suggest how players might choose between different
equilibria
• Does not suggest how players might learn to play equilibrium.
• Does not allow for bargains, side payments, threats, collusions, “pre-
play” communication.

• Computing Nash equilibria for large games is computationally

difficult.
Other issues
• Relies on assumptions that might be violated in the real world
• Rationality is common knowledge.
• Agents are computationally unbounded.
• Agents have full information about other players, payoffs, etc.
 Zero-sum games are
payopgain
Penalty kicks grow player
Goalie Kicher says
suppose
wer Luh pnb p R
it loss ofGabeygoes

foiled tpfo.seP
E gosh
20,9 Q4p
o.ee 0.9 0.48

InpoxmmfEIyE7sr p
 kicker goes first
0.2ps0.8 goalie goesugh Suppose kicker
0.9 must announce p
pso.scp
0.2
gained.gs Tuat
Feast is kicker's best
aap 0.8 0.9 0.410 for
I o 6p al choice P
Ete p p

kick left af prob f

Choosing p f Kick right 4 prob Z
she
maximizes Kickers expected
first i.e
gain is the p that
if
has to announce
maximizes min
p 0.811 p
0.5
pto 9 Kp
kicker plays she guarantees herself
If p
Eg Y
an expected payoff of Latos ft E
Goalie first
goes
I o.iq to 8 kickergoesnght Supposes kicker
0
99 0.81191 bestrespond
gets to
08
kickergoesleft to Goalies mixed
1 asg
µ
0
59 1 9
strategy q dive
left C g dive
a
g www.qq.my yes
3
g 9g choice for q
3
0.025
with prob and
choosing GE
dire left prob 73
dive right by he has to
minimizes goalies expected loss if
announce first i.e minimizes
moxfoagto.SC g 0.5Gt 9
a
Goalie goes first he can
guarantee himself
If
loss of at most 0.9 zt08Zz V2
 payoff the kicker
can guarantee himself
Y exp he has to go first
if kicker can himself
V2 exp payoff the second
guarantee
he can
go he has
if loss he can guarantee if
hp goalie first
V
go E Vy

Viva
Summary – zero-sum games
• Zero-sum games have a “value”.
• Optimal strategies are well-defined.
• Maximizer can guarantee a gain of at least V by playing p*
• Minimizer can guarantee a loss of at most V by playing q*.
• This is a Nash equilibrium.
• In contrast to general-sum games, optimal strategies in zero-sum
games can be computed efficiently (using linear programming).
 1500 penaltykicks

0.423 0.5577 actual observedfractions

942 0.58 optimal strategies
in
game

0.4 0.38
0.6 0.62
Extensive Form Games
White
nd

HID
Mutual Assured Destination A aggressive B benign

a
gampy
 Centipede

so
far g perfect info
games
 vs startup
LangeCompany

startup announces a
technology that
threatens

big company
is prob that BC
Big
company
together
canpullproduct
coup
Startup
Repealed Prisoners Dilemma

Infinitely repeated game with discounting

IIcountdBp
ayff thefts PTI
continues
 I p g
Gnmtriggeri Cooperate until around
which your opponent defects then
in
from then
on
defect
finthgger Guthger
NE
Tiffortat DtfortatJ

Grim Trigger
I

8ptt2 P vs 6
j
PJ
8ptt2 pJ 2ptL4 pi YE
Gj Pt
when

i a 213
p posts
 Cooperate in round 1
Titfortat round k I
mercy what opponentplayed
play your K l
in round