<![CDATA[Game Theory (Part 3)]]>

<![CDATA[Game Theory (Part 3)]]>Last time we started looking at 2-player normal form games. The idea is that player A has $m$ different choices of which move to make, while player B has $n$ choices, and we have two $m \times n$ matrices of payoffs, $A$ and $B.$ If player A makes choice $i$ and player B makes choice $j,$ then the payoff to player A is $A_{i j},$ while the payoff to player B is $B_{i j}.$

What should you do if you’re playing a game like this? As we saw when playing rock-paper-scissors, sometimes the best thing is to adopt a strategy with some built-in randomness. In this game, if your opponent knows what you’re going to do, he can exploit that and beat you!

A strategy involving randomness is called a mixed strategy. They’re very important, and we’ll talk about them a lot. But today we’ll only consider pure strategies, where we definitely choose one of the choices available, with no randomness.

Notice: there are as many pure strategies as there are choices! For each choice, there’s a pure strategy where you always make that choice when playing the game. So, a lot of people say ‘pure strategy’ for what I call a ‘choice’. Other people use the word ‘action’.

Anyway: let’s try to figure out the best pure strategy for each player, if we can.

Sometimes this is impossible. For example, rock-paper-scissors has no best pure strategy. Could playing rock be best? No, because paper beats rock. Could playing paper be best? No, because scissors beats paper. Could playing scissors be best? No, because rock beats scissors.

But sometimes we can find a best pure strategy, and the ideas we meet will help us later when we study mixed strategies. So, let’s dive in!

Nash equilibria

Suppose player A makes choice $i$ and player B makes choice $j$ . Then we say $(i,j)$ is a Nash equilibrium if neither player can improve their payoff by changing their choice.

For example, look at this game:

	1	2
1	(10,10)	(9,-1)
2	(-1,1)	(-1,-1)

Here we are writing the matrices $A$ and $B$ together in one table, like last time, with $A$ in black and $B$ in red. But we could also separate them out:

$A = \left( \begin{array}{rr} 10 & 9 \\ -1 & -1 \end{array} \right) , \qquad B = \left( \begin{array}{rr} 10 & -1 \\ 1 & -1 \end{array} \right)$

It’s just a different way of conveying the same information.

Either way, it’s pretty clear what the players should do in this game! Both players should make choice 1. That way, they both win 10 points.

Furthermore, this pair of choices $(i,j) = (1,1)$ is certainly a Nash equilibrium. In other words: neither player can improve their payoff by unilaterally changing their choice! If player A switches to choice 2, their payoff drops to -1 points. If player B switches to choice 2, their payoff drops to 9 points.

Let’s give an official definition of Nash equilibrium and then look at some trickier examples. Remember, player A’s choices are $i = 1, 2, \dots , m,$ while player B’s choices are $j = 1, 2, \dots, n.$

Definition. Given a 2-player normal form game, a pair of choices $(i,j)$ is a Nash equilibrium if:

1) For all $1 \le i' \le m$ , $A_{i'j} \le A_{ij}.$

2) For all $1 \le j' \le n$ , $B_{ij'} \le B_{ij}.$

Condition 1) says that player A can’t improve their payoff by switching their choice from $i$ to any other choice $i'.$ Condition 2) says that player B can’t improve their payoff by switching their choice from $j$ to any other choice $j'.$

Examples

Let’s look at more examples of Nash equilibria, to see some funny things that can happen. First let’s modify the last game a little:

	1	2
1	(10,10)	(-1,10)
2	(10,-1)	(-1,-1)

Is there a Nash equilibrium? Yes—and just as before, it happens when both players pick pure strategy 1. Now player A’s payoff doesn’t get any worse when they switch to pure strategy 2. But it doesn’t improve, either! It stays equal to 10. Similarly, player B’s payoff doesn’t get any worse when they switch to pure strategy 2… but it doesn’t improve. So, neither player is motivated to change their strategy.

I said a Nash equilibrium is a situation where neither player can improve their payoff by changing their choice. But it might be clearer to say: neither player can improve their payoff by unilaterally changing their choice.

What do I mean by ‘unilaterally’ changing their choice? I mean that one player changes their choice while the other player does not change their choice.

But if both players change their choices simultaneously, sometimes they can improve both their payoffs! Lets see an example of that:

	1	2
1	(10,10)	(9,-1)
2	(-1,8)	(20,20)

Now it looks like both players will be happiest if they pick pure strategy 2. And it’s true! Moreover, this is a Nash equilibrium. Check and see.

But what if both players pick choice 1? This is also a Nash equilibrium! Shocking but true. If they both use pure strategy 1, neither player can improve their payoff by unilaterally changing their choice. If player A changes her choice, her payoff drops to -1. And if player B changes his choice, his payoff drops to -1.

Of course, they can improve their payoff if they both simultaneously change their choice to 2. But that’s not what the concept of Nash equilibrium is about.

This raises the question of whether Nash equilibrium is a good definition of ‘the best’ choice for each player. The big problem is figuring out what ‘best’ means—we’ll have to talk about that more. But we’re also seeing some problems with the word ‘the’. There may be more than one Nash equilibrium, so we can’t always talk about ‘the’ Nash equilibrium.

In other words, our example shows there isn’t always a unique Nash equilibrium.

Furthermore, a Nash equilibrium doesn’t always exist! Check out the game of rock-paper-scissors:

	rock	paper	scissors
rock	(0,0)	(-1,1)	(1,-1)
paper	(1,-1)	(0,0)	(-1,1)
scissors	(-1,1)	(1,-1)	(0,0)

It’s easy to see that there’s no Nash equilibrium. No matter what both players choose, at least one of them can always improve their payoff by switching to a different choice. If one of them wins the game, the loser can improve their payoff by switching to a different choice. If it’s a tie, either player can improve their payoff by switching to a different choice.

So: Nash equilibria are interesting, but they don’t always exist— at least not when we consider only pure strategies, as we’ve been doing. And even when they do, they’re not always unique! This is a bit frustrating. We’d like game theory to tell us how to play games well.

We can improve the situation by allowing mixed strategies, where a player picks different choices with different probabilities. If we do this, there is always at least one Nash equilibrium! This result was proved by—you guessed it!—John Nash. He did it in 1950, in this astoundingly short paper:

• John F. Nash, Jr., Equilibrium points in n-person games, Proceedings of the National Academy of Sciences 36 (1950), 48–9.

He eventually won the Nobel prize in economics for this work.

In fact, Nash was not the first to think about Nash equilibria; this idea goes back to the French economist Antoine Cournot, who wrote about it way back in 1838! However, Nash was the first to consider Nash equilibria for mixed strategies for general simultaneous multi-player games, and prove they always exist. (As we’ll see later, von Neumann and Morgenstern had already done this for the zero-sum 2-player games.)

John Nash

If you haven’t seen the movie about Nash called A Beautiful Mind, you should! Here’s the scene where Nash figures out something about multiplayer games:

It’s not very clear, mathematically speaking… but oh well. It’s a good movie and it gives you some sense of how Nash battled with mental illness for much of his life. He has now largely recovered and spends his time at Princeton University.

Here’s the young Nash—click for more details:

A ‘practical’ question

A student in my class asked what’s the best book or website on how to play blackjack well. I asked this on Google+ and got over 50 replies, which you can read here. If you know more, please tell me!

]]>