Skip to main content

Section 3.7 Undercut

This section requires you to be able to solve “large” systems of equations. You will be using the matrix techniques from Section 3.6. You are encouraged to use technology such as a graphing calculator or Sage.

As we saw in Section 3.5, an important part of game theory is the process of translating a game to a form that we can analyze.

Example 3.7.1. Undercut.

Each player chooses a number 1-5. If the two numbers don't differ by 1, then each player adds their own number to their score. If the two numbers differ by 1, then the player with the lower number adds both numbers to his or her score; the player with the higher number gets nothing. (From Douglas Hofstadter's Metamagical Themas.)

For example, suppose in round one Player 1 chooses 4; Player 2 chooses 4. Each player keeps their own number. The score is now 4-4. In the next round, Player 1 chooses 2, Player 2 chooses 5. The score would now be 6-9. In the third round Player 1 chooses 4, Player 2 chooses 5. Now Player 1 gets both numbers, making the score 15-9.

Choose an opponent and play Undercut several times. Keep track of the outcomes.

After playing Undercut with an opponent, try to devise a good strategy.

Just from playing Undercut several times, can you suggest a strategy for Player 1? What about for Player 2? For example, what number(s) should you play most often/ least often, or does it matter? Are there numbers you should never play? Does this game seem fair, or does one of the players seem to have an advantage? Explain your answers.

As we've seen before, a payoff matrix can help with analyzing a game.

Create a payoff matrix for Undercut. Note that your payoffs should have a score for each player.

Is this a zero-sum game? Explain.

Does there appear to be a pure strategy equilibrium for this game? Explain.

Let's assume we are going to play Undercut repeatedly. By the time you and your opponent are done playing, what should it mean to win the game?

How might we determine a “winner” for Undercut after playing several times?

Most likely, you said that someone will win the game if they have the most points. In fact, we probably don't care if the final score is 10-12 or 110-112. In either case, Player 2 wins. Since we will play this game several times, we do care about the point difference. For example, a score of 5-1 would be better for Player 1 than 5-3. So let's think about the game in terms of the point difference between the players in a given game. This is called the net gain. For example, with score of 5-1, Player 1 would have a net gain of 4.

Calculate the net gain for Player 1 for each of the three rounds in Example 3.7.1 in the beginning of this section.

Create a new payoff matrix for Undercut which uses the players' net gain for the payoff vectors.

Is this now a zero-sum game? Explain.

The method of using net gain to describe the payoffs to each player should be familiar from some of the really early examples where we turned constant-sum payoff vectors into zero-sum vectors. But note that the original form of this game wasn't even a constant-sum game! What we are really doing here is thinking about our payoffs not as points, but a win or loss relative to our opponent. Now that we have reframed Undercut as a zero-sum game, we can apply our methods for solving the game that we have seen in this chapter.

Is there a pure strategy equilibrium for this game? Explain.

Hint

Rather than looking at each option, you could compare the values for the pure maximin/ minimax strategies.

This game has one additional property that will help simplify our analysis. This game is symmetric, meaning the game looks the same to Players 1 and 2.

Give an example of another game which is symmetric. Give an example of a game which is not symmetric.

What is the expected payoff for a symmetric game? Explain your answer.

Hint

You might think about whether it is possible for a player to have an advantage in a symmetric game.

Hopefully, you determined that there is not a pure strategy equilibrium for Undercut. Thus, we would like to find a mixed strategy equilibrium. Since this is a \(5 \times 5\) game, we cannot use our graphical solution. We will need to rely on our expected value solution. We want to decide with what probability we should play each number. Let \(a, b, c, d, e\) be the probabilities with which Player 2 plays 1-5, respectively. For example, if Player 1 plays a pure strategy of 2, then the expected value for Player 1, \(E_1(2)\text{,}\) is \(-3a+0b+5c-2d-3e\text{.}\)

Write down the five equations that give Player 1's expected value for each of Player 1's pure strategies.

In Exercise 3.7.13, you should have determined that since this is a symmetric game, the expected value for each Player should be 0. Modify your equations to include this piece of information. It is important to recognize that this step greatly simplifies our work for the expected value method since we don't need to set the expected values equal to each other. HOWEVER, we can ONLY do this since we know the game is symmetric!

If we use that the game is symmetric, and hence the expected value of the game for each player must be 0 since neither player can have an advantage over the other, we do not need to set the equations equal to each other. We could not use this method earlier since we had no way of knowing the expected value of a general game.

We now have five equations and five unknowns. There is a sixth equation: we know that the probabilities must add up to 1. We can now solve for the equilibrium strategy!

Use matrices to solve the resulting system of six equations. Give the mixed strategy equilibrium for Player 2. What is the mixed strategy for Player 1?

Hint

Should it be different than the strategy for Player 2?

Based on your answer to Exercise 3.7.16, which number(s) should you play the most often? Which should you play the least? Are there any numbers that you should never play? Compare the mathematical solution to your conjectured solution for Exercise 3.7.3. Is there an advantage to knowing the mathematical solution?

You have now solved a rather complex two-person game. Try playing it with your friends and family. It may be difficult (or even impossible) to play randomly with the exact probabilties. It is also unlikely that your opponent will also be playing the equilibrium strategy, but can you use the solution to assure an advantage, or at least assure that your opponent doensn't have an advantage? Can you see the difference between an exact theoretical solution to a game, and a practical strategy for playing the game? In the next chapter we will see even more differences between theoretical and practical solutions to a game.

login