Is the Price Right?

In the game show “The Price is Right”, contestants try to guess the price of a prize without going over. Assume you’re a contestant, and you somehow know the exact distribution of prices for the prize. Would you be able to win?

Pure Strategy Equilibrium

Let $V \sim \mathcal{D}$ be a random variable representing the true value of the prize, with CDF $F(v)$, supported on $[0, v_{\text{max}})$ (we assume $F$ is strictly increasing and the corresponding PDF is continuous for simplicity). Suppose we’re playing with two contestants, who simultaneously makes guesses $x_1, x_2 \in [0, v_{\text{max}})$. They receive a reward of 1 if they are closest to the randomly selected price $v$ without going over, and 0 otherwise (we’ll ignore ties throughout the analysis). This leads to symmetric (expected) payoff functions

$$ f_1(x_1, x_2) = \begin{cases} 1 - F(x_1) & x_1 > x_2 \\ F(x_2) - F(x_1) & x_1 < x_2 \\ \end{cases} $$

and

$$ f_2(x_1, x_2) = \begin{cases} F(x_1) - F(x_2) & x_1 > x_2 \\ 1 - F(x_2) & x_1 < x_2 \\ \end{cases} $$

You can play around with different strategies below to get a sense for how the payoff works:

Note that the payoff depends only on $F(x)$. To simplify, we’ll assume $F$ has an inverse, allowing us to express each player’s action as a quantile: $q_1 = F(x_1)$ and $q_2 = F(x_2)$. Once we find the optimal quantile $q \in [0, 1]$, we can compute $F^{-1}(q) = x$ to get the correct bid. This will make it easier to work with arbitrary price distributions $\mathcal{D}$.

Let’s analyze the best response function for each contestant. This is a concept from game theory that finds the optimal choice for one player, given what the other player has chosen. When an action is a mutual best response, neither player would be choose to play differently, given what the other player has played. This leads to Nash Equilibrium. So finding the best response for each player is the first step to determining if an equilibrium solution is possible.

We seek to prove that there’s no best response to any opponent moves. For any proposed best response to Player 2’s choice, we can always find a Player 1 choice that’s better. If the proposed best response is above Player 2’s, you’d do better if you dropped your guess so it’s just a little bit higher than Player 2, to minimize your risk of going over while still ensuring you’re closer to the true price than Player 2. On the other hand, if the proposed best response is below Player 2’s, then you’d do better dropping your guess even further to more fully capitalize on the times when Player 2 goes over.

Proof

Theorem: Under the above assumptions, no pure strategy Nash Equilibrium exists.

Given $x_2$, suppose by way of contradiction that there’s some $x_1 \in \beta_1(x_2)$. This leads us to two cases:

(i) If $x_1 > x_2$, we can always reduce $x_1$ to something arbitrarily close to $x_2$ to improve the payoff. Fix some $\epsilon > 0$ such that $x_2 + \epsilon < x_1$. Then $f_1(x_1, x_2) = 1 - F(x_1) < 1- F(x_2 + \epsilon) = f_1(x_2 + \epsilon, x_2)$ (note we used the strict monotinicity of $F$ here).

(ii) On the other hand, if $x_1 < x_2$, we payoff would only increase if $x_1$ were reduced. Fix some $\epsilon > 0$. We have $f_1(x_1, x_2) = F(x_2) - F(x_1) < F(x_2) - F(x_1 - \epsilon) = f_1(x_1 - \epsilon, x_2)$.

In either case, there’s a better strategy than $x_1$ when Player 2 plays $x_2$, so $x_1 \notin \beta_1(x_2)$. Hence no best response $\beta_1(x_2)$ is attained. By symmetry of the payoff functions, the same applies to $\beta_2(x_1)$.

Mixed Strategy Equilibrium

It’s tempting to stop there and say there’s no optimal way to play the game. But Game Theory gives us another option: mixed strategy equilibria. The idea is that even in games where there’s no pure mutual best response, we can still find probability distributions over potential actions such that if each player chooses their actions according to their distribution, we can reach equilibrium.

