Best-Of-Seven and the First-Price Auction

The Riddler for June 2, 2017. The Express is a clean expected-length calculation for a best-of-seven series under independent games. The Classic is a textbook Bayesian game: a sealed first-price auction with values drawn uniformly on $[0, V]$, asking for the Nash equilibrium bidding strategy with two bidders, with $N$ bidders, and in the all-pay variant.

Riddler Express

How many games would we expect to be needed to complete a best-of-seven series if each team has a $50$ percent chance of winning each individual game? How about if one team has a $60$ percent chance of winning each game? How about $70\%$?

The Riddler, FiveThirtyEight, June 2, 2017(original post)

Solution

Let $p$ be the probability that team $A$ wins any given game; $q = 1 - p$ is the probability that $B$ wins. Games are independent.

The series lasts $k$ games (for $k \in \{4, 5, 6, 7\}$) exactly when one team reaches its fourth win on game $k$. For team $A$ to win $4$–$(k-4)$, game $k$ itself must be one of $A$’s wins (the clinching game), and among the first $k-1$ games $A$ must have won exactly $3$ and lost $k-4$. There are $\binom{k-1}{3}$ orderings of those first $k-1$ games, each with probability $p^3 q^{k-4}$, and game $k$ contributes a further factor $p$. So $$\Pr(\text{series ends }k, A\text{ wins}) \;=\; \binom{k-1}{3}\, p^{4}\, q^{k-4},$$ and symmetrically for $B$, $$\Pr(\text{series ends }k, B\text{ wins}) \;=\; \binom{k-1}{3}\, q^{4}\, p^{k-4}.$$ The expected length is then $$\mathbb{E}[L] \;=\; \sum_{k=4}^{7} k \binom{k-1}{3}\bigl(p^{4} q^{k-4} + q^{4} p^{k-4}\bigr).$$ Plug in $p = 0.5$ (so $q = 0.5$): $$\begin{aligned} \mathbb{E}[L] &= 4 \cdot 2 \cdot 0.5^4 + 5 \cdot 8 \cdot 0.5^5 + 6 \cdot 20 \cdot 0.5^6 + 7 \cdot 40 \cdot 0.5^7\\ &= 0.5 + 1.25 + 1.875 + 2.1875 \;=\; 5.8125. \end{aligned}$$ For $p = 0.6$ (so $q = 0.4$), $$\begin{aligned} \mathbb{E}[L] \;=\;& 4(p^4 + q^4) + 20(p^4 q + q^4 p)\\ &+ 60(p^4 q^2 + q^4 p^2) + 140(p^4 q^3 + q^4 p^3), \end{aligned}$$ which evaluates to approximately $5.6973$. For $p = 0.7$ the analogous sum evaluates to approximately $5.3780$. $$\boxed{\,\mathbb{E}[L] \;=\; 5.8125,\; 5.6973,\; 5.3780 \text{ at } p = 0.5,\, 0.6,\, 0.7.\,}$$

The series shortens as $p$ moves away from $\tfrac12$ because the more imbalanced the matchup, the likelier it ends in a sweep or near-sweep.

The computation

Encode the actual rule: flip a biased coin until one side has won four games, and average the length over many independent series.

import random

def length(p, rng):
    a = b = n = 0
    while a < 4 and b < 4:
        n += 1
        if rng.random() < p: a += 1
        else:                 b += 1
    return n

rng = random.Random(0)
TRIALS = 300_000
for p in (0.5, 0.6, 0.7):
    avg = sum(length(p, rng) for _ in range(TRIALS)) / TRIALS
    print(f"p={p}: empirical E[length] = {avg:.4f}")
# p=0.5: empirical E[length] = 5.8114
# p=0.6: empirical E[length] = 5.6985
# p=0.7: empirical E[length] = 5.3786

The simulated averages match the closed-form values to three decimals.

Riddler Classic

