Game Theory: What are Best Strategies for High-Low game (game details are below)?

Solution 1:

A high-school student at IMSA and I analyzed the adversarial High-Low finding game of numbers $1\ldots N$ for $N$ up to $100$ about a decade ago.

Before presenting the answers, let me distinguish these games, in which the adversary has to choose a number in advance, and a game in which the adversary is free to alter the number chosen as long as all the answers given to date remain true. Allowing the adversary to change the answer makes the game much easier to analyze (it is no longer an imperfect information game!) and this is particularly true if we consider a variant of the game in which a single lie is permitted.

In general, there is a unique optimal hiding strategy (that is, a unique optimal distribution of probabilities of choosing the number $k$ with $1 \leq k \leq N$). But for many values of $N$, there are a range of optimal finding strategy mixes (that is, there are various decision trees that all lead to the same optimal expected finding time). In this answer I will only describe one finding strategy for a given $N$.

$N=3$: Hiding strategy is $2 \,|\, 1\,|\, 2$, meaning that the hider chooses $$P(k=1) = \frac{2}{5} \\P(k=2) = \frac{2}{1} \\P(k=3) = \frac{2}{5} $$ Henceforth, I will describe hiding strategies as just that sequence of relative values. The finding strategy is $$ P( (2)) = 3/5 \\ P(1;(3)) = 2/5 $$ This notation means the finder chooses an initial guess of $2$ 60% of the times, and the combination of [an initial guess of $1$ intending to guess $3$ next] and [the mirror reflection of that strategy, guessing 3 first] 40% of the time.

For $N=3, V(3) = \frac95$ which is 0.13333 worse than the optimum obtained by a binary search if the hider must choose $k$ as a uniform random on $[1,3]$.

For $N=4$ the optimum hiding strategy is $1 \,|\, 1\,| \, 1\,| 1$ (how boring!) and the optimum finding strategy is $P(2;(4)) = 1$, again with the understanding that that $1$ is split (half-half) between the strategy shown of choosing $2$ and then, if the answer is "higher", choosing $4$, and its mirror image of choosing $3$ and then $1$. This mirror property will hold for all the solutions I will present (although there are other finding optimal strategies for some of the games that do not have mirror symmetry). For $N=4$ the adversarial hiding game has the same value as the uniform-distribution binary search.

