Introduction to Game Theory

Bill Chen, [email protected]

Friday, January 18, 2013

(based on work with Dan Loeb and Jerrod

Ankenman)
 What is a game?
A “Game” is a situation in which “players” have choices.
The outcome of the game can be more or less favorable to
each player depending on the interaction of those choices
(and possibly an element of luck).
• Number of Players (1, 2, many)
• Chance in Rules (random, deterministic)
• Information (hidden, common knowledge)
• Order of play (sequential, simultaneous)
• Zero-sum or Cooperative Play

Introduction to Game Theory 2

 Combinatorial Games
Chess, Checkers, Go, Tic-tac-toe, Nim, Dots-
and-Boxes, ...
• 2 players
• Deterministic
• Common knowledge
• Sequential play
• Zero-sum. Win-lose, Draw-draw, Lose-win.

Introduction to Game Theory 3

 Backgammon
• 2 players
• Random (dice)
• Common knowledge
• Sequential play
• Zero-sum. Loser pays winner amount on the
doubling cube (possibly times 2 or 3)

Introduction to Game Theory 4

 Poker
• Could be 2 players (heads-up) or more
• Random (cards)
• Hidden information
• Sequential play
• Usually zero-sum (unless house is taking a
percentage of the pot or in some
tournaments)

Introduction to Game Theory 5

 Bridge
• 2 “players” (actually each is a 2-
person team)
• Random (cards)
• Hidden information. (Even
within a team!)
• Sequential play
• Zero-sum (even when duplicate)

Introduction to Game Theory 6

 Zero-Sum Matrix Games
Odds-Evens, Roshambo
• 2 players
• Deterministic. (Strategies can be random!)
• Common knowledge.
• Simultaneous play.
• Zero-sum

We will begin by studying Zero-sum matrix

games.
Introduction to Game Theory 7
 Solitaire
• 1 player, or 1 player against “nature”
• Random (cards)

Introduction to Game Theory 8

 Voting Systems
Congress & President form coalitions.
Winning coalition (if any) divides US Budget
amongst themselves...
• Many players (100+435+1+1)
• Deterministic?
• Common knowledge. (Wheeling-dealing
behind closed doors, but voting in public.)
• Sequential play.
• “Cooperative play”

Introduction to Game Theory 9

 Stock Market
• Many players (~108, firms like SIG,
Mom&Pop investors, etc.)
• Random (news)
• Hidden information!
• Simultaneous (asynchronous) play.
• Zero-sum (modulo taxes, commissions,
SEC …).
(We will give a couple of examples: 0-sum
and cooperative.)

Introduction to Game Theory 10

 Auctions
Each player can spend money for research to get estimate of
value of oil field. Each player places a sealed bid. High bidder
wins. (Beware of the winner’s curse…)

• 2 or more players
• Random (estimation error, depends on $ spent research)
• Hidden information (research)
• Simultaneous play.
• Not zero-sum.

Introduction to Game Theory 11

 Introduction to Game Theory
0-sum 2-player Games. Multiplayer Games
• Odd-even game • Highway construction
• Cops & Robbers • Cost of Sharing a Secret
• Market-making
Cooperative 2-player Games.
• Prisoner’s Dilemma
• Outbidding
• Chicken / MAD
• Position Dumping

Introduction to Game Theory 12

Zero-Sum Two Player Games
 Zero-sum Two-player Games.
Odd-even game
• Players: Rose Todd vs. Colin Stevens
• Each player simultaneously displays 1
or 2 fingers. Stevens wins $1 if total is
even (both players display same
number of fingers). Todd wins $1 if
total is odd. Odd-Even Game
• Payoffs to Colin shown in table. Colin Stevens
Rose chooses Row and G(x,y) C1 C2
Rose R1 +1 -1
Colin chooses Column.
Todd R2 -1 +1
Introduction to Game Theory 14
 Odd-Even game
Theory of Moves (Steven J. Brams)
• Suppose Colin and Rose both are thinking of
choosing 1.
• Then Rose should switch to 2.
• If she does, then Colin should switch to 2.
• So Rose should switch to 1. Odd-Even Game
• So Colin should switch to 1. Colin Stevens
• We are back we started. G(x,y) C1 C2
There seems to be no Rose R1 +$1 -$1
stable solution! Todd R2 -$1 +$1
Introduction to Game Theory 15
 Nash Equilibrium
• John F. Nash, Nobel Prize 1994 for “pioneering
analysis of equilibria in the theory of non-cooperative
games.”
• Nash’s work extended earlier idea of John Von
Neumann and Oskar Morgenstern.
• A (Nash) Equilibrium is a set of strategies:
One strategy for each player such that no player has an
incentive to unilaterally change his strategy.
• In Odd-Even, Rose & Colin each have 2 possible
“pure” strategies. None of the four possible
combinations is a Nash equilibrium.

