Rock, Paper, Scissors, Double Scissors

Riddler Express

In rock-paper-scissors-double-scissors, the three classical moves interact in the standard way, double scissors defeat regular scissors, and double scissors cut paper and are smashed by rock. A match is the first to two wins (ties replay the throw). One exception: if your opponent throws paper and you throw regular scissors, you immediately win the match regardless of the score. What is the optimal mixed strategy at each possible score $(0\text{-}0, 1\text{-}0, 0\text{-}1, 1\text{-}1)$? What is your chance of winning from a $1\text{-}0$ lead with both players optimal?

The Riddler, FiveThirtyEight, September 29, 2017(original post)

Solution

The game is symmetric, so any score $(s_y, s_o)$ with $s_y = s_o$ has equal value for both players, that is $\tfrac12$. The $1\text{-}1$ score is even simpler: there is exactly one throw left, and double scissors dominates regular scissors for the leading player. This holds at any score where the special paper-scissors rule cannot help. Once a player already has one win, the auto-win bonus is irrelevant (one more throw and the match is over), and double scissors beats everything that scissors does plus regular scissors itself. So at $1\text{-}1$ neither player throws regular scissors, and the game reduces to ordinary rock-paper-double-scissors, with equilibrium $(\tfrac13, \tfrac13, \tfrac13)$ on rock, paper, double scissors and value $\tfrac12$.

That leaves $1\text{-}0$ (your lead) and $0\text{-}0$. Write $X$ for your winning chance from $1\text{-}0$ with optimal play on both sides, so that $1 - X$ is your chance from $0\text{-}1$. We will compute $X$ from a single matrix game.

The $1\text{-}0$ subgame. You already have one win, so double scissors dominates regular scissors for you: you choose among rock $R$, paper $P$, double scissors $DS$. Your opponent still trails $0\text{-}1$ and may benefit from throwing regular scissors (against your paper it auto-wins the match), so the opponent chooses among $R, P, S, DS$. Each throw resolves one of three ways:

• A tie returns to $1\text{-}0$ and is worth $X$.

• You win the throw and reach $2\text{-}0$, worth $1$.

• Your opponent wins the throw, ties the match at $1\text{-}1$, worth $\tfrac12$.

The auto-win exception applies in two cells: if you throw paper and the opponent throws scissors, the opponent auto-wins (value $0$). The full $4 \times 3$ payoff matrix is given below, rows for the opponent’s throw and columns for yours:

Both players randomise. The value of this $4 \times 3$ matrix game (you maximising over the columns, the opponent minimising over the rows) must equal $X$ by self-consistency. Solving the linear-programming equilibrium and self-consistently fixing $X$ gives $$X \approx 0.7267.$$ $$\boxed{\,X \approx 0.73.\,}$$

Equilibrium strategies at $1\text{-}0$. The same LP returns the mixing probabilities. Your optimal mix on $(R, P, DS)$ is $$(0.40,\ 0.27,\ 0.33),$$ and your opponent’s optimal mix on $(R, P, S, DS)$ is $$(0.55,\ 0.25,\ 0.21,\ 0).$$ Two features of the opponent’s mix are worth pausing on. First, the trailing opponent should never throw double scissors here: at $0\text{-}1$ a tie at $1\text{-}1$ is the best outcome of the round, and double scissors only ties when you throw double scissors. Second, regular scissors gets a healthy weight ($0.21$), driven entirely by the auto-win against your paper.

The $0\text{-}0$ subgame. Both players use all four throws. Each round’s outcome is one of: tie (replay, worth $\tfrac12$ by symmetry); you win the throw and lead $1\text{-}0$, worth $X \approx 0.73$; opponent wins and you trail $0\text{-}1$, worth $1 - X \approx 0.27$; or the auto-win exception fires. The matrix is symmetric in the sense that swapping your throw and the opponent’s throw transposes the payoffs around $\tfrac12$, so the value of the $0\text{-}0$ matrix game is exactly $\tfrac12$. Solving the matrix LP gives the equilibrium mix on $(R, P, S, DS)$, $$(0.52,\ 0.24,\ 0.24,\ 0).$$ Both players use the same mix by symmetry. Double scissors gets weight zero at $0\text{-}0$. This is the puzzle’s neat observation: nobody should ever open with double scissors, and nobody should ever play regular scissors after gaining a win. Regular scissors stays in the toolkit only when the auto-win exception is in reach, and double scissors only when the special rule is dead.

The computation

Encode the recursive matrix games and solve them as linear programs. We fix $X$ self-consistently for the $1\text{-}0$ matrix (the only one whose value is itself $X$), then solve the $0\text{-}0$ matrix to read off its equilibrium.

1. Build the $4 \times 3$ payoff matrix for the $1\text{-}0$ subgame as a function of $X$.

2. Solve the LP for the value $v(X)$ as a function of $X$.

3. Iterate $X \leftarrow v(X)$ until convergence.

4. Build the $4 \times 4$ payoff matrix for the $0\text{-}0$ subgame using the converged $X$.

5. Solve its LP and read off the equilibrium mix and value.

import numpy as np
from scipy.optimize import linprog

def solve_max(M):                                   # value & col-strategy
    rows, cols = M.shape
    c = np.zeros(cols + 1); c[-1] = -1
    A_ub = np.hstack([-M, np.ones((rows, 1))])
    b_ub = np.zeros(rows)
    A_eq = np.zeros((1, cols + 1)); A_eq[0, :cols] = 1
    res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=[1.0],
                  bounds=[(0, 1)] * cols + [(None, None)], method="highs")
    return -res.fun, res.x[:cols]

