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.
Right! I'm not sure if that's actually what he had in mind, but if he did, it's funny because it makes all this mathematical analysis completely pointless.
The OP has a complex randomized strategy that guarantees to average at least $0.07 against any adversary; meanwhile, just by delaying his "pick" and stringing you along, Ballmer makes you take seven guesses and owe him a dollar each time.
If you were expecting to win $0.07 on average, how many rounds would you play before you realise you're being scammed?
The OP's article is interesting, but it assumes a very weak notion of "adversarial", in which Ballmer still commits to some initial choice.
Interestingly it's actually possible for a player to know this is the case if Ballmer uses a commitment scheme [1]. For example, at the start of the game Ballmer could generate 500 random bits, append his chosen number in the range 1-100 to this, hash the result and then send you that hash: At the conclusion of the game, he sends you the 500 random bits, and you can check that concatenating his chosen number (now revealed) to those bits and hashing the result produces the hash he originally sent. (If Ballmer lies and changes his number, he would need to somehow come up with 500 bits that when concatenated with this different number still produce the original hash. This is hard.)
His wording of the rules implies he chooses a number and sticks with it. He "has a number in mind". Of course some interviewers like to play mind games and twist things up to make themselves feel smart but I don't think that's his intent here.
Well, rereading what he (was reported to have) said, I now think that probably was his intent, and he was just sloppy. At least, he can't have it both ways: Either he genuinely commits to a number at the outset, and uses the word "adversarial" to mean a very weak form of adversary (one that is defeated in expectation by TFA's mixed strategy), or he is using "adversarial" in the standard (strong) sense, in which case he must be lying about committing to a number, which is a shifty mind game as you say.
This is how it is done in the analysis of competitive ratios of online algorithms. The adversary can change its mind on a whim, it merely has to commit to the decisions it has already made in the past.
I mean, who know what he’s thinking, but based on the game description that strategy isn’t “adversarial”, it’s lying. Maybe the lesson is “don’t play games for money with people who will cheat”, but it would be a boring one.
