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

<![CDATA[Game Theory (Part 13)]]>Last time we introduced mixed strategies, and generalized the idea of Nash equilibrium to mixed strategies. Now let’s look at an example.

Matching pennies

In the game of matching pennies, each player has a penny and must secretly turn the penny to either heads or tails. They then reveal their choices simultaneously. If the pennies match—both heads or both tails—player A keeps both pennies, so he wins one from player B. If the pennies do not match—one heads and one tails—B keeps both pennies, so she wins one from A.

Let’s write this game in normal form! If the pennies match, A wins one penny and B loses one, so their payoffs are (1,-1). If they pennies don’t match, A loses one and B wins one, so their payoffs are (-1,1). If we say

• choice 1 is heads
• choice 2 is tails

then the normal form looks like this:

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

We can also break this into two matrices in the usual way, one showing the payoff for A:

$A = \left( \begin{array}{rr} 1 & -1 \\ -1 & 1 \end{array} \right)$

and one showing the payoff for B:

$B = \left( \begin{array}{rr} -1 & 1 \\ 1 & -1 \end{array} \right)$

If you examine this game, it’s easy to see no pure strategy is a Nash equilibrium. If A chooses heads, B will want to choose tails. But if B chooses tails, A will want to choose tails. And if A chooses tails, B will want to choose heads. And if B chooses heads, A will want to choose heads! There’s always someone who would do better by changing their choice. It’s a lot like rock, paper, scissors.

Mixed strategies

However, there is a Nash equilibrium if we allow mixed strategies, where the players can randomly make their choice according to a certain probability distribution.

Let’s see if we can guess where this Nash equilibrium is. If you were player A, can you guess what you should do? Should you choose heads 90% of the time? 80% of the time? 70% of the time?

A student says: “50% of the time.”

Yes, that seems right. After all, if player A chooses heads most of the time, player B can win most of the time by always choosing tails! And if player A chooses tails most of the time, B can win most of the time by always choosing heads! The only way out is for player A to choose heads with probability 1/2.

But what about player B? What should player B do?

A student says: “She should also choose heads 50% of the time.”

Yes, that makes sense too—for the same sort of reason.

So, let’s see if these mixed strategies give a Nash equilibrium. Remember that we write

$p = (p_1, p_2)$

for A’s mixed strategy. $p_1$ is the probability that A makes choice 1: that is, chooses heads. $p_2$ is the probability that A makes choice 2: that is, chooses tails. So, what $p$ are we guessing here?

The students say:

$p = (1/2, 1/2)$

Okay, that’s A’s mixed strategy. And what about B’s mixed strategy?

The students say:

$q = (1/2, 1/2)$

Okay, now lets see if these are really a Nash equilibrium! Remember the definition from last time:

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.$

We want to check this for our $p$ and $q.$ This looks hard, because we have to check part 1) for all $p'$ and part 2) for all $q'.$ But sometimes it’s easy, and I’ve picked a game where it’s easy.

Why is it easy? Well, first consider part 1). For this we need to show

$p' \cdot A q \le p \cdot A q$

To show this, let’s start by computing $A q:$

$A q = \left( \begin{array}{rr} 1 & -1 \\ -1 & 1 \end{array} \right) \left( \begin{array}{r} 1/2 \\ 1/2 \end{array} \right) = \left( \begin{array}{r} 0 \\ 0 \end{array} \right)$

Hey! It’s the zero vector, a list of all zeros! We write this simply as 0. So, we’re trying to show

$p' \cdot 0 \le p \cdot 0$

but of course this is true, because both sides equal the number zero!

What’s going on here? The point is that if B uses mixed strategy $q,$ A’s expected payoff is zero no matter what mixed strategy A uses! If A uses any mixed strategy $p',$ the expected value of his payoff is always $p' \cdot A q = 0,$ since $Aq = 0.$

Now let’s check part 2). This should be similar. Now we need to show that for any mixed strategy $q',$

$p \cdot B q' \le p \cdot B q$

Hey, this is actually a bit different! Before we could use $Aq = 0$ to get the job done. But now we see $B q'$ showing up, and $q'$ is any mixed strategy, so we can’t calculate this! What do we do?

We need to use the power of math!

We need to use a fact about matrices and dot products! For any vectors $v \in \mathbb{R}^m$ and $w \in \mathbb{R}^n$ and any $m \times n$ matrix $A,$ we have

$v \cdot A w = A^T v \cdot w$

Here $A^T$ is the transpose of the matrix $A;$ that is, the matrix we get by switching rows and columns:

Here’s the formula for the transpose:

$A^T_{ji} = A_{ij}$

Someday when I’ll in a bad mood I’ll make you prove $v \cdot A w = A^T v \cdot w$ in your homework.

Anyway, applying this equation to the matrix $B,$ we can take part 2):

$p \cdot B q' \le p \cdot B q$

and rewrite it like this:

$B^T p \cdot q' \le B^T p \cdot q$

Notice that $B^T p$ shows up on both sides now. So, we should start by computing this! We have

$B = \left( \begin{array}{rr} -1 & 1 \\ 1 & -1 \end{array} \right)$

so taking the transpose doesn’t actually do anything in this particular case:

$B^T= \left( \begin{array}{rr} -1 & 1 \\ 1 & -1 \end{array} \right)$

and we get:

$B^T p = \left( \begin{array}{rr} -1 & 1 \\ 1 & -1 \end{array} \right) \left( \begin{array}{r} 1/2 \\ 1/2 \end{array} \right) = \left( \begin{array}{r} 0 \\ 0 \end{array} \right)$

Hey! It’s the zero vector again! You should have guessed that was coming. So, the thing we’re trying to show:

$B^T p \cdot q' \le B^T p \cdot q$

simply boils down to

$0 \cdot q' \le 0 \cdot q$

which is true because both sides are zero.

Yay, we’re done! We found a Nash equilibrium! And the point of our last little calculation is that if A uses mixed strategy $p,$ B’s expected payoff is zero no matter what mixed strategy B uses. This is just the mirror image of what we saw before: if B uses mixed strategy $q,$ A’s expected payoff is zero no matter what mixed strategy A uses.

So, when both A and B are choosing heads or tails with 50% probabilities, independently, either one can unilaterally change their mixed strategy without improving their expected payoff. That’s a Nash equilibrium for you!

The coin-matching game

Just for fun, let me warn you about a scam that involves matching pennies. I’ll quote this article:

• Coin-matching game, Wikipedia.

A coin-matching game (also a coin smack or smack game) is a confidence trick in which two con artists set up one victim.

The first con artist strikes up a conversation with the victim, usually while waiting somewhere. The con artist suggests matching pennies (or other coins) to pass the time. The second con artist arrives and joins in, but soon leaves for a moment. The first con artist then suggests cheating. The victim, thinking they are going to scam the second con artist, agrees to match coins each time.

When the second con artist returns and begins losing, he accuses the two of cheating and threatens to call the police. The first con artist offers a sizable sum of hush money, and the victim pitches in. After the victim leaves, the two con artists split up the money extorted from the victim.

So, watch out if someone suggests playing ‘matching pennies’ with you! It could be legit, but if a second person joins in and starts placing bets on the two of you, it’s probably a coin smack!

For more con games, see:

• The Encylopedia of Scams.

I’m not trying to teach you how to con people! I’m trying to help you defend yourself. Of course the best way to avoid scams is a generally cautious, skeptical attitude, especially in any situation where someone seems to be helping you get money or get around the law. And don’t forget: successful con artists don’t usually look suspicious, like this:

They look and act trustworthy. As the saying goes:

The most important thing is sincerity. If you can fake that, you’ve got it made.

]]>