Guessing Game Problem

Inspired by (stolen from) an interview question posed by Steve Ballmer found on John Graham-Cumming's blog and HackerNews.

Problem

Let there by two players, a Picker and a Guesser. The Picker chooses a number between $1$ and $N$ (inclusive). The Guesser then pays the Picker \$1 to guess a number. The Picker then responds with either "Correct", "Lower", or "Higher". This repeats, with the Guesser paying \$1 per guess and the Picker responding, until the Guesser finds the number. How much should the Picker pay the Guesser for her to choose to play this game?

Analysis

Given a probability vector $p$ of length $n$, if the Guesser chooses $k$, the expected number of guesses is

$$ Un^k(p) = \left( \sum{i\lt k} pi \right) V{k-1} \left( \left[ \frac{pj}{\sum{i\lt k} p_i} \middle| j\lt k \right] \right) + pk + \left( \sum{i\gt k} pi \right) V{n-k} \left( \left[ \frac{pj}{\sum{i\gt k} p_i} \middle| j\gt k \right] \right) $$

where $V_n$ is the optimal choice

$$Vn(p) = \min{1\leq k\leq n} U_n^k(p)$$

The Guesser cannot credibly deviate from the optimal choices after the first guess, so her strategy is some distribution $q_N$ over $[N]$. The Picker's strategy is also a probability vector $p_N$. There is then a symmetric Nash equilibrium for this game where both the Guesser and the Picker play $p_N^*$. (Credit to Wing Suen for explaining the game theory reasoning to me,)

We can find the distribution $p_N^*$ that solves the game by solving the system of equations

$$U_N^1(p^*) = U_N^2(p^*) = \cdots = U_N^N(p^*)$$

which then gives the solution to the problem $V_N^*=U_N^k(p^*)$.

Solutions

Solutions for $N\leq6$ found by Z3. Remainder found by scipy.optimize.minimize and checked by computing $U_N^k(p)$ exactly.

Repo

pick-choose.nb

Exploratory work in a Mathematica notebook. Solves up to $N=4$.

z3solve.py

Requirements: z3-solver

solveprob(N) returns dictionary of solution for $N$.

Solutions up to $N=6$ computable.

optimize.py

Requirements: SciPy

exact(N) and approx(N) return dictionaries of either exact or approximate solutions for $N$.

Exact solutions up to $N=16$ computable. Approximate solutions up to $N\approx40$ computable.