Game Theory (Part 12)

Suppose we have a 2-player normal form game. As usual, we assume:

• Player A has some set of choices i = 1, \dots, m.

• Player B has some set of choices j = 1, \dots, n.

• If player A makes choice i and player B makes choice j, the payoff to player A is A_{ij} and the payoff to player B is B_{ij}.

Earlier we studied ‘pure strategies’, where the players make the same choice each time. Now we’ll study ‘mixed strategies’, where the players make their choices randomly. I want to show you that there’s always a Nash equilibrium when we allow mixed strategies—even in games like rock, paper, scissors that don’t have a Nash equilibrium with pure strategies!

But to do this, we need to define Nash equilibria for mixed strategies. And before that, we need to define mixed strategies!

First let’s make up a name for the set of player A’s choices:

X = \{ 1, \dots, m \}

and a name for the set of player B’s choices:

Y = \{1, \dots, n \}

Definition 1. A mixed strategy for player A is a probability distribution p on the set of their choices, X. A mixed strategy for player B is a probability distribution q on the set of their choices, Y.

Let’s recall exactly what this means, since you’ll need to know! Player A has a probability p_i of making any choice i = 1, \dots, m, and these probabilities obey

0 \le p_i \le 1

and

\displaystyle{ \sum_{i \in X} p_i = 1 }

Similarly, the probability that player B makes the choice j = 1, \dots, n is q_j, and these probabilities obey

0 \le q_j \le 1

and

\displaystyle{ \sum_{j \in Y} q_j = 1 }

In our earlier discussions of probability, we would call X and Y sets of events. An event is anything that can happen. But now the thing that can happen is that a player makes a certain choice in the game! So, now we’re calling X and Y sets of choices. But you can also think of these choices as events.

The expected payoff

Now let’s work out the expected value of the payoff to each player. To do this, we’ll assume:

1) Player A uses mixed strategy p.
2) Player B uses mixed strategy q.
3) Player A and player B’s choices are independent.

If you forget what ‘independent’ means, look at Part 8. The basic idea is player A’s choice doesn’t affect player B’s choice, and vice versa. After all, this is a ‘simultaneous game’, where each player makes their choice not knowing what the other has done.

But mathematically, the point is that we must assume the player’s choices are independent to know the probability of player A making choice i and player B making choice j is the product

p_i \, q_j

Knowing this, we can work out the expected value of the payoff to player A. Here it is:

\displaystyle{ \sum_{i \in X, j \in Y} A_{i j} \, p_i \, q_j }

I hope you see why. The probability that player A makes choice i and player B makes choice j is p_i q_j. The payoff to player A when this happens is A_{ij}. We multiply these and sum over all the possible choices for both players. That’s how expected values work!

Similarly, the expected value of the payoff for player B is

\displaystyle{ \sum_{i \in X, j \in Y} B_{i j} \, p_i \, q_j }

More details

If you’re in the mood, I can make this more formal. Remember that X \times Y is the set of all ordered pairs (i,j) where i \in X and j \in Y. A pair (i,j) is an event where player A makes choice i and player B makes choice j.

A’s payoff is a function on this set X \times Y. Namely, if player A makes choice i and player B makes choice j, A’s payoff is A_{ij}. There’s also a probability distribution on X \times Y. Namely, the probability of the event (i,j) is p_i \, q_j. So, the expected value of the payoff with respect to this probability distribution is

\displaystyle{ \sum_{(i,j) \in X \times Y} A_{i j} \, p_i \, q_j }

But this is equal to what we’ve seen already:

\displaystyle{ \sum_{i \in X, j \in Y} A_{i j} \, p_i \, q_j }

Matrix multiplication and the dot product

It looks like all of the students in this class have studied some linear algebra. So, I’ll assume you know how to:

take the dot product of vectors to get a number,

and

multiply a vector by a matrix to get a new vector.

Click on the links if you want to review these concepts. They will let us write our formulas for expected payoffs much more efficiently!

Here’s how. First, we think of the probability distribution p as a vector in \mathbb{R}^m; that is, a list of m numbers:

p = (p_1, \dots, p_m)

Second, we think of the probability distribution q as a vector in \mathbb{R}^n:

q = (q_1, \dots, q_n)