def M10(X):                                # rows opp(R,P,S,DS), cols you(R,P,DS)
    return np.array([
        [X,   1,   0.5],
        [0.5, X,   1.0],
        [1,   0,   1.0],
        [1,   0.5, X  ],
    ])

X = 0.5
for _ in range(200):
    v, _ = solve_max(M10(X)); X = v
print(f"X = {X:.4f}")                                # 0.7267

v10, you10 = solve_max(M10(X))
print("you 1-0 (R,P,DS):", you10.round(2))          # [0.40 0.27 0.33]

The same routine, applied to the $4 \times 4$ matrix at $0\text{-}0$ (entries $X$ for your-throw wins, $1 - X$ for opp-throw wins, $\tfrac12$ for ties, $1$ for your-scissors-vs-opp-paper, $0$ for opp-scissors-vs-your-paper), returns value $0.5000$ and mix $(R, P, S, DS) \approx (0.52, 0.24, 0.24, 0)$, exactly the values quoted above.

Riddler Classic

Two coins look and feel identical. One is fair (heads with probability $0.5$); the other is doctored (heads with probability $0.6$). You flip both at once, one per hand, the same number of times. How many flips do you need to give yourself a $95\%$ chance of correctly identifying the doctored coin? Extra credit: replace $0.6$ by a general $P$.

The Riddler, FiveThirtyEight, September 29, 2017(original post)

Solution

After $n$ paired flips, let $K$ be the number of heads on the doctored coin and $J$ the number on the fair coin. The rule is the obvious one: declare the coin with more heads to be the doctored one. We are correct exactly when $K > J$ (ties go against you in the worst case; the official solution treats them as failures, and we follow suit), so the question becomes the smallest $n$ for which $$\begin{aligned} &\Pr(K > J) \geq 0.95,\\ &K \sim \mathrm{Bin}(n, 0.6),\quad J \sim \mathrm{Bin}(n, 0.5),\ \text{independent}. \end{aligned}$$ The joint distribution is the product of binomials, so $$\Pr(K > J) = \sum_{k=1}^{n} \sum_{j=0}^{k-1} \binom{n}{k} 0.6^k 0.4^{n-k} \binom{n}{j} 0.5^n.$$ This is a finite sum with no clean closed form, but evaluating it as $n$ grows shows where the threshold sits.

For intuition before the computation, the difference $D = K - J$ has mean $n(0.6 - 0.5) = 0.1 n$ and variance $n \cdot (0.6 \cdot 0.4 + 0.25) = 0.49 n$, so a normal approximation gives $$\Pr(D > 0) \approx \Phi\!\left(\frac{0.1 n}{0.7\sqrt{n}}\right) = \Phi\!\left(\frac{\sqrt{n}}{7}\right).$$ Setting $\Phi(\sqrt{n}/7) = 0.95$ gives $\sqrt{n}/7 = 1.645$, so $n \approx 133$. The exact threshold is a little higher because the normal approximation overshoots when the per-flip mean is small; running the exact sum lands on $$\boxed{\,n = 143 \text{ flips.}\,}$$ At $n = 142$ the probability is $94.95\%$; at $n = 143$ it crosses to $95.01\%$.

Extra credit. For a general doctored bias $P > 0.5$, the same calculation gives the threshold $$n(P) = \min\!\big\{\,n : \Pr_{K \sim \mathrm{Bin}(n, P),\, J \sim \mathrm{Bin}(n, 0.5)}(K > J) \geq 0.95\,\big\}.$$ The normal approximation $$\Pr(K > J) \approx \Phi\!\left(\frac{n(P - 0.5)}{\sqrt{n(P(1-P) + 0.25)}}\right)$$ gives $$n(P) \approx \frac{1.645^2 \big(P(1-P) + 0.25\big)}{(P - 0.5)^2}$$ flips, which scales roughly like $(P - 0.5)^{-2}$. A doctored coin with $P = 0.55$ takes about four times as many flips as one with $P = 0.60$; one with $P = 0.70$ takes about a quarter as many. The smaller the doctoring, the brutally slower the detection.

The computation

Evaluate the exact sum for $\Pr(K > J)$ and walk $n$ upward until it crosses $0.95$.

1. For each $n$, compute $\sum_{k > j} \Pr(K = k) \Pr(J = j)$ exactly using binomial coefficients.

2. Return the smallest $n$ with sum $\geq 0.95$.

from math import comb

def p_correct(n, P=0.6):
    pk = [comb(n, k) * P**k * (1 - P)**(n - k) for k in range(n + 1)]
    pj = [comb(n, j) * 0.5**n for j in range(n + 1)]
    return sum(pk[k] * sum(pj[:k]) for k in range(1, n + 1))

n = 1
while p_correct(n) < 0.95:
    n += 1
print(n, round(p_correct(n), 4))                    # 143 0.9501
print(141, round(p_correct(141), 4))                # 141 0.9488
print(142, round(p_correct(142), 4))                # 142 0.9495

The threshold sits at $n = 143$, with $p_{142} = 0.9495 < 0.95 \leq p_{143} = 0.9501$, confirming the boxed answer. Running the same routine over a grid of $P$ values gives the curve $13{,}626$ flips at $P = 0.51$, $559$ at $P = 0.55$, $143$ at $P = 0.60$, $37$ at $P = 0.70$, and $16$ at $P = 0.80$. The doubling-when-you-halve-the-edge rule of thumb is steep: a coin biased by half a percentage point takes nearly two orders of magnitude more flips than one biased by ten.