Analysis of adversarial binary search game

Introduction

Alice and Bob are at it again, this time playing a game called Binary Search. Alice begins by secretly selecting an integer key from 1 to , then Bob makes a series of integer guesses, to each of which Alice responds indicating whether the guess is correct, or higher than her selected key value, or lower. Bob must pay Alice one dollar for each guess (including the final correct guess). How much should Alice be willing to pay to play this game with Bob?

This post is motivated by a recent blog post by John Graham-Cumming, discussed on Hacker News, about a similar game apparently used by Steve Ballmer in Microsoft job interviews. In the linked clip, Ballmer plays the role of Alice, and offers $6 to play the game. You’re Bob interviewing for a job: should you take the bet? Ballmer suggests that the answer is no, since as he puts it, “I [Alice/Steve] can pick numbers specifically that are hard for you [Bob] to get.”

As many have noted in the subsequent discussion, this comment certainly seems to allow for Alice/Steve picking numbers adversarially, that is, not necessarily uniformly at random. But presumably Bob is then allowed similar leeway, not being forced to execute textbook binary search that always guesses the midpoint of the interval of remaining possible numbers. So who has the greater strategic advantage? I’m not sure. I think this is a hard problem, as I’ll try to make the case below.

Solving smaller problems

I wrote some Mathematica code (on GitHub) to compute exact optimal strategies for Alice and Bob for smaller versions of this problem, up to . Alice’s pure strategies are simply the set of possible secret keys. Bob is more interesting; we can identify each possible pure search strategy as an in-order binary tree with vertices. The following function enumerates these (it’s always a nice surprise when my favorite sequence turns up in another unexpected place):

(* List all possible search strategies with key space[n]. *)
strategies[n_] := strategies[n] = Module[
   {guess},
   If[n === 0, {{}},
    Join @@ Table[Join @@ Outer[
        {guess, #1, #2} &,
        strategies[guess - 1],
        guess + strategies[n - guess],
        1
        ],
      {guess, 1, n}
      ]]]

Armed with Alice’s and Bob’s pure strategies, we can compute the matrix of payoffs resulting from each possible strategy match-up, then solve the corresponding linear programming problem to compute the expected value of the game and the Nash equilibrium mixed strategies for each player.

Results and conjectures

The results for up to 13 exhibit a consistent pattern suggesting that an optimal strategy for Alice is to pick numbers “almost uniformly” at random… but twice as likely to pick a number on the edge. More precisely, pick 1 or each with probability , and pick any other number with probability . I think it is likely that this is an optimal strategy for Alice in the case as well. (However, it’s interesting to observe that the presumed “Ballmer strategy” of picking uniformly from the subset of numbers for which the normal binary search would yield the maximum number of guesses has the same expected payoff.)

Bob’s strategy, on the other hand, is harder to describe in simple terms. Let’s consider for a specific example. Of the 742,900 possible pure search strategies, an optimal mixed strategy for Bob is to select from just the following baker’s dozen with the indicated probabilities, where each search strategy is specified as the pre-order traversal of the corresponding binary tree:

Prob.      Strategy
------------------------------------------------
0.381579   7  3  1  2  5  4  6 11  9  8 10 13 12
0.131579   8  4  2  1  3  6  5  7 12 10  9 11 13
0.131579   6  2  1  4  3  5 10  8  7  9 12 11 13
0.0625     9  4  1  2  3  6  5  8  7 12 10 11 13
0.060855   5  2  1  4  3 10  8  6  7  9 13 12 11
0.055921   9  4  2  1  3  6  5  8  7 12 10 11 13
0.055921   8  3  1  2  5  4  6  7 12 10  9 11 13
0.055921   5  2  1  4  3 10  8  6  7  9 12 11 13
0.055099   6  2  1  4  3  5 11  9  8  7 10 13 12
0.003289   9  5  2  1  4  3  7  6  8 12 10 11 13
0.003289   5  2  1  4  3  9  7  6  8 12 10 11 13
0.001645   5  2  1  4  3 10  7  6  9  8 13 12 11
0.000822   7  2  1  4  3  5  6 11  9  8 10 13 12

In other words, roughly 38% of the time Bob should conduct the usual even-split binary search, guessing the midpoint 7 to start. However, sometimes Bob might start with an initial guess as low as 5 or as high as 9.

In the original game where , I think it’s certainly the case that Bob should similarly be willing to start with guesses north of 51 or south of 50, but it’s unclear how extreme those departures might be.

Finally, what is Alice/Steve’s expected return in this game? Let’s set things up similarly to the Ballmer interview version of the problem, and suppose that Alice pays dollars to play, and wins back a dollar for each of Bob’s guesses. Then the following figure shows Alice/Steve’s expected return as a function of the number of possible keys to pick from.

My suspicion is that this sawtooth behavior persists, continuing to straddle zero expected return, so that it seems difficult to predict whether the particular game at has Alice in the red or the black, when both she and Bob use truly optimal strategies. This simple brute force computational approach certainly won’t work: the matrix of payoffs has 100 rows and roughly 10^57 columns.

Edit 2024-09-09: I was referred to Konstantin Gukov‘s very interesting article about this game, where they compute an explicit strategy for the case that proves that Alice/Ballmer’s expected return is indeed negative in that case. They do this by restricting Bob the Guesser’s set of available binary search strategies, from all possible strategies to just 586 carefully chosen ones, so that it is feasible to solve the corresponding linear programming problem. Since Alice’s expected return is negative against this handcuffed version of Bob, it must also be against a truly optimal guesser.

Gukov’s selection of subset of strategies is indeed well-chosen. I ran Gukov’s Python code to generate their search strategies for all up to 100, then computed the resulting expected return in each case. (Recall that we are assuming that Alice pays dollars to play, so that we can compare performance across a range of key space sizes.) The results are shown in the figure below, with Ballmer’s return against Gukov’s restricted guesser shown in red, and the performance against an optimal guesser shown in blue (essentially a reproduction of the earlier figure above).

This gives more evidence for our earlier speculation about how the advantage varies with , with a clearer picture of the pattern: it seems that Ballmer would have been safest by offering to play the game choosing numbers from 1 to 127– or 1 to 63, or 1 to 31, etc.– instead of 1 to 100. Powers of two are the worst for Ballmer, but as the key space increases from there, it eventually becomes advantageous again… until reaching the next power of two.