Third, we think of A and B as m \times n matrices, since that’s what they are:

A = \left( \begin{array}{cccc} A_{11} & A_{12} & \cdots & A_{1n} \\ A_{21} & A_{22} & \cdots & A_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ A_{m1} & A_{m2} & \cdots & A_{mn} \end{array} \right)

 

B = \left( \begin{array}{cccc} B_{11} & B_{12} & \cdots & B_{1n} \\ B_{21} & B_{22} & \cdots & B_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ B_{m1} & B_{m2} & \cdots & B_{mn} \end{array} \right)

Here’s the cool part:

Theorem. If A has mixed strategy p and B has mixed strategy q, then the expected value of A’s payoff is

p \cdot A q

and the expected value of B’s payoff is

p \cdot B q

Proof. We’ll only prove the first one, since the second works just the same way. By definition, A q is a vector in \mathbb{R}^m with components

\displaystyle{ (Aq)_i = \sum_{j = 1}^n A_{ij} q_j }

Also by definition, the dot product of p with Aq is the number

\begin{array}{ccl} p \cdot Aq &=& \displaystyle{ \sum_{i = 1}^m p_i \, (Aq)_i} \\ \\ &=& \displaystyle{ \sum_{i = 1}^m \sum_{j = 1}^n p_i \, A_{ij} \, q_j } \end{array}

But this agrees with our earlier formula for the expected value of A’s payoff, namely

\displaystyle{ \sum_{i \in X, j \in Y} A_{i j} \, p_i \, q_j  = \sum_{i = 1}^m \sum_{j = 1}^n A_{i j} \, p_i \, q_j }

So, we’re done! █

It’s not just quicker to write

p \cdot A q

than

\displaystyle{ \sum_{i \in X, j \in Y} A_{i j} \, p_i \, q_j }

It will also let us use tools from linear algebra to study games!

Nash equilibria

We’ll have to look at examples to understand this stuff better, but let me charge ahead and define ‘Nash equilibria’ for mixed strategies. The idea is similar to the idea we’ve already seen. A pair of mixed strategies, one for A and one for B, is a Nash equilibrium if neither player can improve the expected value of their payoff by unilaterally changing their mixed strategy.

Let’s make that precise. As before, the definition of Nash equilibrium involves two conditions:

Definition. Given a 2-player normal form game, a pair of mixed strategies (p,q), one for player A and one for player B, is a Nash equilibrium if:

1) For all mixed strategies p' for player A, p' \cdot A q \le p \cdot A q.

2) For all mixed strategies q' for player B, p \cdot B q' \le p \cdot B q.

Condition 1) says that player A can’t improve their payoff by switching their mixed strategy from p to any other mixed strategy p'. Condition 2) says that player B can’t improve their payoff by switching their mixed strategy from q to any other mixed strategy q'.

Now, one of our goals is to prove this big wonderful theorem:

Theorem. For any 2-player normal form game, there exists a pair of mixed strategies (p,q), one for player A and one for player B, that is a Nash equilibrium.

For zero-sum games this was proved by John von Neumann. Later John Nash proved a version for nonzero-sum games, and even games with more than two players. These are famously smart mathematicians, so you should not expect the proof to be extremely easy. We will need to work!

But next time we’ll start by looking at examples, to get our feet on the ground and start getting some intuition for these new ideas.

5 Responses to Game Theory (Part 12)

  1. […] Last time we introduced mixed strategies, and generalized the idea of Nash equilibrium to mixed strategies. Now let’s look at an example. […]

  2. Jesse says:

    In the proof of the first Theorem, should that first sigma be indexed from j = 1 to n?

    Also, small grammar point in the paragraph preceding “The expected payoff”:

    An events is…

    Thank you for your great notes!

    • John Baez says:

      You’re welcome! I bet you’re the Jesse in my class.

      In the proof of the first Theorem, should that first sigma be indexed from j = 1 to n?

      Yes, thanks—fixed. I keep mixing up my m’s and n’s.

  3. Arr says:

    Great lecture notes! The best way to explain Game theory is as you have done. Thanks. Do you have them on pdf?

You can use Markdown or HTML in your comments. You can also use LaTeX, like this: $latex E = m c^2 $. The word 'latex' comes right after the first dollar sign, with a space after it.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s