1Non-Zero Sum GamesR&N Section 17.6Matrix Form of Zero-Sum Gamesm22m21m12m11mij= Player A’s payoff if Player A follows pure strategy i and Player B follows pure strategy j2Results so far• 2 players, perfect information, zero-sum:– The game has always a pure strategy solution given by the minimax procedure• 2 players, perfect information, zero-sum:– The game has always a mixed strategy solution given by the minimax procedure• 2 players, perfect information, zero-sum:–???????ijjColumnsiRowsmMinMax))1(,)1(min(max22122111mpmpmpmpp×−+××−+×Prisoner’s Dilemma• Two persons (A and B) are arrested with enough evidence for a minor crime, but not enough for a major crime.• If they both confess to the crime, they each know that they will serve 5 years in prison.• If only one of them testify, he will go free and the other prisoner will serve 10 years. • If neither of them confess, they’ll each spend 1 year in prison3-1,-1-10,0Refuse0,-10-5,-5TestifyRefuseTestifyPlayer BPlayer AMatrix normal form for non-zero-sum games-1,-1-10,0Refuse0,-10-5,-5TestifyRefuseTestifyPlayer BPlayer APlayer A’s payoff for the pair of strategies A:Testify, B: TestifyPlayer B’s payoff for the pair of strategies A: Testify, B: RefuseMatrix normal form for non-zero-sum games4Why this example?• Although simple, this example models a huge variety of situations in which participants have similar rewards as in this game.• Joint work: Two persons are working on a project. Each person can choose to either work hard or rest. If A works hard then prefers to rest, but the outcome of both working is preferable to the outcome of both resting (the project does not get done).• Duopoly: Two firms compete for producing the same product and they both try to maximize profit. They can set two prices, “High” and “Low”. If both firms choose High, they both make a profit of $1000. If they both choose Low, they both make a lower profit of $600. Otherwise, the High firm makes a profit of $1200 and the Low firm takes a loss of $200.• Arms race, Robot detection, Use of common property……-1,-1-10,0Refuse0,-10-5,-5TestifyRefuseTestifyPlayer BPlayer AMatrix normal form for non-zero-sum games• This not a zero-sum game The interests (payoffs) of the “players” are no longer opposite of each other• What is the best strategy to follow for each player, assuming that they are both rational5-1,-1-10,0Refuse0,-10-5,-5TestifyRefuseTestifyPlayer BPlayer ADominant Strategies• Player A’s payoff is greater if he testifies than if he refuses, no matter what strategy B chooses• Therefore Player A does not need to consider strategy “refuse” since it cannot possibly yield a higher payoff-1,-1-10,0Refuse0,-10-5,-5TestifyRefuseTestifyPlayer BPlayer A6Dominant Strategies• The same reasoning can be applied to Player B:– Player B’s payoff is greater if he testifies than if he refuses, no matter what strategy A chooses– Therefore Player B does not need to consider strategy “refuse” since it cannot possibly yield a higher payoff-1,-1-10,0Refuse0,-10-5,-5TestifyRefuseTestifyPlayer BPlayer ADominant Strategies• We say that a strategy strictly dominates if it yields a higher payoff than any other strategy for every one of the possible actions of the other player.• Key result If both players have strictly dominating strategies, they provide a solution for the game (i.e., predict the outcome of the game) a dominant strategy equilibrium– Testify is a strictly dominant strategy for A– Testify is a strictly dominant strategy for B– Therefore (Testify, Testify) is the solution-1,-1-10,0Refuse0,-10-5,-5TestifyRefuseTestifyPlayer BPlayer A74,52,33,13,86,36,28,42,39,09,75,85,35,65,94,13,0IIIIIIIVIterated Elimination of Dominated Strategies• More generally: We can safely remove any strategy that is strictly dominated It will never be selected as a solution for the game• Iteratively removing dominated strategies is the first step in simplifying the game toward a solution• Is it sufficient? Did we get lucky earlier?4,52,33,13,86,36,28,42,39,09,75,85,35,65,94,13,0IIIIIIIV87,74,54,5IIIA5,4-1,66,-1IIA5,46,-1-1,6IAIIIBIIBIBHow would the two players play this game?Dominant Strategies• It is not the case that we are guaranteed that both players, or even that one player has a dominant strategy• We can still use the rule for simplifying the game: Get rid of the strictly dominated strategies because they will never be selected in the solution• However, we need a more general way of finding a solution to the game (i.e., to predict how rational players would play the game)• We need a definition that generalizes the earlier definition for zero-sum games (using minimax)7,74,54,5IIIA5,4-1,66,-1IIA5,46,-1-1,6IAIIIBIIBIBHow would the two players play this game?97,74,54,5IIIA5,4-1,66,-1IIA5,46,-1-1,6IAIIIBIIBIB()()( ) ( )Y,IIIAIIIB,IIIAIIIB,XIIIB,IIIABBAAuuuu≥≥For any strategy X of Player AFor any strategy Y of Player B(IIIA,IIIB) is an equilibrium because: • Player A cannot find a better strategy given that Player B uses strategy IIIB• Conversely, Player B cannot find a better strategy given that Player A uses strategy IIIASide Note: More than 2 Players?• The formalism extends directly to more than 2 players.• If we have n players, we need to define npayoff functions ui, i=1,..,n.• Payoff function uimaps a tuple of nstrategies to the corresponding payoff for player i• ui(s1,..,sn) = payoff for player i if players 1,..,n use pure strategy s1,…,sn.• Everything else (definition of dominating strategies, etc. remains the same)10More formal definition• A tuple of pure strategies (s1*,s2*,..,sn*) is a pure equilibrium if, for all i’s:for any strategy si.• In words: Player i cannot find a better strategy than si* if the other player use the remaining strategies in the equilibrium• Technically, called a pure Nash Equilibrium (NE)()()**1**1*1**1*1*1,,,,,,,,,,,,niiiiniiiisssssusssssu LLLL+−+−≤More formal definition (equivalent)• A tuple of pure strategies (s1*,s2*,..,sn*) is a pure equilibrium if, for all i’s:• In words: Player i cannot find a better strategy than si* if the other player use the remaining strategies in the equilibrium• Technically, called a pure Nash Equilibrium (NE)()**1*1*1*,,,,,,maxargniiiisisssssusiLL+−=11Examples and Question• So, we’ve generalized our concepts for solving games to non zero-sum games NEs• Basic
View Full Document
Unlocking...