Is The Price Right?

The Riddler for October 16, 2020. The Express finds the chance of a three-way election going to a runoff, and the Classic solves a sequential “Price is Right” bidding game for the first guesser’s odds.

Riddler Express

Riddler City elects a mayor from three candidates. A candidate wins outright with more than $50\%$ of the vote; otherwise the top two go to a runoff. If the three vote shares are uniformly distributed (subject to summing to $100\%$), what is the probability of a runoff?

The Riddler, FiveThirtyEight, October 16, 2020(original post)

Solution

The three shares $(x, y, z)$ with $x + y + z = 1$ live uniformly on an equilateral triangle (the $2$-simplex). A runoff happens exactly when no share exceeds $\tfrac12$. The region where a particular share, say $x > \tfrac12$, is the corner triangle similar to the whole with half the side, hence $\tfrac14$ of the area; the three such corner triangles are disjoint (two shares cannot both exceed $\tfrac12$). So an outright majority occupies $3 \cdot \tfrac14 = \tfrac34$ of the simplex, and the runoff region is the central medial triangle, $$P(\text{runoff}) = 1 - \tfrac34 = \boxed{\tfrac14}.$$

The computation

Encode the model: sample shares uniformly on the simplex (sort two uniforms to split $[0,1]$ into three parts) and check whether all stay below $\tfrac12$.

import random
rng = random.Random(0)
trials, runoff = 2_000_000, 0
for _ in range(trials):
    a, b = sorted((rng.random(), rng.random()))
    shares = (a, b - a, 1 - b)               # uniform on the 2-simplex
    if max(shares) <= 0.5:
        runoff += 1
print(round(runoff / trials, 4))             # ~0.25

The simulation sits at $0.25$: a runoff happens a quarter of the time.

Riddler Classic

You and two others guess the price of an item, one at a time; the true price is uniform on $[0, 100]$. The winner is whoever guesses closest without going over; if all three overshoot, the lowest guess wins. You guess first, and everyone plays optimally, using the earlier guesses. What is your probability of winning?

The Riddler, FiveThirtyEight, October 16, 2020(original post)

Solution

Work backwards. After the first two guesses split $[0, 100]$ into three intervals (below both, between, above both), the third player simply claims whichever interval is widest, by guessing $0$, a hair above the lower guess, or a hair above the higher guess. Knowing this, the second player picks a guess to maximise their own interval, and you, guessing first, anticipate both.

The first guesser’s best move is $A = \tfrac23 \cdot 100 \approx 66.7$. The second then guesses $B = \tfrac13 \cdot 100 \approx 33.3$, which cuts $[0,100]$ into three intervals of equal width $\tfrac{100}{3}$. With all three gaps equal, the last player is indifferent and takes exactly one third, leaving one third for each of you. So every player, including the first, wins with probability $$\boxed{\tfrac13}.$$ Any other opening lets the later players, who see your guess, carve out more than a third at your expense, so $\tfrac13$ is the best you can guarantee.

The computation

Encode the payoff: for fixed guesses, integrate over the uniform price to get each player’s win probability. Then verify that the equilibrium guesses $(\tfrac{200}{3}, \tfrac{100}{3})$ make all three intervals equal, so whichever gap the last player grabs, everyone gets $\tfrac13$.

def shares(gA, gB, gC):
    players = [('A', gA), ('B', gB), ('C', gC)]
    cuts = sorted({0.0, 100.0, gA, gB, gC})
    win = {'A': 0.0, 'B': 0.0, 'C': 0.0}
    for lo, hi in zip(cuts, cuts[1:]):
        t = (lo + hi) / 2                       # a representative price
        under = [(g, who) for who, g in players if g <= t]
        winner = max(under)[1] if under else min(players, key=lambda x: x[1])[0]
        win[winner] += (hi - lo) / 100
    return win

A, B, eps = 200 / 3, 100 / 3, 1e-9
print(round(B, 1), round(A - B, 1), round(100 - A, 1))   # 33.3 33.3 33.3
for C in (0.0, B + eps):              # last player guesses low, e.g. 0 (per official)
    s = shares(A, B, C)
    print({k: round(v, 3) for k, v in s.items()})        # 1/3 each

The three gaps are equal, so the last player’s natural low guess leaves each player, the first included, a $\tfrac13$ chance.