You and a single arch nemesis bid in a sealed first-price auction for a painting. Each of you draws a private valuation uniformly at random from $[0, V]$, where $V = \$100{,}000{,}000$. The distribution and rules are common knowledge. You submit a sealed bid; whoever bids higher wins and pays their bid. If your valuation is $X$, how much should you bid? Extra credit: what if there are $N$ bidders in the room? Extra extra credit: in an all-pay auction, where every bidder pays whatever they wrote down regardless of winning, how much should everyone bid?

The Riddler, FiveThirtyEight, June 2, 2017(original post)

Solution

This is a Bayesian game: each bidder knows her own valuation but only the distribution of the others’. We hunt for a symmetric Bayesian Nash equilibrium: a bidding rule $b(\cdot)$ such that, if every opponent uses $b$, then $b$ is each bidder’s best response.

The two boundary observations. Bidding more than your valuation is dominated: at best you break even, more often you overpay. Bidding exactly your valuation is also dominated: winning then yields zero surplus. The optimal bid lies strictly between $0$ and your valuation, and you trade win probability against surplus per win.

Two-bidder case via linear ansatz. Suppose the opponent uses $b(y) = \alpha y$ for some $\alpha \in (0, 1)$. Your opponent’s bid is then uniform on $[0, \alpha V]$. If you bid $b$ with valuation $x$, your expected payoff is $$\pi(b; x) \;=\; \underbrace{\Pr(\text{your bid wins})}_{\Pr(\alpha Y < b)\,=\,b/(\alpha V)} \cdot \underbrace{(x - b)}_{\text{surplus}} \;=\; \frac{b\,(x - b)}{\alpha V}.$$ This is a concave quadratic in $b$; the first-order condition gives $$\frac{\partial \pi}{\partial b} \;=\; \frac{x - 2b}{\alpha V} \;=\; 0 \quad\Longrightarrow\quad b \;=\; \frac{x}{2}.$$ For self-consistency we need your best response to coincide with the opponent’s rule, so $\alpha = 1/2$. The equilibrium is $$\boxed{\,b(X) \;=\; \frac{X}{2}.\,}$$ The notable feature: the equilibrium bid is independent of $V$. The factor $V$ cancels because both the win probability and the strategy scale linearly with valuations.

Extra credit: $N$ bidders. Suppose the other $N - 1$ bidders each use $b(y) = \alpha y$. Each opponent’s bid is uniform on $[0, \alpha V]$ and they are independent. The probability that all of them bid below $b$ is $(b / (\alpha V))^{N-1}$. Your expected payoff is $$\pi(b; x) \;=\; \left(\frac{b}{\alpha V}\right)^{N-1}\, (x - b).$$ Differentiate (or use logarithmic derivative): setting $\partial \pi / \partial b = 0$ gives $$\frac{N-1}{b}\,(x - b) \;-\; 1 \;=\; 0 \quad\Longrightarrow\quad b \;=\; \frac{N-1}{N}\, x.$$ Self-consistency forces $\alpha = (N-1)/N$: $$\boxed{\,b(X) \;=\; \frac{N-1}{N}\, X.\,}$$ More bidders means stiffer competition; bids climb toward the valuation as $N \to \infty$, and the surplus per win shrinks accordingly.

Extra extra credit: all-pay auction with $N$ bidders. Now everyone pays their bid whether or not they win. Look for a symmetric, strictly increasing equilibrium $b(\cdot)$.

