Related to <a href="https://news.ycombinator.com/item?id=41434637">https://news.ycombinator.com/item?id=41434637</a><p>The exact analysis for n=13 (instead of n=100) is presented--or rather, just the answer from the exhaustive search. The answer for n=100 is still unknown.
The punch line of this post is that <i>if</i> Ballmer defines the payouts so that the interviewee receives floor(lg N) dollars for hitting in one guess, <i>then</i> Ballmer's expected payout decreases as N increases — with a sharp step upward each time N reaches a power of two.<p>This is... exactly how the floor function is defined to behave!<p>The graphs would be much more enlightening if the artificial step function were removed. Instead of subtracting from floor(lg N), subtract from plain old lg N — or even don't subtract from anything at all, and just graph the number of guesses required.
See also <a href="https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-search/" rel="nofollow">https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s...</a> using the Multiplicative Weight Update algorithm ( <a href="https://www.jeremykun.com/2017/02/27/the-reasonable-effectiveness-of-the-multiplicative-weights-update-algorithm/" rel="nofollow">https://www.jeremykun.com/2017/02/27/the-reasonable-effectiv...</a> a recurring feature on HN) to compute an approximate Nash equilibrium up to <i>n</i> = 100.
I don't see why this can't be solved (approximated) recursively.<p>If I know the EV of 1 and 2 choices, then the 3 number situation is the same as whatever weight I assign to choosing the first number multipled by Ballmer's strategy multiplied by the EV of the 1 case when I pick 2, and the 2 case if I pick 1 or 3. Run this as a Counter Factual Regret minimization problem for each value from 3 through 100 with some sort of error threshold and you have a good enough answer.<p>I'm not 100% sure of that though. Perhaps there's a dependency in the two steps that confounds this approach?
It might be fun to play an iterated version of this game.<p>Also I'd be keen to see a web ui where you can play against an ai. Not quite sure how the ai would work though. You don't necessarily want the ai to play optimally (if the optimal strategy were even known) because the fun is in working out how to exploit the other player's flaws.
My feeling without being rigorous is that something is wrong with this solution.<p>Notably the size 13 case enumerated in the post, choosing 1 as the Chooser will always take 3 guesses (the most possible). Even in an iteration of a mixed strategy the Guesser will never guess 1 in fewer than 3. This is also true for 13.