Game Theory (Part 14)

## Game Theory (Part 14)

#### John Baez

Here is the first test in our game theory course. If you're following along on this blog, you can do it and then look at the answers below.

### Definitions

1. Define a Nash equilibrium for a 2-player normal form game.

2. Define the expected value of some function with respect to some probability distribution.

### Proof

3. Suppose $$A$$ and $$B$$ are the payoff matrices for 2-player normal form game. Prove that if $$(i,j)$$ is a Nash equilibrium, there cannot exist a choice $$i'$$ for player A that strictly dominates choice $$i.$$

### 2-Player normal form games

Consider this 2-player normal form game:

$$\begin{array}{rrr} (-2,1) & (4,2) & (2,-5) \\ (2,3) & (-6,2) & (5,3) \\ (1,0) & (2,-4) & (4,-3) \end{array}$$

4. Find all the Nash equilibria. Draw a box around each Nash equilibrium.

For problems 5-8 do not simplify your answers by working out the binomial coefficients, etc.

### Probabilities

5. If you draw 3 cards from a well-shuffled standard deck, what is the probability that at least 2 are hearts?

6. If you flip 4 fair and independent coins, what is the probability that exactly 2 land heads up?

### Expected values

7. Suppose you pay $2 to enter a lottery. Suppose you have a 1% chance of winning$100, and otherwise you win nothing. What is the expected value of your payoff, including your winnings but also the money you paid?

8. Suppose you draw two cards from a well-shuffled standard deck. Suppose you win $100 if you get two aces,$10 if you get one ace, and nothing if you get no aces. What is your expected payoff?

### Extra credit

About how many ways are there to choose 3 atoms from all the atoms in the observable universe? Since this question is for extra credit, I'll make it hard: I'll only accept answers written in scientific notation, for example $$2 \times 10^{50}.$$

And here are the answers to the first test.

### Definitions

1. Given a 2-player normal form game where A's payoff is $$A_{ij}$$ and B's payoff is $$B_{ij}$$, 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}.$$

2. The expected value of a function $$f : X \to \mathbb{R}$$ with respect to a probability distribution $$p$$ on the finite set $$X$$ is

$$\sum_{i \in X} f(i) p_i$$

Note that a good definition makes it clear what term is being defined, by writing it in boldface or underlining it. Also, it's best if all variables used in the definition are explained: here they are $$f, X$$ and $$p.$$

### Proof

3. Theorem. Suppose $$A$$ and $$B$$ are the payoff matrices for 2-player normal form game. If $$(i,j)$$ is a Nash equilibrium, there cannot exist a choice $$i'$$ for player A that strictly dominates choice $$i$$.

Proof. Suppose that $$(i,j)$$ is a Nash equilibrium. Then

