10 ms·
The expected value of the game is positive regardless of Ballmer’s strategy
- qarl 2y agoAnd this, friends, is the perfect example of why the modern tech interview process is pure insanity.
- weinzierl 2y agoIt is the perfect example, why you should pay attention in your math class too.
- corimaith 2y agoI don't think the average CS curriculum is going to cover advanced game theory. And you certainly aren't going to doing most linear programming on the spot in a interview.
- rustybolt 2y agoThis is actually extremely basic game theory, but I agree that most CS programs would probably not cover it.
- OmarShehata 2y agois it? If I was forced to ask this question as an interviewer, and the candidate said, "actually, you're wrong, here's why" that's a very good signal. Do most people not do this? (typically there's discussion with all the interviewers and it isn't just "did the candidate get the question right or not). I personally think a lot of big tech interview questions are dumb but I think the process isn't as broken as I thought, seeing it from both sides.
- metabagel 2y agoI suppose that telling the interviewer that they're wrong is a good way for the interviewee to test culture fit.
- rustybolt 2y ago> Do most people not do this? I'd say it's impossible to answer this question conclusively within the time frame of an interview. That makes it, in my opinion, a bad interview question. My answer to this question would be to show that I understand what it would take to answer this question correctly (you'd have to find a mixed strategy that has a positive expected value for every choice of number), I wouldn't be able to give a confident "yes" or "no" answer on the spot. I think that's the only correct answer. In practice, I think this question is advantegeous for those who confidently blurt out an answer and then make up a heuristic argument for it. But a heuristic argument can be found for both "yes" and "no".
- carlmr 2y ago>If I was forced to ask this question as an interviewer, and the candidate said, "actually, you're wrong, here's why" that's a very good signal. Do most people not do this? The question is whether Ballmers ego would allow him this flexibility if it's his own question. Some people might be very emotionally attached to the questions they created, but not so much to those they've been given as an interviewer. I've fared well pointing out issues with questions in the past and gotten the job. I'd try to be diplomatic about it though and not outright say they're wrong. Instead pointing out how with a classical binary search the expected value is negative, but there are strategies from game theory to deal with adversarial picks and here you could reach a positive expected value. Kind of a "yes, and..." approach. You acknowledge their view, and then you add a new perspective. But don't say they're wrong. Funny enough in situations where I suspect the interviewer was given the question it probably wouldn't have helped, not due to emotional attachment, but because the interviewer had a tenuous grasp of the topic themselves and couldn't stray from the script they were given.
- qarl 2y agoI think you're missing something. Presumably Balmer did ask this question. At least a few times. And yet he never heard of the correct answer, and believed the incorrect answer to be correct. That tells you that if anyone did say "actually, you're wrong" he never listened to them.
- Jalad 2y agoIs this a perfect example of broken modern tech interviews? Balmer's question seems fair for the complexity of the answer he was expecting. As the interviewee you would presumably provide the (mathematically) wrong answer, but you'd show your thinking along the way, including a small demonstration of CS principles. Keep in mind that Balmer had a long career, so if he ever asked this question, it was probably back in the 80s when no one expected you to come up with the complex solution outlined in the post. If you did outline the correct answer, that would be amazing, and you'd be an instant hire. But the question doesn't fundamentally seem broken to me because either answer (taking the bet or not) needs to be well justified.
- langcss 2y agoYes because it is a question for a quant.
- rustybolt 2y agoThe question seems like a mathematical one. What you're saying sounds to me like "your answer doesn't need to be correct, it just needs to sound reasonable". What you're filtering on with this question is good bullshitters. To me, the only reasonable to this question is "I don't know". I think even a mathematical genius like Terrence Tao would not be able to give you the answer to this on the spot. (Although I can also totally believe that he would instantly see this from some obscure theorem that only like 5 people on the planet know.)
- IanCal 2y agoNo, it's about understanding what an interview is for. They're not trying to get the answer. They're trying to find out what you know, how you think and how you communicate. Do you spot that it's different with one Vs many plays? Do you spot the binary search? Do you spot that an adversarial opponent can push things? Can you clearly communicate these? If you just say "I don't know" and that's it you are showing you don't know how to communicate important information and miss soft skills about understanding the context of an interview. If you say "I don't know" and talk through your thoughts then great. The point is talking things through, even if you have gotten the wrong answer. Maybe you'd be able to say "and here's how I'd code a simulation to check"
- deleted 2y ago[deleted]
- beeflet 2y agoI don't work in the tech industry but I always assumed these questions were designed for you to demonstrate your problem-solving skills, regardless if you get the answer correct or not. In this case, it would just be showing that you can reason about binary search and showing that the mean profit is 0.20 dollars
- noname120 2y agoWell to be fair Steve Ballmer is a terrible leader and if he had to take the tech interviews he wouldn't have passed and Microsoft wouldn't have stagnated for 10 years, before Satya Nadella took over and brought the company back on its feet.
- ywvcbk 2y agoHe’s probably a decent leader just not a very good CEO for a company that needs to develop new products and enter new markets to continue growing rather than to try and squeeze every remaining penny from their current customers.
- smolder 2y agoSatya Nadella has been good for the stock price and is probably a better leader than Ballmer, but hasn't made MS into a respectable company.
- high_na_euv 2y agoMany Satyas successes started under Ballmer.
- noname120 2y agoCould you give some examples?
- high_na_euv 2y agoBiggest one: Azure, then Bing https://blog.jovono.com/p/ballmer-microsoft-underrated https://blog.jovono.com/p/ballmer-microsoft-underrated
- thih9 2y agoAs long as it's used to figure out if the two parties would enjoy working with each other, I guess it's fine. But yes, increasingly often this turns into a quiz or worse. At least we get some quality fiction like https://aphyr.com/posts/340-reversing-the-technical-interview https://aphyr.com/posts/340-reversing-the-technical-intervie... and its sequels.
- TheCondor 2y agoI think this is a good question, there are many veins of potential discussion which is what you want. It’s not likely a binary question. Is it fair? Does he change his choice or pre-record it? Can you play multiple times? Purely random distribution, totally fair? Sure play the game every time, the math pans out. It’s not that though. It’s about showing your work
- leni536 2y agoCan't wait for the paper that solves for the Nash equilibrium for this game.
- arianvanp 2y agoBallmer Peaking - an optional strategy for a number guessing game
- lazyasciiart 2y agoIsn’t that what the Arthur O’Dwyer link gives?
- fph 2y agoSteve 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.
- koolala 2y agoWe let our computers play. My computer's AI vs Ballmer's AI. One trillion six hundred eighty-three billion thirty-six million fifty-one thousand nine hundred eighty-four computer games in 30 seconds.
- deleted 2y ago[deleted]
- koolala 2y agoWhat if he flips a coin? 50% chance to optimize for Binary Search and 50% chance to optimize for Ballmer Search?
- cbanek 2y agoOf all the things that Ballmer was wrong about... I guess this is one of them.
- jimt1234 2y agoMy personal fav: https://www.youtube.com/shorts/rCszxibClKE https://www.youtube.com/shorts/rCszxibClKE
- cbanek 2y agoMy favorite Ballmer practice is stack ranking. It completely screwed up the entire company. I worked on Windows Mobile at the time the iPhone came out. We were all shitting ourselves.
- Varriount 2y agoOof, that does not sound like a strategy that culminates a positive work atmosphere.
- muststopmyths 2y agoStack ranking existed at MSFT before Ballmer became CEO, i.e., when billg was CEO. It was a practice that Jack Welch brought into the corporate world and Microsoft was just guilty of following what were thought to be best practices at the time. Source: worked at Microsoft before Windows Mobile was a thing. As an aside, Windows Phone was my favorite phone OS and Ballmer seemed like the one who actually cared about it a lot.
- RaftPeople 2y ago> best practices Tangent: I love that phrase. Anytime I hear someone make that statement I think about the 9,000 things that have been considered "best practice" until we actually understood that they weren't even "good practice". It gets thrown around as if it's been studied and confirmed when in reality it means "a bunch of people are doing it"
- 2y ago
- ajcp 2y agoAfter 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.
- nighthawk454 2y agoThis 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
- nopinsight 2y agoKelly Criterion Betting more than the Kelly fraction increases the risk of ruin, especially in the long run. https://en.m.wikipedia.org/wiki/Kelly_criterion https://en.m.wikipedia.org/wiki/Kelly_criterion Note: Not saying that this is applicable in the original post's situation. It's relevant to the parent comment though, and very useful in many situations, such as investing.
- nighthawk454 2y agoYes, precisely. Although that's more about bet sizing for optimal return in the long run, not quite about binary choice of whether or not to play. But conceptually bang on, I had it in mind
- n4r9 2y agoWhat if I wanted to maximise the bottom 5th or 10th percentile of wealth?
- energy123 2y agoFractional Kelly?
- nehalem 2y agoI 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.
- thih9 2y agoI'd like an online demo where you play as Ballmer against an opponent using this strategy.
- tromp 2y ago> 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.
- thaumasiotes 2y agoPreliminary analysis: one in every three numbers has this undesirable property; the edges mess this up but shouldn't be able to add more than two extra undesirables; it should be impossible to have more than ceil(33.333) + 2 = 36 undesirables. (Also, since six bits will serve to identify 64 different numbers, it should be impossible to have more than 36 numbers that can't be identified that way.) I'll update with boring manual data later. ---- update ---- That was wrong; using a naive guessing method, I found 37 values that require 7 guesses.
- gukoff 2y agoThanks for spotting it! Exactly right, I fixed the text.
- malthaus 2y agomoral 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?
- balazspeczeli 2y agonot being a billionaire doesn't automatically make you a loser a better moral of the story would be "a billion dollars does not guarantee that someone is right"
- randomdata 2y agoI don't know. Play his game just shy of two trillion times and it will be you with the $120bn net worth! It seems the real moral here is: The best time to plant a tree was 20 years ago.
- tfwnopmt 2y ago[dead]
- dang 2y agoRecent and related: Steve Ballmer's incorrect binary search interview question - https://news.ycombinator.com/item?id=41434637 https://news.ycombinator.com/item?id=41434637 - Sept 2024 (240 comments)
- draluy 2y agoI 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?
- larsnystrom 2y agoI'm no mathematician, but I think that if you know something about the probability distribution before searching, then you can be more efficient than blindly using binary search. And if you assume Ballmer is out to get you (i.e. the distribution is not random) then you can use that information to improve the search speed.
- abigail95 2y agoBinary search wins in the average case on random data. Ballmer is not required to choose randomly.
- pnt12 2y agoThe point is that Ballmer is an adversary, and may choose the worst cases for binary search. As I understood, the algorithm in TFA holds against any choice. As others said, if you don't expect adversary behavior in your data, it should be good enough.
- Lockal 2y agoIf a second party can submit adversarial values into a system, potentially causing a denial of service in a binary search (where comparisons are computationally expensive and data is unevenly distributed), there is a much simpler solution: avoid using sorted collections and binary search. Instead, use hashmaps. To address similar HashDoS attacks, many implementations (in Python, Rust, Java, etc.) use a randomized hash function, which vaguely resembles the idea of randomizing starting value for binary search.
- fnord123 2y ago> 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.
- gavindean90 2y agoI 100% believe Balmer had an off by one error
- quuxplusone 2y agoFrom my own blog post (linked from TFA): > If Ballmer is choosing his secret number uniformly at random, then the expected value of the game is [that you win $0.20]. But, as Ballmer points out in the linked video, if he knows you’re going to do a plain old binary search, then he certainly won’t ever choose 50 as his secret number. In fact, he has no reason to choose 25 or 75 either. Or 12, 13, 37, 38, 62, 63, 87, or 88. If Ballmer avoids those eleven numbers, and chooses uniformly at random from among the rest, that alone is enough to lower the expected value of the game from [$0.20] to about [−$0.0045]. So I think Ballmer was being perfectly honest in what he said: he does know a strategy that makes the expected value of binary search counterintuitively negative, and that strategy is (as he says explicitly) to avoid the first few numbers that you're going to guess. No further speculation about errors or deception on his part is needed.
- veltas 2y agoHonestly I think Ballmer would have appreciated this answer in an interview.
- arduanika 2y agoOnly if he were hiring for game theorists game theorists game theorists game theorists
- WalterBright 2y ago> 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.
- gwd 2y ago> 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. If I were to take the bet with him, I'd make him write down the number first hide it (turn the paper over / put it under a book, whatever).
- Lockal 2y agoHere is a chart for probabilities for starting value: https://docs.google.com/spreadsheets/d/e/2PACX-1vThljkK2nUILt_emMyPpFbdwvgVYpeaGsgPIswKopeFcQsofetYjKqojFCLn-w_kM4PCZczKhIcsQ7i/pubchart?oid=412606124&format=interactive 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.
- gukoff 2y agoThis really depends on the pure strategies that you choose. The initial set of strategies wasn't very diverse and compensated for the binary search "weaknesses" on the ends of the spectrum by sometimes guessing 1 and 98. But after adding some more pure strategies to the set, we've got a far better mixed strategy that prefers the numbers between 28-70 as the first pick: https://github.com/gukoff/ballmer_puzzle#winning-strategy https://github.com/gukoff/ballmer_puzzle#winning-strategy
- Lockal 2y agoO, wow, post got update! > Avg win if Ballmer chooses randomly: $0.16247848000093376 > Win if Ballmer chooses adversarially: $0.14657033010415976 So the goal is to find a set of strategies where adversarial avg win == random avg win? Or these numbers will never be equal?
- TheDong 2y agoEdit: 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.
- kikimora 2y agoThis is brilliant!
- n4r9 2y agoNeat. A nice way to see this is to imagine that the numbers 1-100 are arranged around a clockface; you randomly spin the clock before doing a conventional binary search starting from the top.
- deleted 2y ago[deleted]
- fgna 2y agoUnfortunately the numbers are not circular :( By offsetting the initial number, the binary search does not work optimally right? Imagine the number is below 50, and you start by guessing 60, now you have to search for 30 numbers instead of 25, and thus the binary search is not optimal. reply
- TheDong 2y agoAh, yup, you're right. Ballmer's answer of "high or low" isn't in the offset number system, but the normal one, so my strategy doesn't work. That's what I get for not thinking it through properly, thank you for pointing that out!
- rcxdude 2y agoWhen 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.
- GuB-42 2y agoThat's what I thought too, kind of like Absurdle, an adversarial variant of Wordle: https://qntm.org/files/absurdle/absurdle.html https://qntm.org/files/absurdle/absurdle.html It is by the author of HATERIS, a variant of Tetris that always gives you the worst piece.
- imtringued 2y agoThis 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.
- iainmerrick 2y agoRight! 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?
- jessriedel 2y agoI 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.
- mrgoldenbrown 2y agoHis 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.
- wed239023 2y agoI 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...
- mattmanser 2y agoHe also doesn't say he wants to play in this reality where the rules of maths hold. That his one and your one mean the same thing. That your accent doesn't have to match his. That you haven't got to be holding a certain pose when you say it. There are always implied rules, and Ballmer's implied rules are he'll use a whole number, not change his number and be fair. You could probably spend now until the end of time adding stipulations and he'd still be able to cheat. I'd recommend never learning about philosophy as you'll disappear into nihilsm. And lottery wins aren't taxable every where on the planet (e.g. the UK), so you made the same "mistake" as the author too!
- vjo 2y agoI 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.
- dooglius 2y agoNice! 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.
- zug_zug 2y agoI 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!
- deleted 2y ago[deleted]
- tromp 2y agoA 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-search/ https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s...
- gukoff 2y agoThank you, this is very interesting
- nojvek 2y agoIt 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.
- vismit2000 2y agoLittle Mathematics Library – Elements of Game Theory: https://mirtitles.org/2012/09/06/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."