A classic example is rock paper scissors. If you play rock and your opponent plays paper, you’ll regret not doing scissors instead. In fact, no matter what, the losing player will wish they’d chosen a different strategy. However, if both players choose to select randomly between rock/paper/scissors, there’s no more room for regret. Even though a player might wish they’d chosen differently in an individual loss, they still know that they couldn’t have chosen a better strategy to maximize their overall expected payoff.

The key idea in finding a mixed strategy equilibrium is ensuring you’re indifferent to the action you choose, meaning all actions have equal expected value for you. If this wasn’t the case, you’d be better off playing a different strategy that doesn’t leave your action up to chance. We can solve for indifference by finding a distribution over your opponent’s actions that make it so your expected value is constant. Put mathematically, this means solving

$$ \mathbb{E}_{q_2}\big[ f_1(q_1, q_2) \big] = c, \quad \forall q_1 $$

In integral form, this means

$$ \int_0^1 f_1(q_1, q_2) g(q_2) dq_2 \\ = \int_0^{q_1} (1 - q_1) g(q_2) dq_2 + \int_{q_1}^1 (q_2 - q_1) g(q_2) dq_2 = c $$

Differentiating both sides with respect to $q_1$ gives

$$ g(q_1) - q_1 g(q_1) - \int_0^1 g(q_2) dq_2 = 0 $$

Since $g$ must be a PDF that integrates to 1, we can simplify to $g(q_1)(1 -q_1) = 1$, implying $g(q_1) = \frac{1}{1-q_1}$. Note that this doesn’t integrate to 1 over the full $[0, 1]$ domain of our quantile support, so we need to set it to 0 some places. We can decide where to set it to 0 by going back to our payoff function and finding the support where our PDF maximizes our payoff. Mathematically, we want to choose some $a$ and $b$ such that $\int_a^b \frac{1}{1-q} dq = 1$.

Evaluating the integral gives $\ln\left(\frac{1-a}{1-b}\right)=1$, so $b = \frac{a + e - 1}{e}$. Plugging this back into our original payoff function gives:

$$ \mathbb{E_{q_2}} \big[ f_1(q_1, q_2) \big] =\int_a^{q_1} \frac{1 - q_1}{1 - q_2} dq_2 + \int_{q_1}^{\frac{a + e - 1}{e}} \frac{q_2 - q_1}{1 - q_2} dq_2 = \frac{1-a}{e} $$

So to maximize our payoff, we should minimize $a$, leading to $a = 0$, $b = \frac{e-1}{e} = 1 - e^{-1}$. So our final mixed strategy distribution is:

$$ g(q) = \begin{cases} \frac{1}{1-q} & 0 \leq q < 1 - e^{-1} \\ 0 & \text{otherwise} \end{cases} $$

This gives us an expected payoff of $e^{-1} \approx 0.368$.

Analysis

To see how well this strategy performs, I ran a simulation where two players play against each other 100,000 times. Player 1 uses the optimal mixed strategy above, while Player 2 bids a fixed quantile. The price distribution is $V \sim \mathcal{N}(550, 300)$ (truncated).

I thought this would be my moment! I’d show how the equilbrium strategy smokes any pure strategy, and move on. However, that’s not what happened at all. Around the 33-68 percentile range (exactly where a normal player would be guessing), the pure strategy performs better than the mixed strategy! How did that happen?

It turns out that because it’s possible for both players to go over, this isn’t a zero-sum game. Because of that, the equilibrium strategy isn’t necessarily dominant. It’s only optimal against a player who’s also using the equilibrium strategy. That doesn’t mean it’s useless though.

The equilibrium strategy shines because it puts a cap on the win rate of your opponent. No matter what strategy your opponent plays, they cannot win more than ~36.8% of the time. In the rock paper scissors example from earlier, you’ll only win 1/3 of the time against someone who plays rock, so it might seem like a paper-only strategy would be better. But that would remove the protection you get from playing the mixed strategy, which guarantees you’re unpredictable enough to not get defeated more than 1/3 of the time.

Conclusion

If you actually were to get on the show, it’d probably be best to go for either the 50 or 0 percentile strategy, as described above.