Some solutions for the last post

Exercises

Last time left some questions in the text or comments:

1. Why can we assume that both players are playing the same strategy for in a Nash equilibrium for a symmetric zero-sum game?
2. Why is Rock not used in Rock-Paper-Scissors-Well?
3. Why was there non-uniqueness for Rock-Paper-Papyrus-Scissors?
4. What's the equilibrium in Rock-Paper-SuperScissors?
5. Why is the scenario described in this scene from "A Beautiful Mind" not a Nash equilibrium?

Thanks to Sam Olesker-Taylor for working through questions like these with me.

Solutions

1. 

Let \(A,B,C,D\) denote strategies – so \(A\) might stand for "choose Rock every time", or it might stand for "choose Rock half the time and Scissors half the time", to give two examples. When I use strategy \(A\) and you use strategy \(B,\) write \(AB\) for the score I get (averaging over any random choices we make). Suppose the pair of strategies \( (A,B)\) forms a Nash equilibrium. Then by definition, for any strategies \(C,D,\)

\begin{align} CB&\leq AB \tag{1} \\
AD&\geq AB. \tag{2}
\end{align}
[The first inequality records the fact that I can't improve my score by unilaterally changing strategy. The second says that you can't improve your score by unilaterally changing strategy, and we've used that the game is symmetric and zero sum to see that you improving your score is equivalent to you causing my score to worsen.] Symmetry and the zero-sum nature of the game also allows us to see that \(AA=BB=0\), and that \(CA=-AC\).

Our goal is to show that \((A,A)\) forms a Nash equilibrium, which is equivalent to saying that for all \(C,D\)
\begin{align} CA&\leq AA, \tag{3} \\
AD&\geq AA. \tag{4}
\end{align}
Because \(CA\leq AA\) is equivalent to \(-AC\leq -AA\) which is equivalent to \(AC \geq AA\), it's enough to prove that (4) holds: (3) will then follow automatically.  
Using the definitions (1) and (2) we see, for any \(D\) and \(C\),
\[ AD\geq AB\geq CB. \] In particular, this holds for \(C=B\), so that \(AD\geq BB=0 =AA,\) as required.
 

2.

Rock isn't used in RPSW because it is dominated: there's a state which is always a better option. What that means is that whatever option you choose, if I choose Well I do at least as well as if I choose Rock, and there's at least one option of yours (in this case two options: Rock and Well) against which I do better by choosing Well than by choosing Rock.

This is an incomplete definition of a dominated strategy, which we will return to after considering the next question.
 

3.

Nonuniqueness in RPPS comes from the fact that in any strategy we can swap Paper for Papyrus, and vice versa, without changing anything. This leads to a first guess (and a mathematician's word for a guess, when they want to sound fancy, is a conjecture):

Conjecture: a Nash strategy fails to be unique when there are two choices which are functionally identical

Further exploration shows that this isn't quite right though: sometimes we can have a unique Nash equilibrium even when two states are copies of each other! For example, if we added Stone as a copy of Rock in the game Rock-Paper-Scissors-Well, then there is still a unique Nash equilibrium of choosing each of Paper, Scissors and Well a third of the time. The reason uniqueness holds here is because Rock isn't chosen in the Nash strategy anyway, so duplicating it doesn't add any extra optimal strategies. That leads us to a second guess:

Conjecture: a Nash strategy fails to be unique when there are two choices which are functionally identical and not dominated

This is better, but I asked you think as broadly as possible, and we can show that this doesn't capture all possibilities for how uniqueness can fail with the following examples.
 

Example: Rock Paper Scissors Pissors

In this game,

• Rock beats Paper (scoring 1 point for the winner)
• Paper beats Scissors (1)
• Scissors beats Rock (1)
• Rock ties with Pissors (each player scores 0 points)
• Pissors beats Paper (but the winner scores only 1/2 a point)
• Scissors beats Pissors (again scoring 1/2 a point)

Here, the scores obtained by Pissors are the same as someone would get on average by flipping a coin to choose between Paper and Scissors. Why is this relevant to uniqueness? Well, we said that choosing each of Rock, Paper and Scissors a third of the time was a Nash strategy, but now choosing Rock a third of the time and Pissors two thirds of the time will also be a Nash strategy, because it's effectively the same mixed strategy. The problem here was that Pissors can be expressed by choosing randomly between (or "mixing") the states of Scissors and Paper. Let's try again.

Conjecture: a Nash strategy fails to be unique when some option, which isn't dominated, can be expressed as a mixture of other choices

This still isn't quite complete, as an example closely related to the last one will show:
 

Example: Rock, Paper, Pissors, Rissors

Here, you can no longer directly choose Scissors. Instead, you can choose Rissors, which scores the same as the average of flipping a coin to choose between Rock and Scissors.
Now there is no one choice which can be replicated by combining other options (I'll leave it to you to consider why that is). However, uniqueness still fails: choosing Rock a third of the time and Pissors two thirds gives the same outcomes on average as choosing Paper a third of the time and Rissors two thirds (and both are Nash strategies). This leads to a final conjecture.

Conjecture: a Nash strategy fails to be unique if and only if there is redundancy: some non-dominated mixture of strategies can be obtained via two different combinations of choices

Here's the kicker: I haven't been able to prove if this conjecture is true!
This paper, in equation (8), gives a condition for the existence of a unique "completely mixed" Nash strategy, i.e. one in which every option is chosen at least some proportion of the time – unlike Rock in Rock Paper Scissors Well, which was never chosen in the Nash strategy. [The paper uses tables – or matrices – to describe games; my next post will discuss how to represent games with matrices.]

It's not hard to show that if a strategy is the only completely mixed Nash strategy, it's also the unique Nash strategy in total. [Why? Suppose \(A\) is the unique completely mixed Nash strategy, and \(B\) is another Nash strategy. We'll see in a subsequent post that if there are two Nash strategies then choosing randomly between them gives another Nash strategy, so that the strategy \(C\), which sees you flip an initial coin to choose whether to play according to strategy \(A\) or strategy \(B\), is a Nash strategy. It's also completely mixed: it uses every option at least half as often as \(A\) does. That contradicts the fact that \(A\) is unique among completely mixed strategies.]. 

Working out whether the conditions on the payoff matrix in the paper are the same as redundancy as defined here is something I haven't managed, and reader input would be welcomed!

 

Solution 2, continued

In view of the mixing discussions above, a dominated option should actually be defined as any state for which some mixture of the other states always does at least as well on average against every possible option, and does better on average against some option. For some purposes it will be convenient to demand that the option against which the mixture does strictly better is not itself dominated. Otherwise, in for example a game of Rock-Paper-Papyrus-Scissors, we could just add a useless state which loses to or draws with everything but loses worse to Paper than Papyrus; this would entail that Papyrus was a dominated strategy, and yet it defies some expectations of a dominated strategy, since for example 1/3rd each of Rock/Papyrus/Scissors would still be a Nash strategy.

 

4.

The solution, we will see in an upcoming post, is to play Rock half the time and SuperScissors and Paper a quarter of the time each. Is that what you expected? Soon I'll address how to calculate Nash equilibria and how to interpret solutions like this one!

 

5.

Nash says none of his group should attempt to seduce the lady they are all most interested in, because if they all target her then they will "block each other"; instead they should all "settle" for one of her friends.
In fact, in such a scenario, any one of them can improve their personal outcome by unilaterally changing to targeting their first choice instead. The Nash equilibrium is that exactly one of Nash's group goes for her: only then will the others have no incentive to change strategy because of the blocking issue.