WIXLIB

Introduction to Game TheoryBill Chen, chenw@sig.comFriday, January 18, 2013(based on work with Dan Loeb and JerrodAnkenman)

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 toeach 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 PlayIntroduction to Game Theory2

Combinatorial GamesChess, Checkers, Go, Tic-tac-toe, Nim, Dotsand-Boxes, . 2 players Deterministic Common knowledge Sequential play Zero-sum. Win-lose, Draw-draw, Lose-win.Introduction to Game Theory3

Backgammon 2 playersRandom (dice)Common knowledgeSequential playZero-sum. Loser pays winner amount on thedoubling cube (possibly times 2 or 3)Introduction to Game Theory4

Poker Could be 2 players (heads-up) or moreRandom (cards)Hidden informationSequential playUsually zero-sum (unless house is taking apercentage of the pot or in sometournaments)Introduction to Game Theory5

Bridge 2 “players” (actually each is a 2person team) Random (cards) Hidden information. (Evenwithin a team!) Sequential play Zero-sum (even when duplicate)Introduction to Game Theory6

Zero-Sum Matrix GamesOdds-Evens, Roshambo 2 playersDeterministic. (Strategies can be random!)Common knowledge.Simultaneous play.Zero-sumWe will begin by studying Zero-sum matrixgames.Introduction to Game Theory7

Solitaire 1 player, or 1 player against “nature” Random (cards)Introduction to Game Theory8

Voting Systems Congress & President form coalitions.Winning coalition (if any) divides US Budgetamongst themselves.Many players (100 435 1 1)Deterministic?Common knowledge. (Wheeling-dealingbehind closed doors, but voting in public.)Sequential play.“Cooperative play”Introduction to Game Theory9

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-sumand cooperative.)Introduction to Game Theory10

AuctionsEach player can spend money for research to get estimate ofvalue of oil field. Each player places a sealed bid. High bidderwins. (Beware of the winner’s curse ) 2 or more playersRandom (estimation error, depends on spent research)Hidden information (research)Simultaneous play.Not zero-sum.Introduction to Game Theory11

Introduction to Game Theory0-sum 2-player Games. Odd-even game Cops & Robbers Market-makingCooperative 2-player Games. Prisoner’s Dilemma Outbidding Chicken / MAD Position DumpingMultiplayer Games Highway construction Cost of Sharing a SecretIntroduction to Game Theory12

Zero-Sum Two Player Games

Zero-sum Two-player Games.Odd-even game Players: Rose Todd vs. Colin Stevens Each player simultaneously displays 1or 2 fingers. Stevens wins 1 if total iseven (both players display samenumber of fingers). Todd wins 1 iftotal is odd.Odd-Even GameColin Stevens Payoffs to Colin shown in table.G(x,y)C1C2Rose chooses Row and-1Rose R1 1Colin chooses Column.Todd R2Introduction to Game Theory-1 114

Odd-Even game Theory of Moves (Steven J. Brams)Suppose Colin and Rose both are thinking ofchoosing 1.Then Rose should switch to 2.If she does, then Colin should switch to 2.So Rose should switch to 1. Odd-Even GameColin StevensSo Colin should switch to 1.G(x,y)C1C2We are back we started.R1 1- 1RoseThere seems to be noTodd R2 - 1 1stable solution!Introduction to Game Theory15

Nash Equilibrium John F. Nash, Nobel Prize 1994 for “pioneeringanalysis of equilibria in the theory of non-cooperativegames.” Nash’s work extended earlier idea of John VonNeumann and Oskar Morgenstern. A (Nash) Equilibrium is a set of strategies:One strategy for each player such that no player has anincentive to unilaterally change his strategy. In Odd-Even, Rose & Colin each have 2 possible“pure” strategies. None of the four possiblecombinations is a Nash equilibrium.Introduction to Game Theory16

