The expected value of the game is positive regardless of Ballmer’s strategy

Recent and related:

Steve Ballmer's incorrect binary search interview question - https://news.ycombinator.com/item?id=41434637 - Sept 2024 (240 comments)

This sort of misses the forest for the trees, although neat application.

Ballmer's argument is essentially about tail risk. Expected value is absolutely not a good way to make bets if you value survival, because you only get one shot. Same reason you wouldn't go all in every time you get a poker hand that's "expected" to win. Because you'll (very probably) be bankrupt in a few hands.

Sure the mean is +$0.07 or whatever, but the spread on that surely goes over the 0 line. So there may well be marginally more chance of winning than losing, on average, but you're only gonna get one outcome. So if the goal is to play to win, or else, then you probably shouldn't unless you like owing Ballmer money.

What would be more interesting is to monte carlo simulate this strategy and look at the win/loss distribution. Presumably the choice is then not so clear cut.

If you're allowed to play the game a few trillion times or so, then by all means bleed him dry :P

When Ballmer said 'adversarial', I considered this strategy: he's not actually required to pick a fixed number at the start at all. He can simply give the answer to each guess which leaves the largest number of possible numbers remaining, guaranteeing a loss regardless of strategy.

Edit: Oops, nope, this comment is wrong, ty fgna for pointing that out!

I feel like there's an even simpler proof that you can beat adversarial-ballmer, with exactly the same expected positive outcome as binary search vs random ballmer.

I call my algorithm "randomly offset binary search". It goes like this:

1. Pick a random number between 0-100, call this 'offset'

2. Perform the binary search algorithm, except at each step add 'offset' to the value and mod by 100.

That's it. Now, even if Ballmer knows you're using this strategy, he can't make it perform any worse by selecting any specific number. Therefore your expected outcome is still $0.20 per game, beating the strategy proposed in this blog post.

Of all the things that Ballmer was wrong about... I guess this is one of them.

And this, friends, is the perfect example of why the modern tech interview process is pure insanity.

A more extensive analysis of Nash equilibria including a numerical solution for the full game is presented in https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s...

I was looking for the comment that simply said "This looks right, good work!" and since I couldn't find one, let it be me:

This looks right. Good work!

Steve Ballmer's net worth is 120 billion dollars, so, assuming each game takes 30 seconds, it would take you 1.6 million years to win it all.

Little Mathematics Library – Elements of Game Theory: https://mirtitles.org/2012/09/06/little-mathematics-library-...

This is a very nice book covering mixed strategy in game theory.

A very nice motivating example from the book: "There are two cards, an ace and a deuce. Player A draws either of the two at random; B does not see which card is drawn. If A has drawn the ace, he says "I've got the ace" and demands a dollar from his opponent. If A has drawn the deuce, then he may either (A1) say "I've got the ace" and demand a dollar from his opponent or (A2) confess that he has got the deuce and pay his opponent a dollar. The opponent, if he is paid the dollar voluntarily, can only accept it. If, however, a dollar is demanded from him, then he may either (B1) believe that player A has got the ace and give him the dollar or (B2) demand a check so as to see whether A's statement is true or not. If it is found that A does have the ace, B must pay A two dollars. If, however, it is found that A is bluffing B and has the deuce, player A pays B two dollars. Analyze the game and find the optimal strategy for each player and the expected payoff."

Can't wait for the paper that solves for the Nash equilibrium for this game.

Nice! I tried to solve this the other day too, but came from the other angle--trying to find a probability vector for Ballmer that always won (finding the best response tree is n^3 complexity best I could find). I'm somewhat surprised since I figured for sure Ballmer had a big edge by picking numbers near the endpoints, making the player pay a large cost to check them.

> I’m thinking of a number between 1 and 100

People are unable to think randomly. They'll avoid the obvious "not random" numbers 2 and 99, for example. I read somewhere that most people, asked to pick a number between 0 and 10, will pick 7. And the next digit would probably be odd, and not 5, because 5 is not random. That leaves you with 71, 73, 77 and 79. 77 is not random, so 71, 73 or 79. I'd pick 73 as my first guess.

I'd say those were good odds!

(That's why when you're picking a "random" number, it's best to use an actual dice.)

This is how you win at hammer-paper-scissors, too.

Ballmer could also change the number he's thinking of as you make guesses, so part of the game would be guessing what he's thinking.

> I’m thinking of a number between 1 and 100.

I guess this is part of the clarifications one normally asks when in an interview setting, but he has specified numbers and not integers. One could choose (pi*2)/2 and you will owe a lot of money.

Here is a chart for probabilities for starting value:

https://docs.google.com/spreadsheets/d/e/2PACX-1vThljkK2nUIL...

I find it interesting: it is definitely symmetrical, but I did not expect that in the final result 1/98 could be more important as a starting value, while 2-17/82-97 are not used at all.

I did a very similar exercise after reading the original post.

You can get the EV a lot closer to the optimal +0.2 (Although I was unable to prove how close) by dropping the requirement "do not increase worst-case complexity for the binary search" as this is lost with initial guesses outside 36-64 anyway. Deviating at a higher depth makes punishing specific guesses in the tails a lot cheaper, only giving up 1-2 cents of EV.

It would only make sense if Ballmer writes the number he is originally guessing on a piece of paper and fold it before game begins. And win/loss is checked with what is written on the paper.

Otherwise it is a hidden mutable information game where Ballmer dynamically changes higher/lower for maximum tree depth and always make you lose.

What if he flips a coin? 50% chance to optimize for Binary Search and 50% chance to optimize for Ballmer Search?

I'd like an online demo where you play as Ballmer against an opponent using this strategy.

I wonder whether the search algorithm would need (and can?) to be adjusted to respond to the increased probability of playing numbers that are hard to find with standard binary search.

I dont get this. If this is true, then he found a more efficient algorithm than binary search. Why are we not using it in CS?

Honestly I think Ballmer would have appreciated this answer in an interview.

I 100% believe Balmer had an off by one error

> Out of the 100 numbers, there are 32 that would require you to ask 6 questions to make a guess.

Huh? I have 100 - (1+2+4+8+16+32) = 100 - 63 = 37, where 2^i numbers can be guessed after exactly i wrong guesses plus one correct guess.

moral of the story: you might be theoretically correct, but the other dude still has a net worth of 120bn and you don't. so who's the loser now?

After watching the interview I can't imagine why anyone would spend time trying to solve for this or entertain this as a valid test of anything. In 7 guesses he TWICE amended if she was high/low after hearing her guess.

I watched the interview, and I see two problems:

- nowhere it says he has to choose whole number, he could choose fractions (55.25) or even irrational like PI. Number of questions can be infinitive.

- nowhere it says, he may not change his number while the game runs.

You pay upfront for each question, and you hope game is not somehow rigged. It is not just question of algorithms.

Also money you win is a taxable income, payments for hazard are not taxable expenses...