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.

Zero sum games: where Trump and Biden differ on trade

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. 

Surer than almost sure: Axiomatic probability

Axiomatic probability

Perhaps you noticed in the last post that I couldn’t help myself from slipping in just a little probability, when imagining throwing a dart at the number line. That shows how probability theory can be helpful in thinking about measures. What about the other way round: why is it useful to view probability theory as a sub-branch of measure theory?
Suppose we have a uniform random variable: a random number, between zero and 1, equally likely to be anywhere on the number line. How likely is it to be

1. between 0 and 1/2?
2. exactly equal to 2/3?
3. between 1/6 and 1/3, if I’ve told you it’s between 0 and 1/2?
   

Surer than almost sure: Measure theory

Measure theory

In this post and the following one, I will explain a bugbear of mine: the fact that something is described as ‘almost surely’ true, when it should really just be described as ‘surely’ true. The area of maths this falls in is ‘axiomatic’ probability theory, which is probability theory viewed as a sub-branch of something called measure theory, and so the thrust of this first post will be to briefly introduce measure theory.

Sets

Measure theory is, you guessed it, all about measuring things. The things you can measure are ‘sets’: a set is just the fancy way of saying any collection of things. Here are some sets.

1. \(\{1, 2, 3\}\). The curly brackets or braces are the way mathematicians denote sets, so this set has the numbers 1, 2 and 3 in it. The fancy name for the things in a set are the ‘elements’ of the set, so the elements of \(\{1, 2, 3\}\) are 1, 2 and 3.
2. \(\mathbb{R}\). This denotes the set of all ‘real’ numbers (hence the R): in other words, the number line.
3. \(\{x \in \mathbb{R} : 0 \leq x\leq  1\}\). I’ve introduced another way mathematicians write down sets: this means the collection of all real numbers (hence the \(x \in \mathbb{R} \) bit) which satisfy the condition \(0 \leq x \leq 1 \). So this is just the portion of the number line between zero and one (including for example 1/2, 0.23, \(1/\pi \),…).
4. \(\{\text{red, orange, yellow, green, blue, indigo, violet}\}\). Sets don’t have to consist of obviously mathematical things like numbers, but can include whatever you like, like here the colours of the rainbow. You could even mix and match, so \(\{1,  \text{red}\}\) is a set.
5. The set of all points on the ground which lie within Paris. I choose Paris partly because it’s well defined as a city: inside the ‘périphérique’ you’re in Paris, and outside you’re not.

 

Secret Santa schemes

In Secret Santa, rather than each person in a group getting a present for each other person, everyone receives just one present, from one person assigned to choose theirs. How do you decide who gets who in secret santa? Here are some of the things you might want to be true (with what I hope are some suitably fancy-sounding names):

Secrecy

Weak

No-one knows who has them

Strong

No-one knows who anyone has (except themselves)

Mixing

Minimal

No-one is assigned themself

Medium

No pair are both assigned each other

Strong

Everyone in the group is part of a single chain of gifts

Knowledge

In a group where some people don’t know others, you may want to ensure everyone is assigned someone they know.

Here are some comments on these conditions:

• In fact the ‘minimal mixing’ conditions is redundant: if no-one can know who has them, necessarily no-one can be assigned themselves. I include as a separate requirement for emphasis.
• Why wouldn’t we want pairs assigned each other? I suppose it feels against the spirit of the thing, maybe because you get to directly compare who gave the better gift.
• ‘Strong mixing’ can makes for fun present giving sessions, where I give my present first, then the receipient gives their present, and so on, and we never have to start again with someone new.
• The ‘knowledge’ condition can also adapt to impose other types of restriction. For example, you might not want for anyone to be assigned their spouse, or their ex. Let’s focus primarily on groups where everyone knows (and likes!) each other so we can ignore the ‘knowledge’ requirement.

Puzzle:  

How many people do you need before it’s possible to meet both a mixing condition and a secrecy condition? Have a think about it before you scroll down.
____________________________________