Odd-Even GameMixed Strategiesy 100% Col. 1 all the timey 75%y 50%y 25%y 0% Col. 2 all the timeExpected payoff for Colin In order to avoid beingoutguessed, choose arandom combinationof strategies. Rose selects R1, x%of the time and R2,(100-x)% of the time. Colin chooses C1, y%of the time.Colin StevensG(x,y)C1C2- 1Rose R1 1Todd R2 - 1 1 1.00 0.80 0.60 0.40 0.20 0.00( 0.20)100%50%0%( 0.40)( 0.60)( 0.80)( 1.00)x% (Rose's mixed strategy)Introduction to Game Theory17

Odd-Even GameMixed Strategiesy 100% Col. 1 all the timey 75%y 50%y 25%y 0% Col. 2 all the timeExpected payoff for Colin y 50%, If Colin chooses C1 lessthan half of the time, Rose maypick R1 (x 100%) and Colinloses on average. y 50%, similarly, Rose picks R2(x 100%) and Colin loses onaverage. Setting y 50%, guarantees thatColin breaks even. Similarly x 50% guarantees thatRose breaks even.Colin StevensG(x,y)C1C2- 1Rose R1 1Todd R2 - 1 1 1.00 0.80 0.60 0.40 0.20 0.00( 0.20)100%50%0%( 0.40)( 0.60)( 0.80)( 1.00)Introduction to Game Theoryx% (Rose's mixed strategy)18

Odd-Even GameMixed Strategiesy 100% Col. 1 all the timey 75%y 50%y 25%y 0% Col. 2 all the timeExpected payoff for Colin x 50%, y 50% is a Nashequilibrium. Both players breakeven. If either player unilaterallychanges his strategy, he is notbetter off. (In fact, as is usuallythe case, he is indifferent.) The symmetry of the solutionreflects the symmetry of thegame. Let’s change the rules sosolution is not so obvious.Colin StevensG(x,y)C1C2- 1Rose R1 1Todd R2 - 1 1 1.00 0.80 0.60 0.40 0.20 0.00( 0.20)100%50%0%( 0.40)( 0.60)( 0.80)( 1.00)Introduction to Game Theoryx% (Rose's mixed strategy)19

Cops & Robbers Variant Rose is a sociopathic Robberwho can try to steal or not (1 or2). Colin is a Cop who can try tocatch Rose or not (1 or 2). If neither does anything, thepayoff is zero. If Rose stealssuccessfully, she gets 1, ifColin catches Rose, he gets 1. Rose has it in for Colin, so ifColin tries to catch Rose whenshe is not stealing, Rose gets 1 The game is the same asOdd/Even except the R2/C2outcome of 1 is changed to 0in Rose’s favor.Cop ColinG(x,y)C1 C2Robber R1 1 - 1Rose R2 - 1 0 The game favors Rose sinceshe can guarantee at least 0 bynot stealing. (Row 2). If Colin catches on to this hewill just not try to catch Rose(Col 2) and break even. So Rose can try to stealoccasionally, but 1/2 the time istoo much, since then Colin willjust try catching her all of thetime (Col 1) and break even.Introduction to Game Theory20

Cops & Robbers Varianty 100% Col. 1 all the timey 66.7%y 33.3%y 0% Col. 2 all the timeExpected payoff for Colin If Colin tries to catch Rose (C1)with y 1/3, then Rose’s best playis to not steal (R2) and Colin’sexpectation will be -y -1/3. Similarly if Colin tries to catchRose with y 1/3, Rose can juststeal and Colin’s expectation willbe y-(1-y) 2y-1 -1/3. Conversely, Colin can try tocatch Rose exactly 1/3 of thetime and guarantee anexpectation of -1/3. The optimal solution is RoseSteals 1/3 of the time and Colintries to catch her 1/3 of the time.Cop ColinG(x,y)C1 C2Robber R1 1 - 1Rose R2 - 1 0 1.00 0.80 0.60 0.40 0.20 0.00( 0.20)( 0.40)( 0.60)( 0.80)( 1.00)Introduction to Game Theory100%67%33%0%x% (Rose's mixed strategy)21

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

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 ofcards 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, ifColin calls there is a showdown with 2 going to the winner.ActionsRoseColinAceAlways Bets, will Always Calls, willalways win if called.always winKingNever Bets, willnever win if called.May Call (C1) orFold (C2).QueenMay Bet (R1) orCheck (R2).Never Calls, willnever win.Introduction to Game Theory23

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.ActionsCallin' Colin's Expected ValueR's StrategyR1 Bet QR2 Check QR1 Bet QR2 Check QR's 1-1KC's CardsC1 Call KC1 Call KC2 Fold KC2 Fold KC's StrategyRoseColinAceAlways Bets, will Always Calls, willalways win if called.always winKingNever Bets, willnever win if called.May Call (C1) orFold (C2).QueenMay Bet (R1) orCheck (R2).Never Calls, willnever win.Total C's EV11/6-1- 1/6-1- 1/600Introduction to Game Theory24

Mike Caro’s AKQ GameAKQ Matrix FormG(x,y) C1C2R11/6 - 1/6R2- 1/6 0 Cop ColinG(x,y)C1 C2Robber R1 1 - 1Rose R2 - 1 0Here, we have reduced the game to matrixform, which is rather interesting since wetook a sequential play poker game andmapped it into 2x2 matrix game.Notice that we have already solved thegame as the matrix is the same as for Copsand Robbers scaled by 1/6. Hence Roseshould bluff 1/3 of the time with a Q andColin should call 1/3 of the time with a K.Callin' Colin's Expected ValueR's StrategyR1 Bet QR2 Check QR1 Bet QR2 Check QR's 1-1KC's CardsC1 Call KC1 Call KC2 Fold KC2 Fold KC's StrategyIntroduction to Game TheoryTotal C's EV11/6-1 - 1/6-1 - 1/60025

Optimal vs. Exploitive PlaySo why play optimally in poker? Isn’tpoker all about reading your opponents,and then adjusting? Optimal play is akin to using standardmarket metrics. You can evaluate anoption price based on the current price,volatility, interest rate, etc, without anyprediction on the performance of theunderlying equity. It helps to know what optimal play iseven though you are going to deviatefrom it. Sometimes you are against someonewho is a top player because of hisreading skills, where you don’t want toget into that type of a contest with him.These are situations where I woulddeviate from optimal play: If I see some of my opponent’s holecards. Unfortunately this seems to goon at both the poker table and thefinancial world. If I have a tell on my opponent, anindication by his mannerisms that hehas a particular type of hand. JaySipelstein pointed out often you can gettells on other traders. If I have information on my opponent’spast behavior. For example in the lastmillion hands we have played, he hasnever tried bluffing a 4th time afterhaving been caught 3 times in a row.Introduction to Game Theory26

Introduction to Game Theory 22 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