6 ms·

The article implies that the interviewee assumes that the number is being chosen randomly, when Ballmer could actually be choosing adversarially. However, if t

• more_corn 2y ago
  Speaking of adversarial choices, the interviewee may wish to clarify that this number is an int and not a float :-p
• OneLessThing 2y ago
  Okay I did the simulation. I don't think this strategy actually works, but I initially thought it might like you did. One such nash equillibrium my sim found was having the Ballmer player mix between picking either end of the range (not always 1 or 100 but around those numbers). I have the Ballmer player winning with around $.85-$1.00 EV per round. The resulting player strategy was to also try to start their binary search at the extreme ends of the range and hope they guessed the right side. It's kind of like the soccer penalty kick dynamic between the shooter and goalie. Goalie wants to pick the same side, shooter wants opposite sides. But with 100 choices, the goal is too wide I think. I now think that not constraining the players remaining choices to follow binary search pattern would completely change the resulting equilibrium and improve the results for the player. But that would be more computationally demanding to calculate because there's a strategy choice for every range of choices. And also I've avoided work for 2 hours by working on this so that's not great haha. I _am_ curious what not constraining the player to binary search would do though...
  • gukoff 2y ago
    You can actually do well combining different flavors of binary search! I commented a solution on the parent post if you're curious.
• gukoff 2y ago
  Yes, you can counter the adversarial choices and win at least 7 cents per game :) https://gukov.dev/puzzles/math/2024/09/05/steve-ballmer-was-wrong.html https://gukov.dev/puzzles/math/2024/09/05/steve-ballmer-was-...
