<![CDATA[Game Theory (Part 14)]]>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 “Q.E.D.” or “█” or something similar.

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?

Answer. One correct answer is

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

Another correct answer is

\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?

Answer. The probability

\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?

Answer. One correct answer is

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

Another correct answer is

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?

Answer. One correct answer is

\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 + \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} }
]]>