Section 4.1 Introduction to Two-Player Non-Zero-Sum Games¶
In this section we introduce non-zero-sum games. In a non-zero-sum game the players' payoffs no longer need to sum to a constant value. Now it is possible for both players to gain or both players to lose.
Exercise 4.1.1. Compare properties.
What are some properties of a zero-sum game that may no longer hold for a non-zero-sum game? For example, in a zero-sum game is it ever advantageous to inform your opponent of your strategy? Is it advantageous to communicate prior to game play and determine a joint plan of action? Would you still want to minimize your opponents payoff?
Let's build an understanding of non-zero-sum games by looking at an example.
Example 4.1.2. Battle of the Sexes.
Alice and Bob want to go out to a movie. Bob wants to see an action movie, Alice wants to see a comedy. Both prefer to go to a movie together rather than to go alone. We can represent the situation with the payoff matrix in Table 4.1.3:
|Bob||Action||\((2, 1)\)||\((-1, -1)\)|
|Comedy||\((-1, -1)\)||\((1, 2)\)|
Exercise 4.1.4. Not zero-sum.
Explain why this is not a zero-sum game.
In zero-sum games it is never advantageous to let your opponent know you strategy. Does that property still apply for games like Battle of the Sexes?
Exercise 4.1.5. Announcing a strategy.
Could it be advantageous for a player to announce his or her strategy? Could it be harmful to announce his or her strategy? If possible, describe a scenario in which it would be advantageous to announce a strategy. If possible, describe a scenario in which it would be harmful to announce a strategy.
We might first try to analyze Battle of the Sexes using the same techniques as we used for zero-sum games. For example, we might start as we would in zero-sum games by looking for any equilibrium points.
Exercise 4.1.6. Equilibrium points.
Since our main goal in analyzing games has been to find equilibrium points, let's find any equilibrium points for Battle of teh Sexes. Are there any strategy pairs where players would not want to switch?
There are two!
Exercise 4.1.7. Values of equilibrium points.
Are the equilibrium points the same (in other words, does each player get the same payoff at each equilibrium point)? Compare this to what must happen for zero-sum games.
Now that we know Battle of the Sexes has two equilibrium points, we should try to find actual strategies for Alice and Bob. Is there a good strategy for each if they play the game only once? What if they repeat the game? Recall that with zero-sum games, if there was an equilibrium, rational players always want to play it, even if the game is repeated. Does that still seem to work here? Also, how might the ability to communicate change what the players do?
Exercise 4.1.8. Repeating the game.
Suppose the game is played repeatedly. For example, Alice and Bob have movie night once a month. Suggest a strategy for Alice and for Bob. Feel free to play the game with someone from class. Try a playing several times without communicating about your strategy before each game.
Exercise 4.1.9. Communication.
How could communication affect the choice of strategy? Now play several times where you are allowed to communicate about your strategy. Does this change your strategy?
Exercise 4.1.10. Mixed strategy equilibrium.
In either case, communicating and not communicating, do you think your strategies for Alice and Bob represent a mixed strategy equilibrium?
Exercise 4.1.11. Compare to zero-sum.
In a zero-sum game, if there is a pure strategy equilibrium, then what happens when you repeat a game? If you repeat Battle of the Sexes, does the game always result in an equilibrium pair?
Hopefully, you are beginning to see some of the challenges for analyzing non-zero-sum games. We know there are equilibrium points in Battle of the Sexes, but even rational play may not result in an equilibrium. For the remainder of this section, let's assume that players are not allowed to communicate about strategy prior to play. Such games are called non-cooperative games. Before moving on, let's try to find the maximin strategies for our players using the graphical method, as we did with zero-sum games.
Exercise 4.1.12. Bob's payoff matrix.
Consider Battle of the Sexes from Bob's point of view. We know that Bob wants to maximize his payoff (that has not changed). So Bob doesn't care what Alice's payoff's are. Write down Bob's payoff matrix.
Exercise 4.1.13. Graphical method on Bob's matrix.
Recall that the graphical method represents Bob's expected payoff depending on how often he plays each of his options. Sketch the graph associated with Bob's payoff matrix.
Exercise 4.1.14. Bob's maximin mixed strategy.
The area between the two lines still represents the possible expected values for Bob, depending on how often Alice plays each of her strategies. So as before, the bottom lines represent the least Bob can expect as he varies his strategy. Thus, the point of intersection will represent the biggest of these smallest values (the maximin strategy). Find this point of intersection. How often should Bob play each option? What is his expected payoff?
So no matter what Alice does, Bob can expect that over the long run he wins at least the value you found in Exercise 4.1.14. Make sure you understand this before moving on.
Exercise 4.1.15. Alice's maximin mixed strategy.
Now consider Battle of the Sexes from Alice's point of view. Write down her payoff matrix and use the graphical method to find the probability with which she should play each option and her expected payoff.
Now, from Exercise 4.1.14 and Exercise 4.1.15 you have the minimum payoff each player should expect. Note that since this is not a zero-sum game, both players can expect a positive payoff. But now we want to see how this pair of mixed strategies really works for the players.
Exercise 4.1.16. Alice's expected value when Bob plays his maximin strategy.
Assume Bob plays the mixed strategy from Exercise 4.1.14. Calculate Alice's expected value for each of her pure strategies (\(E_2\)(Comedy) and \(E_2\)(Action)).
Exercise 4.1.17. Alice's preference.
Are Alice's expected values equal? If not, which strategy does she prefer when Bob plays the mixed strategy from Exercise 4.1.14? Does Alice want to deviate from her mixed strategy?
Exercise 4.1.18. Mixed strategy equilibrium.
Now if Alice plays a pure strategy, does Bob want to change his strategy? So is the mixed strategy pair for Bob and Alice from Exercise 4.1.14 and Exercise 4.1.15 an equilibrium? In fact, if Bob changes his strategy, how does his expected value compare to the expected value for his mixed strategy?
Exercise 4.1.19. Downside of the graphical method.
What goes wrong with the graphical method in the case of a non-zero-sum game?
Is it important for Alice to consider the minimax strategy? Does Alice have any reason to minimize Bob's payoff?
As we can see by the above example, the methods used to analyze zero-sum games may not be too helpful for non-zero-sum games. Part of the problem is that in solving zero-sum games we take into consideration that one player wants to minimize the payoff to the other player. This is no longer the case. Changing strategies may allow BOTH players to do better. A player no longer has any reason to prevent the other player from doing better.
Exercise 4.1.20. Response to the mixed strategy.
So we know the mixed strategy won't give us an equilibrium. But suppose we start there. In other words, suppose Bob plans to play the mixed strategy from Exercise 4.1.14. Which pure strategy should Alice play? In response, which pure strategy should Bob play? What is the outcome? Do you end up at an equilibrium?
Exercise 4.1.21. Bos's expected value when Alice plays her maximin strategy.
Now suppose Alice plans to play the mixed strategy from Exercise 4.1.15. Calculate the expected value for Bob for each of his pure strategies. Which pure strategy does Bob prefer to play? How will Alice respond to Bob's pure strategy? What is the outcome? Do you end up at an equilibrium?
Exercise 4.1.22. Out-guessing the mixed strategy.
Suppose Bob thinks Alice will try the mixed strategy and Alice thinks Bob will try the mixed strategy. Which pure strategy will each play? What is the outcome? Do you end up at an equilibrium?
Exercise 4.1.23. Playing the maximin mixed strategy.
We've seen the limitations of the graphical method, but what about the expected value method?
Exercise 4.1.24. Expected value solution.
Try applying the expected value method to Battle of the Sexes. What mixed strategies do you get? Explain why this method will also not result in an equilibrium. You might want to consider whether it is important for one player to minimize the expected value for the other player.
Now that we have seen how the methods that allowed us to solve zero-sum games don't work for non-zero-sum games, we will need to find new ways to approach non-zero-sum games.