For $n=5$ the optimum hiding strategy is $5 \,|\, 3\,| \, 2\,| 3\,| \,5$ and the finding strategy is $$ P( (3;(1)(5) ) = 4/9 \\ P(2;(4) )= 4/9 \\ P(2;(5;(4))) = 1/9 $$ A final notation tidbit here -- the first of these strategies exhibits, for the first time so far, the information as to what you will do for each of two possible answers, saying that if you guess $3$ and the number low, you use the strategy $(1)$ but that if it is high you use the strategy $(5)$. This is why some single numbers are written in parentheses; items in parentheses represent complete finding strategies for some sub-interval.

Note that even though the numbers $1$ and $5$ are significantly more common than the other numbers, you can never (in an optimum strategy) start by guessing one of those endpoints. That sacrifices too much information in the case that the first guess does not hit $k$ immediately. $V(5) = 20/9$, which is $0.2222$ worse than the non-adversarial (uniform distribution) finding problem.

For $N=6$ The optimum hiding strategy is $5 \,|\, 3\,| \, 2\,| \, 2\,| 3\,| \,5$ and the finding strategy is $$ P( (3;(1)(5) ) = 3/5 \\ P(3;(1)(6;(5)) )= 1/5 \\ P(2;(5;(4))) = 1/5 $$ (Don't forget that since you must split these between the stated strategies and their mirrors, this is really a six-component mixed strategy.) $V(6) = 12/5$ which is 0.066667 worse than the value of the non-adversarial game (which I will $B(6)$.

For $N=7$ thru $N=10$ the optimum hiding strategy is $2 \,|\, 1\,| \, 1\,| \cdots \,|\, 1\,| 1\,| \,2$ and $$V(N) = \frac{4N-5}{N+2} = B(N) + \frac{22-2N}{N(N+2)}$$ so the adversarial game is worse than the uniform game by an amount tan falls from $0.127$ down to $0.0167$.

It would be tempting to suppose that that pretty property of hiding by doubling the chances of each end number, and otherwise choosing the number as a uniform random, holds from then on. Not that simple!

For $N=11$ the optimum hiding strategy is $58 \,|\, 29\,| \, 29\,| 34 \,| 25 \,| 22 \,| 25 \,| 34 \,| 29 \,| 29\,| 58$ and an optimum finding strategy is $$\begin{array}{lll} P(6;(3;(1)(4))(9;(8)(11))) &=& 117/744 \\ P(6;(2;(4))(10;(8))) &=& 123/744\\ P((5;(2;(4))(9;(7)(11))) &=& 348/744\\ P((4;(2)(8;(6)(10))) &=& 54/744\\ P(4;(2)(9;(7;(5))(11))) &=& 72/744 \\ P(4;(1;(3))(8;(6)(11;(9)))) &=& 30/744 \end{array} $$ I should mention the technique for solving these games: It is easy enough to write a simplex solver and tie it to something that fills in the expected values (which may have halves because a strategy includes its mirror image) for each combination of number chosen and strategy employed. The tough part is to feed in a suitable set of candidate strategies. You can't afford (for large $N$) to simply generate all possible strategies, as the number grows exponentially. For example, with $N=11$ we initially fed in $17$ plausible finding strategies. The key next step is to assume the hiding strategy found by the simplex solver is fixed, and solve for the best possible search. If the expected value is the same as the game values you just solved, then you are through; otherwise, you need to add in at least the superior finding strategy you just determined, possibly chop out some of the discarded strategies, and try again.

For $N=12$ the optimum hiding strategy looks qualitatively like that for $N=11$, it is $68 \,|\, 34\,| \, 34\,| 43 \,| 31 \,| 24 \,| 24 \,| 31 \,| 43 \,| 34\,| 34\,| 68$. Note that both of these look a lot like the basic $2,1,1,1,\ldots,2$ pattern, but with some waviness.

$N=13$ and $N=14$ fall into a third common pattern: $$129 \,|\, 77\,| \, 52\,| 62 \,| 64 \,| 48 \,| 48 \,| \cdots \,| 48 \,| 48\,| 64\,| 62\,| 52\,| 77\,| 129$$.

$N=15$ through $N=19$ obey the same pattern found for $N=5$ and $N=6$, namely $5 \,|\, 3\,| \, 2 \,| 2 \,| \cdots \,| 2 \,| 2\,| 3\,| 5$. $N=20$ foall back into the simpler $2\,| \, 1 \,| 1 \,| \cdots \,| 1 \,| 1\,| 2$ pattern. That pattern persists until $N=28$ which has a fairly ghastly hiding pattern where the least common multiple of the denominators is a 25 digit number; it still looks like a slightly wavy shallow bathtub with the end elements precisely double their neighbors.

By the time we get to $N=30$ we are back to the simple $2$ pattern, but $N=31$ has the pattern that starts with $129$. The highest one I remember is for $N=63$, for which the optimal hiding strategy is the "Fibonacci" pattern $5 \,|\, 3\,| \, 2 \,| 2 \,| \cdots \,| 2 \,| 2\,| 3\,| 5$. It may be a deep problem to determine what drives the changes in these patterns.

We also solved the one-lie fully adversarial (but no "cheating" by changing the selected number) game, for up to $N=9$. That problem is vastly more difficult, since both the finder and the hider have large sets of plausible strategies. One thing that emerged is that the naive single-error-correcting finding strategies (based on assuming that the number originally chosen was uniformly random and that lies are equally probable at each guess) are markedly inferior; typically more than $0.25$ of a guess worse than the optimal finding strategies.