Transcription
A Brief Introduction to Game TheoryJesse CrawfordDepartment of MathematicsTarleton State UniversityNovember 20, 2014(Tarleton State University)Brief Intro to Game TheoryNovember 20, 20141 / 36
The Penny GameTwo players.Start with 4 pennies in center of table.Each player can take 1 penny or 2 pennies on his/her turn.Player to take the last penny wins.First player blueSecond player red(Tarleton State University)Brief Intro to Game TheoryNovember 20, 20142 / 36
Backwards Induction for Penny Game(Tarleton State University)Brief Intro to Game TheoryNovember 20, 20143 / 36
Backwards Induction for Penny Game(Tarleton State University)Brief Intro to Game TheoryNovember 20, 20144 / 36
Backwards Induction for Penny Game(Tarleton State University)Brief Intro to Game TheoryNovember 20, 20145 / 36
Backwards Induction for Penny Game(Tarleton State University)Brief Intro to Game TheoryNovember 20, 20146 / 36
Backwards Induction for Penny Game(Tarleton State University)Brief Intro to Game TheoryNovember 20, 20147 / 36
Backwards Induction for Penny Game(Tarleton State University)Brief Intro to Game TheoryNovember 20, 20148 / 36
Backwards Induction for Penny Game(Tarleton State University)Brief Intro to Game TheoryNovember 20, 20149 / 36
Backwards Induction for Penny Game(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201410 / 36
Backwards Induction for Penny Game(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201411 / 36
Game Tree for Tic-Tac-Toe(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201412 / 36
Tic-Tac-Toe and CheckersWith optimal play, tic-tac-toe is a draw.Schaeffer et al. (2007) showed that checkers is also a draw.(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201413 / 36
ChessFirst turn white moves 20First turn black moves 20(20)(20) 400400 variations on first twomoves!(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201414 / 36
ChessAllis (1994) estimated number of chess variations:# of variations 10123 Number of atoms in visible universe!Chess programs do use the game tree.IIOnly plot to finite depth.Use an evaluation function to evaluate positions.(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201415 / 36
Scratch-off Lottery TicketTicket costs 1PrizeProbability 00.8(Tarleton State University) 20.15 100.05Brief Intro to Game TheoryNovember 20, 201416 / 36
Scratch-off Lottery TicketTicket costs 1xp(x) 00.8 20.15 100.05Expected ValueE(X ) X(Tarleton State University)xp(x) 0(0.8) 2(0.15) 10(0.05) 0.8Brief Intro to Game TheoryNovember 20, 201417 / 36
Texas Hold’emPot 23Bet 2Probability of hitting our straight p (Tarleton State University)Brief Intro to Game Theory446 0.087.November 20, 201418 / 36
Expected Value for Hold’em ProblemIf we foldxp(x) 01E(X ) 1(0) 0If we callxp(x) 23p 2(1 p)E(X ) 23p 2(1 p)We should call if23p 2(1 p) 02p 0.0823 2(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201419 / 36
Rock-Paper-ScissorsTwo playersEach one chooses Rock, Paper, or Scissors simultaneously.(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201420 / 36
Payoff Matrix for RPSFirst player blueSecond player 1)(0,0)(1,-1)Scissors(1,-1)(-1,1)(0,0)RPS is a zero sum game.(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201421 / 36
Randomized Strategy for RPSRandomized strategy.IIIpR probability of choosing RockpP probability of choosing PaperpS probability of choosing ScissorsExample:IIIpR 0.7pP 0.2pS 0.1(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201422 / 36
Randomized Strategy for RPSExample:IIIpR 0.7pP 0.2pS 0.1If opponent chooses Paper, his expected utility is0.7(1) 0.2(0) 0.1( 1) 0.6This is the maximum utility our opponent can achieve.We want to minimize his maximum utility.(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201423 / 36
Minimax Strategy for RPSMinimax strategy:IIIpR pP pS 131313Now if opponent chooses Paper, his expected utility is111(1) (0) ( 1) 0333No matter what he does, his expected utility will be 0.(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201424 / 36
Equilibrium StrategiesIn zero sum games with finite strategy spaces, minimax strategiesalways exist for both players.Theory can be generalized to multiplayer games, cf. Nash (1949).(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201425 / 36
King-Two-Jack Game(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201426 / 36
King-Two-Jack Game(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201427 / 36
Expected Value for Player 1p probability that Player 1 bluffs with 2 .q probability that Player 2 calls when Player 1 betsPlayer 1’s expected value isEV1 1 12 [3q 2(1 q)] 12 p[ 1q 2(1 q)]EV1 1 21 [q 2] 12 p[2 3q](Tarleton State University)Brief Intro to Game TheoryNovember 20, 201428 / 36
Optimal Calling FrequencyEV1 1 12 [q 2] 12 p[2 3q]Claim: Player 2 should choose q 23 .If q 23 , Player 1 can choose p 1, andEV1 1 q 31 .If q 23 , Player 1 can choose p 0, andEV1 12 q 31 .If q 23 , then(Tarleton State University)EV1 31 .Brief Intro to Game TheoryNovember 20, 201429 / 36
A Bit of AlgebraEV1 1 12 [q 2] 12 p[2 3q]EV1 1 21 [q(1 3p) 2 2p](Tarleton State University)Brief Intro to Game TheoryNovember 20, 201430 / 36
Optimal Bluffing FrequencyEV1 1 12 [q(1 3p) 2 2p]Claim: Player 1 should choose p 13 .If p 13 , Player 2 can choose q 0, andEV1 p 31 .If p 13 , Player 2 can choose q 1, andEV1 If p 13 , then(Tarleton State University)12 12 p 31 .EV1 13 .Brief Intro to Game TheoryNovember 20, 201431 / 36
King-Two-Jack SolutionPlayer 1 should always bet with K .Player 1 should bluffPlayer 2 should call13 of the time with 2 .23 of the time when Player1 bets.Player 1 will win about 33 cents per hand on average.(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201432 / 36
A Non-zero-sum Game: Prisoner’s DilemmaTwo criminalsInterrogated in separate roomsStay SilentConfessStay Silent(-1,-1)(0,-10)Confess(-10,0)(-5,-5)General principle: individuals acting in their own self interest canlead to a negative outcome for the group.Related problems:IIIPollution/“Tragedy of the Commons”Cartels/MonopoliesTaxation and public goods(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201433 / 36
Areas of Application for Game TheoryEconomics/Political ScienceIBargaining problemsBiologyIIICompetition between organismsSex ratiosGeneticsPhilosophy(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201434 / 36
ReferencesAllis, V. (1994). “Programming a Computer for Playing Chess”.Philosophical Magazine 41 (314).Chen, B., and Ankenman, J. (2006). The Mathematics of Poker.Conjelco.Luce, R.D., and Raiffa, H. (1989). Games and Decisions:Introduction and Critical Survey. Dover.Nash, J.F. (1949). Equilibrium Points in N-Person Games.Proceedings of the National Academy of Sciences 36 48-49.Schaeffer, et al. (2007). Checkers is Solved. Science 141518-1522.(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201435 / 36
Thank You!(Tarleton State University)Brief Intro to Game TheoryNovember 20, 201436 / 36
A Brief Introduction to Game Theory Jesse Crawford Department of Mathematics Tarleton State University November 20, 2014 (Tarleton State University) Brief Intro to Game Theory November 20, 2014 1 / 36. The Penny Game