$$A_{ij} \ge A_{i' j}$$

for any choice $$i'$$ for player A. On the other hand, if choice $$i'$$ strictly dominates choice $$i$$, then

$$A_{i'j} > A_{i j}$$

This contradicts the previous inequality, so there cannot exist a choice $$i'$$ for player A that strictly dominates choice $$i$$. █

Note that the really good way to write a proof involves:

• First writing "Theorem" and stating the theorem.
• Saying "Proof" at the start of the proof.
• Giving an argument that starts with the hypotheses and leads to the conclusion.
• Marking the end of the proof with █ or "Q.E.D.".

### 2-Player normal form games

4. In this 2-player normal form game, the three Nash equilibria are marked with boxes:

$$\begin{array}{rrr} (-2,1) & \boxed{(4,2)} & (2,-5) \\ \boxed{(2,3)} & (-6,2) & \boxed{(5,3)} \\ (1,0) & (2,-4) & (4,-3) \end{array}$$

### Probabilities

5. If you draw 3 cards from a well-shuffled standard deck, what is the probability that at least 2 are hearts?

$$\displaystyle{ \frac{\binom{13}{2} \binom{39}{1}}{\binom{52}{3}} + \frac{\binom{13}{3} \binom{39}{0}}{\binom{52}{3}} }$$

since there are:

• $$\binom{52}{2}$$ ways to choose 3 cards, all equally likely,

• $$\binom{13}{2}$$ ways to choose 2 hearts and $$\binom{39}{1}$$ ways to chose 1 non-heart, and

• $$\binom{13}{3}$$ ways to choose 2 hearts and $$\binom{39}{0}$$ ways to chose 0 non-hearts.

$$\displaystyle{ \frac{\binom{13}{2} \cdot 39 }{\binom{52}{2}} + \frac{\binom{13}{3}} {\binom{52}{2}}}$$
This is equal since $$\binom{39}{0} = 1$$ and $$\binom{39}{1} = 39.$$

6. If you flip 4 fair and independent coins, what is the probability that exactly 2 land heads up?

$$\displaystyle{ \frac{\binom{4}{2}}{2^4} }$$

since there are $$2^4$$ possible ways the coins can land, all equally likely, and $$\binom{4}{2}$$ ways to choose 2 of the 4 coins to land heads up.

### Expected values

7. Suppose you pay $2 to enter a lottery. Suppose you have a 1% chance of winning$100, and otherwise you win nothing. What is the expected value of your payoff, including your winnings but also the money you paid?

$$0.01 \cdot \98 \quad + \quad 0.99 \cdot (-\2)$$

$$0.01 \cdot \ 100 \quad + \quad 0.99 \cdot \ 0 \quad - \quad \ 2$$
Of course these are equal.

8. Suppose you draw two cards from a well-shuffled standard deck. Suppose you win $100 if you get two aces,$10 if you get one ace, and nothing if you get no aces. What is your expected payoff?

$$\displaystyle{ \frac{\binom{4}{2} \binom{48}{0}}{\binom{52}{2}} \cdot 100 \quad + \quad \frac{\binom{4}{1} \binom{48}{1}}{\binom{52}{2}} \cdot 10 \quad + \quad \frac{\binom{4}{0} \binom{48}{2}}{\binom{52}{2}} \cdot 0 }$$

since $$\binom{4}{n} \binom{48}{3-n}$$ is the number of ways to pick $$n$$ aces and $$3-n$$ non-aces. Of course we can also leave off the last term, which is zero:

$$\displaystyle{ \frac{\binom{4}{2} \binom{48}{0}}{\binom{52}{2}} \cdot \ 100 \quad + \quad \frac{\binom{4}{1} \binom{48}{1}}{\binom{52}{2}} \cdot \ 10 }$$

Since $$\binom{48}{0} = 1$$ we can also write this as

$$\displaystyle{ \frac{\binom{4}{2}}{\binom{52}{2}} \cdot \ 100 \quad + \quad \frac{\binom{4}{1} \binom{48}{1}}{\binom{52}{2}} \cdot \ 10 }$$

Or, since $$\binom{4}{1} = 4$$ and $$\binom{48}{1} = 48$$ we can write this as

$$\displaystyle{ \frac{\binom{4}{2}}{\binom{52}{2}} \cdot \ 100 \quad + \quad \frac{4 \cdot 48}{\binom{52}{2}} \cdot \ 10 }$$

But I said not to bother simplifying the binomial coefficents.

### Extra credit

About how many ways are there to choose 3 atoms from all the atoms in the observable universe? Since this question is for extra credit, I'll make it hard: I'll only accept answers written in scientific notation, for example $$2 \times 10^{50}.$$

Answer. In class I said the number of atoms in the observable universe is about $$10^{80},$$ and I said I might put this on the test. So, the answer is

$$\begin{array}{ccl} \displaystyle{ \binom{10^{80}}{3}} &=& \displaystyle{ \frac{10^{80}(10^{80} - 1)(10^{80} - 2)}{3 \cdot 2 \cdot 1} } \\ \\ &\approx& \displaystyle{ \frac{10^{80} \cdot 10^{80} \cdot 10^{80}}{6} } \\ \\ &=& \displaystyle{ \frac{10^{240}}{6} } \\ \\ &\approx & 1.667 \times 10^{239} \end{array}$$

Note that the question asked for an approximate answer, since we don't know exactly how many atoms there are in the observable universe. The right answer to a question like this gives no more decimal places than we have in our data, so $$1.667 \times 10^{239}$$ is actually too precise! You only have one digit in the data I gave you, so a better answer is

$$\mathbf{ 2 \times 10^{239} }$$

Since the figure $$10^{80}$$ is very approximate, another correct answer is

$$\mathbf{ 10^{239} }$$