If everyone else plays $b$, a bidder of true valuation $v$ who pretends to have valuation $z$ (bids $b(z)$) gets expected payoff $$\pi(z; v) \;=\; \Pr(\text{all other } z' < z)\, v \;-\; b(z) \;=\; \left(\frac{z}{V}\right)^{N-1} v \;-\; b(z).$$ The first term is the win probability times the value won; the second is the bid paid regardless. Equilibrium requires $z = v$ to maximise $\pi(z; v)$, so $$\begin{aligned} \left.\frac{\partial \pi}{\partial z}\right|_{z=v} \;&=\; (N-1)\,\frac{v^{N-1}}{V^{N-1}} \;-\; b'(v) \;=\; 0\\ \Longrightarrow\quad b'(v) \;&=\; \frac{(N-1)\, v^{N-1}}{V^{N-1}}. \end{aligned}$$ With boundary condition $b(0) = 0$, integrate: $$\boxed{\,b(X) \;=\; \frac{N-1}{N}\,\frac{X^{N}}{V^{N-1}}.\,}$$ For $N = 2$, $b(X) = X^2 / (2V)$: a bidder valuing the painting at $X = V/2$ bids only $V/8$, much less than the $V/4$ she would bid in the first-price auction. The reason: paying win or lose makes overbidding far more painful, so equilibrium bids are heavily compressed.

A sanity check via expected surplus. In the first-price auction with $N = 2$, your expected utility before learning your value is $$\mathbb{E}\,\pi \;=\; \int_{0}^{V} \frac{1}{V} \cdot \frac{x}{2} \cdot \frac{x}{V}\, dx \;=\; \frac{1}{V^{2}} \int_{0}^{V} \frac{x^{2}}{2}\, dx \;=\; \frac{V}{6},$$ where $\Pr(\text{win}|x) = x/V$ (opponent has lower value, equivalently lower bid) and surplus is $x/2$. Revenue equivalence predicts the all-pay auction yields the same expected utility, which matches the Monte Carlo computation below.

The computation

We confirm two distinct claims: (i) $b(X) = (N-1)X/N$ is a best response when all others use it (first-price), and (ii) the equilibrium expected utility matches $V/6$ for $N=2$ in both auction formats (revenue equivalence).

1. Draw $N$ valuations uniformly on $[0, V]$. Apply the candidate equilibrium bid $b(x) = (N-1)x/N$ for each.

2. Tally wins (highest bid takes the painting) and net utilities.

3. For best-response check: hold $N - 1$ opponents at the equilibrium and vary your bid; confirm the maximum lands at the predicted value.

import random
V = 100_000_000

def eq_utility(N, trials, rng):
    """All N bidders use b(x) = (N-1)x/N; average winner's surplus."""
    tot = 0.0
    for _ in range(trials):
        vals = [rng.uniform(0, V) for _ in range(N)]
        bids = [(N-1)*v/N for v in vals]
        i = bids.index(max(bids))
        tot += vals[i] - bids[i]
    return tot / trials

rng = random.Random(0)
for N in (2, 3, 5):
    u = eq_utility(N, 200_000, rng)
    # winner's expected surplus = E[max(X_1,...,X_N) / N]
    # for N=2 that is (1/2)(2V/3) = V/3 = 33,333,333
    print(f"N={N}: avg winner surplus = {u:.2f}")

# Best-response check at N=2, x = V/2
def br_check(N, x, rng):
    best = (-1.0, None)
    for frac in [0.30, 0.40, 0.45, (N-1)/N, 0.55, 0.60, 0.70]:
        b_me = frac * x
        u = 0.0
        T = 200_000
        for _ in range(T):
            others = [rng.uniform(0, V) for _ in range(N-1)]
            obids = [(N-1)*y/N for y in others]
            if b_me > max(obids):
                u += (x - b_me)
        u /= T
        if u > best[0]: best = (u, frac)
    return best

print(f"N=2 best-response fraction (predicted 0.500): {br_check(2, V/2, rng)[1]}")
print(f"N=3 best-response fraction (predicted 0.667): {br_check(3, V/2, rng)[1]}")
# N=2: avg winner surplus = 33329015.18   (matches V/3 = 33333333)
# N=3: avg winner surplus = 24988709.23   (matches V/4 = 25000000)
# N=5: avg winner surplus = 16660330.67   (matches V/6 = 16666667)
# N=2 best-response fraction (predicted 0.500): 0.5
# N=3 best-response fraction (predicted 0.667): 0.6666666666666666

The best-response check picks out exactly the analytic fraction $(N-1)/N$ in each case, and the equilibrium winner surplus tracks the closed-form prediction. The all-pay calculation in the Solution agrees with the revenue-equivalence prediction $V/6$ for $N = 2$.