• jgrahamc 2y ago
  And then if Ballmer assumes the other party assumes he's being adversarial we get into game theory.
  • kibwen 2y ago
    The ultimate conclusion of which is likely that both parties will decay to picking the secret value/first guess randomly (although I'm not sure if the optimal distribution is perfectly flat?), which is also something that we can model.
    • gcanyon 2y ago
      Seems like the distribution definitely won’t be flat since the guesser can randomly choose any of the numbers from 37 to 64 as a first guess without losing anything on the large side, so Ballmer starting with any of those increases his chance of having to pay out the $5. Likewise for other numbers there are nuances to what can be guessed.
      • alain94040 2y ago
        But if you assume that the opponent knows that they shouldn't pick between 37-64, doesn't that change your odds? The game theory here is similar to another quiz "Guess 1/3 of the average". You are really trying to guess how deep the other has thought about the problem, so you can tell which strategy they settled on, and then you adapt your strategy based on that. Of course, it's a loop.
        • gcanyon 2y ago
          Yep, definitely not just what I said. I was saying that guaranteed it won't work out to an even distribution, not what the distribution would be.
  • TeMPOraL 2y ago
    The way forward is to make Ballmer pay with time for screwing with you, which gets us into geopolitics, and then using the resulting MAD dynamics to make the game fair again. That's how adults with keys to the nukes do it :).
• thedavibob 2y ago
  > you can select an initial guess that is offset from 50 Given that 7 guesses covers 128 numbers, you can offset by +/- 14 without actually affecting the "worst case" of the algorithm (i.e. provided you have at most 64 either side of your guess). As you say, randomly selecting this offset would neuter most adversarial examples (purposefully chosen to fall into the gaps of binary search) and would possibly completely remove the benefits from adversarial choice (though a tailored distribution on offset might be required there). I'd be interested in such an analysis too.
  • hulium 2y ago
    > Given that 7 guesses covers 128 numbers I might be confused, but don't 7 guesses actually cover 255 numbers? I think you have to count all nodes in the search tree, not only the leafs, because you can get the correct number before reaching a leaf node. Or more generally k guesses cover 2^(k+1)-1 numbers, e.g. with one guess you get the answers correct/high/low, which can cover 3 numbers) Maybe there is a mistake in my thinking, because this would mean you can cover 127 numbers with 6 guesses so you could not lose the original game. Edit: My mistake is that you still have to explicitly guess even if you know the precise answer already, so you cannot cover 3 numbers with 1 guess. This means 7 guesses cover 127 numbers.
    • deleted 2y ago
      [deleted]
    • sltkr 2y ago
      Your logic is correct but you are off-by-one. 1 guess gets you 1 number, so the formula is 2^k - 1, and 7 guesses thus covers 127 numbers. You can also view it as a recurrence: f(1) = 1 f(n) = 2*f(n - 1) + 1 = 2^n - 1 But your binary search tree example is more intuitive.
      • hulium 2y ago
        Yes, you are right. In this game, you can know the answer after 6 guesses, but then you also have to tell him, which counts as the 7th guess.
• mrgoldenbrown 2y ago
  It would not be shocking to find out a cocky interviewer posed a brainteaser while leaving out a fundamental assumption, then judged an answer as incorrect because it violated that unspoken assumption - I can imagine Ballmer saying "no actually, you have to start with a guess of 50, everyone knows that."
  • enneff 2y ago
    Unless the interviewer has totally lost sight of the purpose of the interview, they’d recognise a candidate starting at an offset from 50 as an instant pass.
    • ozim 2y ago
      What was the last time you were on the interview? I think like 70% of interviews I ever had were like they were there to prove how smart they are and how stupid I am. I suppose most likely to make me feel stupid and accept lowball offer.
      • HarryHirsch 2y ago
        Like this one: https://rachelbythebay.com/w/2011/07/27/ohreally/ https://rachelbythebay.com/w/2011/07/27/ohreally/ Yes, that happens, and elsewhere she goes on about culture in tech.
        • wisemang 2y ago
          I don’t doubt this happens but seems like a poor example. She effectively rooted out a bullshitter. No worries if you don’t know how a tool works, but just say I don’t know. That answer was nonsensical.
          • HarryHirsch 2y ago
            The purpose of an interview is not to root out a bullshitter but to find someone you can work with. If that guy doesn't know about TCP/IP, move on to the next topic. If the guy has poor attitude, be polite. Just don't waste time with making fun of the candidate, it does not reflect well on interviewer and company. For what we know, the guy may well have been employing "test-taking strategies", and he may have been led down the garden path by the interviewer. There's far too many posts in Rachel's blog where she goes on about "the one", who knows much better already, and here she channels the asshat that she complains about when she encounters him at work.
• corecirculator 2y ago
  Other commenters are wrong in saying that the payout is different for an adversarial choice. The crux of the payout derivation is: we can only cover 1 number in step 1, 2 in step 2, 4 in step 3, 8 in step 4, and so on. You can choose your initial number in binary search randomly, and as long as you meet the above condition is met (# of possible numbers covered in each step), payout should be same as 0.2
  • alexey-salmin 2y ago
    Your calculation assumes that probability of each number is the same which is not true for adversarial choice.
  • dagw 2y ago
    If I 'know' that my opponent is adversarial, then I might assume that he's not picking from the set of 100 possible numbers, but actually from a smaller set of 'adversarial' numbers, like the set that will always take 6 or 7 guesses using the naive binary search approach, and I can adjust my strategy accordingly.
    • LudwigNagasena 2y ago
      You should assume that your opponent is adversarial to your specific strategy.
• deleted 2y ago
  [deleted]
• layer8 2y ago
  If Ballmer is being adversarial, he won’t pick the number at the start, and always win. Of course you can set up the game such that Ballmer has to commit on a number at the start of the game (by sealing it in an envelope or whatever), but that wasn’t specified.
  • whimsicalism 2y ago
    they’re being adversarial within the framed rules of the game, not breaking the rules of the game?
    • patal 2y ago
      Without writing the number down, it's up to Ballmer to decide that aspect, because you cannot look into his brain, or prove that he didn't commit to a prior number. Therefore, it's fair game.
  • jefftk 2y ago
    Ballmer opens with "I'm thinking of a number between 1 and 100". If he uses your strategy instead that's a different scenario.
    • layer8 2y ago
      That’s only if you’re willing to trust Ballmer to do what he claims, which I wouldn’t.
      • jefftk 2y ago
        Do you trust Ballmer to give you $1 in the cases where he's said he's going to give you $1? If not the EV calculation looks pretty bad...
• Someone 2y ago
  > I'd be interested to see someone do the analysis of what the optimal random-offset-selection algorithm would be to counter trivial adversarial choice If you know your opponent picks a number uniformly from all numbers that lead to a maximum of guesses, the optimum strategy is a binary search between those numbers, making sure to pick one of those numbers at each turn. The problem stays completely symmetric under this condition, so there would be two (maybe four due to edge conditions) optimal first guesses summing to 101. In general, I think the trick still is a binary search where each guess splits the range of options in halves of equal expected/min/max cost (depending on whether you want to optimize for expected/min/max cost).
• auselen 2y ago
  Genuinely asking - not directly to OP of course, wasn’t this how people were playing the game when you were kids? Not as rigorous, but you intuitively try offsets to get lucky and find the number in fewer tries?
• gweinberg 2y ago
  No it doesn't, it's quite clear that Ballmer can be choosing adversarially. The point is that even if Ballmer chooses randomly and the interviewee plays optimally given this, the game still has a negative expectation value, and that is enough to be sure the game is a loser for the interviewee. The post never answers the question "so what is the real expectation value", which is a more difficult question. But I think if the interviewee chooses a number randomly from 40-60 as the first guess and does a binary search from there, Ballmer can't really improve on choosing his initial number randomly.
  • whimsicalism 2y ago
    right but as posed the EV is positive if ballmer picks randomly so you have to go into consideration of the adversarial case
  • baking 2y ago
    I think you did the math wrong. The expected value for the guesser is $0.20 if Ballmer chooses randomly. I think Balmer is saying that he can beat you if he chooses adversarially and you choose the expected initial guesses. I agree that if you choose your first guess somewhat randomly in the 40-60 range (maybe not a uniform distribution though) Balmer would be forced to choose randomly and you would be back at a positive $0.20 EV. For example, you could flip 6 coins and add the number of heads, then flip another coin to decide whether you add or subtract the number of heads from 50 for your starting guess. But I think you would need to randomize your later guesses a bit also.
• potsandpans 2y ago
  I'm not really married to this idea, but my first reaction is that to assume a random number would be an invalid assumption. The scenario is framed as a zero sum game: one of us wins. The question is, "should you play?" In order to answer, you need to be able to determine whether or not there is an optimal strategy that is generally successful.That should include both the assumption that Ballmer has chosen a number adversarial weighed against the random choice.
• baking 2y ago
  You have 31 positive payout guesses (1 $5, 2 $4, 4 $3, 8 $2 and 16 $1) leaving 69 other numbers with zero or negative payouts. You don't want to have gaps larger than three between your positive guesses, but there are 32 gaps for a total of 96 possibilities, or an excess of 27 over the numbers you need to cover. It seems like a lot of possibilities and I think you can get away with a minimum gap size of one, but let's assume you do 5 3-gaps at 1, 25, 50, 75, and 100 and 2-gaps everywhere else. So start with 51, then 26 and 76. Then go up or down 12, then 6, then 3. If you have a gap of two you flip a coin, if a gap of three you pick the middle one. Or if you have them write down the number and you think it has double-digits you could put your 4-gaps below 20. Start with 53 and go up or down 24, 12, 6, and 3 (unless it is below 20, then it is multiples of four.) 59 would pay you a dollar. Your starting guess could be anywhere from 37 to 64 without paying out more than a dollar, but if you start with an extreme, then low odd numbers and high even numbers will have a negative payout. However, I think you can still randomize sufficiently starting with 38 and 63, e.g. 63-31-15-7-3-1.
  • vladimirralev 2y ago
    One can make the case for a perfectly rational adversary who always avoids picking paying numbers in anticipation of the opponent to exclude paying numbers successively in their guesses. When the game is played with perfectly rational characters the picker is doomed to select one specific number and thus you always make the maximum amount. There are some variations of the binary search but that can also be worked around. If they are not cheating, that is.