Introduction to Game Theory 16

 Odd-Even Game
Mixed Strategies G(x,y)
Colin Stevens
C1 C2
Rose R1 +$1 -$1
• In order to avoid being Todd R2 -$1 +$1
outguessed, choose a
y=100% Col. 1 all the time
random combination y=75%
y=50%
y=25%
of strategies. y=0% Col. 2 all the time

• Rose selects R1, x%

$1.00
$0.80

Expected payoff for Colin

of the time and R2, $0.60
$0.40
(100-x)% of the time. $0.20
$0.00
• Colin chooses C1, y% ($0.20) 100% 50% 0%
($0.40)
of the time. ($0.60)
($0.80)
($1.00)
x% (Rose's mixed strategy)

Introduction to Game Theory 17

 Odd-Even Game
Mixed Strategies G(x,y)
Colin Stevens
C1 C2
Rose R1 +$1 -$1
Todd R2 -$1 +$1

• y<50%, If Colin chooses C1 less y=100% Col. 1 all the time

y=75%
y=50%
than half of the time, Rose may y=25%
y=0% Col. 2 all the time
pick R1 (x=100%) and Colin $1.00
loses on average. $0.80

Expected payoff for Colin

• y>50%, similarly, Rose picks R2 $0.60
$0.40
(x=100%) and Colin loses on $0.20
$0.00
average. ($0.20) 100% 50% 0%
• Setting y=50%, guarantees that ($0.40)
($0.60)
Colin breaks even. ($0.80)
• Similarly x=50% guarantees that ($1.00)
x% (Rose's mixed strategy)
Rose breaks even.
Introduction to Game Theory 18
 Odd-Even Game
Mixed Strategies G(x,y)
Colin Stevens
C1 C2
Rose R1 +$1 -$1
• x=50%, y=50% is a Nash Todd R2 -$1 +$1
equilibrium. Both players break y=100% Col. 1 all the time
y=75%
even. y=50%
y=25%
• If either player unilaterally y=0% Col. 2 all the time
$1.00
changes his strategy, he is not $0.80

Expected payoff for Colin

better off. (In fact, as is usually $0.60

the case, he is indifferent.) $0.40

$0.20
• The symmetry of the solution $0.00
($0.20) 100% 50% 0%
reflects the symmetry of the ($0.40)
game. ($0.60)

• Let’s change the rules so

($0.80)
($1.00)
solution is not so obvious. x% (Rose's mixed strategy)

Introduction to Game Theory 19

 Cop Colin
Cops & Robbers Variant G(x,y) C1 C2
Robber R1 +$1 -$1
• Rose is a sociopathic Robber
Rose R2 -$1 $0
who can try to steal or not (1 or
2). Colin is a Cop who can try to • The game favors Rose since
catch Rose or not (1 or 2). she can guarantee at least $0 by
• If neither does anything, the not stealing. (Row 2).
payoff is zero. If Rose steals
• If Colin catches on to this he
successfully, she gets $1, if
will just not try to catch Rose
Colin catches Rose, he gets $1.
(Col 2) and break even.
• Rose has it in for Colin, so if
Colin tries to catch Rose when • So Rose can try to steal
she is not stealing, Rose gets $1 occasionally, but 1/2 the time is
too much, since then Colin will
• The game is the same as
just try catching her all of the
Odd/Even except the R2/C2
outcome of +$1 is changed to 0
time (Col 1) and break even.
in Rose’s favor.
Introduction to Game Theory 20
 Cop Colin
Cops & Robbers Variant G(x,y) C1 C2
Robber R1 +$1 -$1
• If Colin tries to catch Rose (C1) Rose R2 -$1 $0
with y>1/3, then Rose’s best play
is to not steal (R2) and Colin’s y=100% Col. 1 all the time
expectation will be -y < -1/3. y=66.7%
y=33.3%
• Similarly if Colin tries to catch y=0% Col. 2 all the time
Rose with y<1/3, Rose can just
$1.00
steal and Colin’s expectation will $0.80

Expected payoff for Colin

be y-(1-y) = 2y-1 < -1/3. $0.60
$0.40
• Conversely, Colin can try to $0.20
catch Rose exactly 1/3 of the $0.00
($0.20)
time and guarantee an 100% 67% 33% 0%
($0.40)
expectation of -1/3. ($0.60)
• The optimal solution is Rose ($0.80)
($1.00)
Steals 1/3 of the time and Colin x% (Rose's mixed strategy)

tries to catch her 1/3 of the time.

Introduction to Game Theory 21
 Mike Caro’s AKQ Game
• Game invented by Mike Caro [Card Player, 1995]
• I’m corrupting the legend a bit but… Two cave men
wanted to play poker but cards hadn’t been invented yet.
So then one of them invents the Ace. They really couldn’t
figure out much of a game with it, so then the other one
created the King. They could now shuffle and deal but the
game was uninteresting since there was no point in betting.
They didn’t know what to do until one day one of them got
married and his wife came up with the idea of the Queen.
She has regretted it ever since.

Introduction to Game Theory 22

 Mike Caro’s AKQ Game
• Each player, Raisin’ Rose and Callin’ Colin, antes $1.
• Both players are dealt one hole card from a 3 card-deck which includes an Ace,
King, and Queen. Each player may look at his card but not his opponent’s.
• Raisin’ Rose may bet $1. If Rose checks, there is a showdown and the ordering of
cards is Ace > King > Queen, and the winner gets the pot and nets $1.
• If Rose bets, Colin has a chance to Call or Fold. If Colin folds, Rose wins $1, if
Colin calls there is a showdown with $2 going to the winner.

Actions Rose Colin

Always Bets, will Always Calls, will
Ace
always win if called. always win
Never Bets, will May Call (C1) or
King
never win if called. Fold (C2).
May Bet (R1) or Never Calls, will
Queen
Check (R2). never win.

Introduction to Game Theory 23

 Mike Caro’s AKQ Game
• Rose and Colin both have at most two viable strategies.
• Let R1 be Rose’s strategy of Betting (stealing) with a Queen.
• Let R2 be Rose’s strategy of Checking with a Queen.
• For both R1 and R2, Rose will Bet with an Ace and Check with a King.
• Let C1 be Colin’s strategy of Calling a bet with a King (being the “Table Cop”).
• Let C2 be Colin’s the strategy of Folding a bet with a King.
• For both C1 and C2, Colin will always Call with an Ace and Fold a Queen.
Actions Rose Colin
Always Bets, will Always Calls, will
Ace
always win if called. always win
Never Bets, will May Call (C1) or
King
never win if called. Fold (C2).
Callin' Colin's Expected Value Queen
May Bet (R1) or Never Calls, will
Check (R2). never win.

R's Strategy A A K K Q Q C's Cards Total C's EV

R1 Bet Q 1 2 -2 2 -1 -1 C1 Call K 1 1/6
R2 Check Q 1 1 -2 1 -1 -1 C1 Call K -1 - 1/6
R1 Bet Q 1 2 -1 -1 -1 -1 C2 Fold K -1 - 1/6
R2 Check Q 1 1 -1 1 -1 -1 C2 Fold K 0 0
R's Cards K Q A Q A K C's Strategy
Introduction to Game Theory 24
 Mike Caro’s AKQ Game
AKQ Matrix Form
G(x,y) C1 C2 • Here, we have reduced the game to matrix
form, which is rather interesting since we
R1 1/6 - 1/6
took a sequential play poker game and
R2 - 1/6 0 mapped it into 2x2 matrix game.
• Notice that we have already solved the
Cop Colin game as the matrix is the same as for Cops
G(x,y) C1 C2 and Robbers scaled by 1/6. Hence Rose
should bluff 1/3 of the time with a Q and
Robber R1 +$1 -$1 Colin should call 1/3 of the time with a K.
Rose R2 -$1 $0
Callin' Colin's Expected Value

R's Strategy A A K K Q Q C's Cards Total C's EV

R1 Bet Q 1 2 -2 2 -1 -1 C1 Call K 1 1/6
R2 Check Q 1 1 -2 1 -1 -1 C1 Call K -1 - 1/6
R1 Bet Q 1 2 -1 -1 -1 -1 C2 Fold K -1 - 1/6
R2 Check Q 1 1 -1 1 -1 -1 C2 Fold K 0 0
R's Cards K Q A Q A K C's Strategy

Introduction to Game Theory 25

 Optimal vs. Exploitive Play
So why play optimally in poker? Isn’t These are situations where I would
poker all about reading your opponents, deviate from optimal play:
and then adjusting? • If I see some of my opponent’s hole
• Optimal play is akin to using standard cards. Unfortunately this seems to go
market metrics. You can evaluate an on at both the poker table and the
option price based on the current price, financial world.
volatility, interest rate, etc, without any • If I have a tell on my opponent, an
prediction on the performance of the indication by his mannerisms that he
underlying equity. has a particular type of hand. Jay
• It helps to know what optimal play is Sipelstein pointed out often you can get
even though you are going to deviate tells on other traders.
from it. •If I have information on my opponent’s
• Sometimes you are against someone past behavior. For example in the last
who is a top player because of his million hands we have played, he has
reading skills, where you don’t want to never tried bluffing a 4th time after
get into that type of a contest with him. having been caught 3 times in a row.

Introduction to Game Theory 26