Nash's theorem shows the existence of a certain "optimal" strategy for playing games, called the Nash strategy. This is the first of a series of posts exploring the introductory concepts of game theory and Nash's theorem, with the ultimate goal of explaining in exactly what sense a Nash strategy is optimal, and why, despite this "optimality", it's rarely a good idea to play the Nash strategy if you want to win. This post will define Nash's theorem for certain types of game, called zero-sum games, and examine (without going into depth) how game theory can illuminate a key policy difference between the candidates in the last US presidential election. There are puzzles dotted through the text, and gathered together in the comments section, for those of you who are interested in doing some exploring on your own; these puzzles will be discussed in future posts.
Nash's theorem
You may have heard of the mathematician and economist John Nash, perhaps through the film "A beautiful mind" which portrays parts of his life and career. One version of his theorem is the following, though he actually proved something more general, allowing for more than two players, games which are not zero-sum or symmetric, and guaranteeing the existence of a collection of strategies – one for each player – collectively called a Nash equilibrium.
Nash's theorem: For any two-player symmetric zero-sum game, there exists a Nash strategy.
What do each of those terms mean? I won't give formal definitions because pinning everything down rigorously can be tedious. Instead, I'll give an idea of what you should be picturing for each word, and then lots of examples.
- Game
- Picture something like Rock Paper Scissors, although the definition extends to more general situations of decision making if the possible outcomes can be modelled abstractly with "points" that you score.
- Two-player
- Exactly what you think it means
- Symmetric
- The options available to me are the same as the options available to you, and the corresponding points match up (if my Paper beats your Rock, then your Paper beats my Rock).
- Zero-sum
- I can only win by making you lose, so that if we track total scores (with losses counting as negative points), my score added to your score always gives zero.
- Strategy
- Either a "pure" strategy, like 'choose rock every time', or a "mixed" strategy, like 'choose rock, paper, or scissors based on the outcome of a dice roll'.
Most of the terms in Nash's theorem, then, are easy to envision. It remains to discuss what a Nash strategy is.
Nash strategies
A Nash equilibrium in a multiplayer game is a scenario where no player can improve their average payoff by unilaterally changing strategy. That is, if all the other players stick to their current strategies, I can't score better by changing my strategy than by sticking to it. The strategies that each player is doing form a collection of Nash strategies.
Here are some examples of (non zero-sum) games and their Nash equilibria.
Examples (non zero-sum games):
- Which restaurant? A brother and sister are choosing where to go for dinner. The brother would prefer to go to a Chinese restaurant, the sister an Indian restaurant, but they'd each rather settle for their worse option than have to eat at home, which is what their parents will impose if they can't agree. The value of each possible outcome is different for the two siblings, so this is not a symmetric game, and they can both "lose" simultaneously if they have to eat at home so it's not zero-sum either. Here are two possible Nash equilibria: both agreeing to go to the Chinese, or both agreeing to go to the Indian. In either of these scenarios, neither sibling can hope to benefit from changing their own strategy (without the other also changing strategy) because they'll end up eating at home.
- Which lane? One car is behind another and wants to overtake. If both drivers drive in the inside lane they'll crash, and similarly for the outside lane. Here are two Nash equilibria: the front driver goes to the inside lane and the rear driver to the outside lane, and the opposite. Again, either driver unilaterally changing will lead to a worse outcome for that driver (crashing, instead of not crashing). There's another Nash equilibrium though: both drivers choose lane by flipping a coin. This is obviously a bad idea, but it's still a Nash equilibrium, because it needs both drivers to stop choosing lane randomly if the crash probability is to be reduced below a half: one driver unilaterally changing away from the bad strategy isn't enough to reach a situation where there is a less than 50% chance of crashing.
I stated Nash's theorem above in terms of a Nash strategy, but I've defined collections of Nash strategies. In fact, in a symmetric zero-sum two-player game – the type of game which we'll focus on – if we're in a Nash equilibrium and I change from doing my strategy to copying yours, we'll still be in a Nash equilibrium. See if you can explain why! [Note that it needn't be true for non zero-sum games – in one of the "good" equilibria in the driving, if I swap to your strategy we end up in a scenario where I can improve my outcomes by swapping back – so your argument will have to use the zero-sum assumption in some essential way. Likewise for symmetry – swapping the names of states for one of the players in a symmetric game will typically lead to a game where the Nash equilibrium necessarily involves the players choosing differently.] This means we can write "is a Nash strategy" as shorthand for "is one of the strategies in a collection forming a Nash equilibrium".
Here are some zero-sum uncooperative two-player games – in particular, variants of Rock-Paper-Scissors – to provide some insight.
Examples (zero-sum games):
- Traditional Rock-Paper-Scissors: (Rock beats Paper, Paper beats Scissors, Scissors beats Rock). The Nash equilibrium is that both players choose each option with probability 1/3, leading to each player winning, losing, and drawing 1/3rd of the time each. Knowing that your opponent is playing this strategy, nothing you can do changes your win, draw and loss probabilities, so you have no incentive to change from the Nash strategy yourself.
- "Pierre, papier, ciseaux, puits" (Rock-Paper-Scissors-Well): This is an old French variant on Rock-Paper-Scissors, in which Scissors and Rock both lose to Well (they fall in the Well) and Paper beats Well (it covers it). Here, there is no reason to choose Rock, since any time you do, choosing Well instead would give you at least as good a score. The Nash strategy is to choose Scissors, Paper, and Well 1/3rd of the time each, and never Rock.
- Rock, Paper, Papyrus, Scissors: In this version I've just made up, Papyrus beats Rock, loses to Scissors, and ties with Paper: in effect, it's just a duplicate of Paper. So in this case there are many possible Nash strategies, including:
- 1/3rd each for Rock, Paper, and Scissors;
- 1/3rd each for Rock, Papyrus and Scissors;
- 1/3rd each for Rock and Scissors and 1/6th each for Paper and Papyrus.
- Rock-Paper-SuperScissors: Rock, Paper, Scissors, but where wins with Scissors count double. Nash's theorem tells us that this has a Nash strategy, and a future post will be on calculating Nash strategies, using this as an example. See if you can work out the Nash strategy – or, have a guess at what you think it might be – in the mean time.
I claim that one can often expect two key properties to hold:
- There is a unique Nash strategy.
- When I use a Nash strategy, I choose every option available to me at least some portion of the time. Such a strategy is called a completely mixed strategy.
Next time we'll explore why these properties aren't always true, using examples from the list above. In the mean time, you can think about what it is about Rock, Paper, Scissors, Well that means the Nash strategy does not use every available option, and what it is about Rock, Paper, Papyrus, Scissors that enables it to have more than one Nash strategy. [Try to think as broadly as possible, and come up with more examples where there is more than one Nash strategy.]
How can these ideas help us understand trade?
Here's Trump describing the United States' international trade while campaigning to be the Republican presidential candidate in 2015:
"We don’t win anymore. We lose to China. We lose to Mexico both in trade and at the border. We lose to everybody." (source)Now here's Biden on roughly the same topic during the 2020 presidential campaign:
"China can’t afford to ignore half the global economy if we’re united. That gives us substantial leverage to shape the future rules of the road on everything from the environment to labor to trade to technology to transparency." (source)Game theory helps illuminate the difference in their positions. Even as they agree on the need to get China to change its policies for America's benefit, a philosophical difference between the two is apparent. Trump views trade as being close to a zero-sum game, with any win for one side coming by making the other lose. Biden has a greater faith in alliances and cooperation, believing that working together can lead to better outcomes for all, as we saw was possible in the non zero-sum game of choosing a lane to drive in.
As a final remark, you can think trade is a non zero-sum game and still not support of free trade and globalisation. Left wing supporters of Brexit, for example, might argue that globalisation is a means by which workers' rights are undermined everywhere – so that free trade agreements are leading to worse outcomes for both sides (at least, workers on both sides) rather than better outcomes.
Here are the puzzles that have been set through the post:
ReplyDelete- Why can we assume that both players are playing the same strategy for in a Nash equilibrium for a zero-sum game?
- Why is Rock not used in Rock-Paper-Scissors-Well?
- Why was there non-uniqueness for RPPS?
- What's the equilibrium in Rock-Paper-superScissors?
And here's a bonus one: the film "A beatiful mind" includes a (not progressive) scene which seems designed to show Nash coming up with his equilibrium. Why is the scenario described *not* in fact a Nash equilibrium? https://www.youtube.com/watch?v=LJS7Igvk6ZM
Interesting post as always!
ReplyDeleteFor the first question, does this also require that the game be symmetrical? (I may be wrong - but would a contrived RPS in which player A’s paper and scissors always lose, whilst B’s are as normal not have a Nash equilibrium with different strategies? (Namely, A plays rock and B plays paper.))
You're correct! In an early version I just said symmetrical, then I realised that the lane choosing game was symmetrical but has Nash equilibria where the players are not matching strategy -- I thought I'd corrected my error by putting zero-sum, but in fact both are necessary. Good catch, thanks :)
Delete(I've edited the post to correct this, though it's not straightforward to edit a comment it seems.) Another example would be to take any symmetric game with a Nash equilibrium which is not uniform, and swap the names of some of the states for one player, so that while morally the players are doing the same strategy, technically they aren't
Delete