CPS 296.1 Normal-form gamesRock-paper-scissorsMatching pennies (~penalty kick)“Chicken”Rock-paper-scissors – Seinfeld variantDominancePrisoner’s Dilemma“Should I buy an SUV?”Mixed strategiesChecking for dominance by mixed strategiesIterated dominanceIterated dominance: path (in)dependenceTwo computational questions for iterated dominanceTwo-player zero-sum games revisitedBest-response strategiesHow to play matching penniesMatching pennies with a sensitive targetSlide 18Let’s change rolesMinimax theorem [von Neumann 1927]Practice gamesSolving for minimax strategies using linear programmingGeneral-sum gamesNash equilibrium [Nash 50]Nash equilibria of “chicken”Nash equilibria of “chicken”…The presentation gameThe “equilibrium selection problem”Some properties of Nash equilibriaHow hard is it to compute one (any) Nash equilibrium?What if we want to compute a Nash equilibrium with a specific property?Search-based approaches (for 2 players)Solving for a Nash equilibrium using MIP (2 players) [Sandholm, Gilpin, Conitzer AAAI05]Lemke-Howson algorithm (1-slide sketch!)Correlated equilibrium [Aumann 74]A correlated equilibrium for “chicken”A nonzero-sum variant of rock-paper-scissors (Shapley’s game [Shapley 64])Solving for a correlated equilibrium using linear programming (n players!)CPS 296.1Normal-form gamesVincent Conitzer [email protected], 0 -1, 1 1, -11, -1 0, 0 -1, 1-1, 1 1, -1 0, 0Row player aka. player 1 chooses a rowColumn player aka. player 2 (simultaneously) chooses a columnA row or column is called an action or (pure) strategyRow player’s utility is always listed first, column player’s secondZero-sum game: the utilities in each entry sum to 0 (or a constant)Three-player game would be a 3D table with 3 utilities per entry, etc.Matching pennies (~penalty kick)1, -1 -1, 1-1, 1 1, -1LRL R“Chicken”0, 0 -1, 11, -1 -5, -5DSD SSDDS•Two players drive cars towards each other•If one player goes straight, that player wins•If both go straight, they both dienot zero-sumRock-paper-scissors – Seinfeld variant0, 0 1, -1 1, -1-1, 1 0, 0 -1, 1-1, 1 1, -1 0, 0MICKEY: All right, rock beats paper!(Mickey smacks Kramer's hand for losing)KRAMER: I thought paper covered rock.MICKEY: Nah, rock flies right through paper.KRAMER: What beats rock?MICKEY: (looks at hand) Nothing beats rock.Dominance•Player i’s strategy si strictly dominates si’ if –for any s-i, ui(si , s-i) > ui(si’, s-i) •si weakly dominates si’ if –for any s-i, ui(si , s-i) ≥ ui(si’, s-i); and–for some s-i, ui(si , s-i) > ui(si’, s-i)0, 0 1, -1 1, -1-1, 1 0, 0 -1, 1-1, 1 1, -1 0, 0strict dominanceweak dominance-i = “the player(s) other than i”Prisoner’s Dilemma-2, -2 0, -3-3, 0 -1, -1confess•Pair of criminals has been caught•District attorney has evidence to convict them of a minor crime (1 year in jail); knows that they committed a major crime together (3 years in jail) but cannot prove it•Offers them a deal:–If both confess to the major crime, they each get a 1 year reduction–If only one confesses, that one gets 3 years reductiondon’t confessdon’t confessconfess“Should I buy an SUV?” -10, -10 -7, -11-11, -7 -8, -8cost: 5cost: 3cost: 5cost: 5cost: 5cost: 5cost: 8 cost: 2purchasing costaccident costMixed strategies•Mixed strategy for player i = probability distribution over player i’s (pure) strategies•E.g.,1/3 , 1/3 , 1/3•Example of dominance by a mixed strategy:3, 0 0, 00, 0 3, 01, 0 1, 01/21/2Usage: σi denotes a mixed strategy, si denotes a pure strategyChecking for dominance by mixed strategies •Linear program for checking whether strategy si* is strictly dominated by a mixed strategy:•maximize ε•such that: –for any s-i, Σsi psi ui(si, s-i) ≥ ui(si*, s-i) + ε–Σsi psi = 1•Linear program for checking whether strategy si* is weakly dominated by a mixed strategy:•maximize Σs-i[(Σsi psi ui(si, s-i)) - ui(si*, s-i)]•such that: –for any s-i, Σsi psi ui(si, s-i) ≥ ui(si*, s-i)–Σsi psi = 1Iterated dominance•Iterated dominance: remove (strictly/weakly) dominated strategy, repeat•Iterated strict dominance on Seinfeld’s RPS:0, 0 1, -1 1, -1-1, 1 0, 0 -1, 1-1, 1 1, -1 0, 00, 0 1, -1-1, 1 0, 0Iterated dominance: path (in)dependence0, 1 0, 01, 0 1, 00, 0 0, 1Iterated weak dominance is path-dependent: sequence of eliminations may determine which solution we get (if any)(whether or not dominance by mixed strategies allowed)0, 1 0, 01, 0 1, 00, 0 0, 10, 1 0, 01, 0 1, 00, 0 0, 1Iterated strict dominance is path-independent: elimination process will always terminate at the same point(whether or not dominance by mixed strategies allowed)Two computational questions for iterated dominance•1. Can a given strategy be eliminated using iterated dominance?•2. Is there some path of elimination by iterated dominance such that only one strategy per player remains?•For strict dominance (with or without dominance by mixed strategies), both can be solved in polynomial time due to path-independence:–Check if any strategy is dominated, remove it, repeat•For weak dominance, both questions are NP-hard (even when all utilities are 0 or 1), with or without dominance by mixed strategies [Conitzer, Sandholm 05]–Weaker version proved by [Gilboa, Kalai, Zemel 93]Two-player zero-sum games revisited0, 0 -1, 1 1, -11, -1 0, 0 -1, 1-1, 1 1, -1 0, 0•Recall: in a zero-sum game, payoffs in each entry sum to zero– … or to a constant: recall that we can subtract a constant from anyone’s utility function without affecting their behavior•What the one player gains, the other player losesNote: a general-sum k-player game can be modeled as a zero-sum (k+1)-player game by adding a dummy player absorbing the remaining utility, so zero-sum games with 3 or more players have to deal with the difficulties of general-sum games; this is why we focus on 2-player zero-sum games here.Best-response strategies•Suppose you know your opponent’s mixed strategy–E.g., your opponent plays rock 50% of the time and scissors 50%•What is the best strategy for you to play?•Rock gives .5*0 + .5*1 = .5•Paper gives .5*1 + .5*(-1) = 0•Scissors gives .5*(-1) + .5*0 = -.5•So the best response to this opponent strategy is to (always) play rock•There is always some pure strategy that is a best response–Suppose you have a mixed strategy that is a best response; then every one of the pure strategies
View Full Document
Unlocking...