[HN Gopher] Nash equilibria in Ballmer's binary-search interview...
___________________________________________________________________
Nash equilibria in Ballmer's binary-search interview game
Author : xlinux
Score : 136 points
Date : 2024-11-17 13:30 UTC (6 days ago)
(HTM) web link (quuxplusone.github.io)
(TXT) w3m dump (quuxplusone.github.io)
| moomin wrote:
| One day it is hoped that enough mathematicians will have worked
| on the problem to have finally, definitively answered Steve
| Ballmer's interview question. The job will be shared between
| them.
| vlovich123 wrote:
| Just in time for the job to be replaced with AI.
| Onavo wrote:
| Well, Terrence Tao is trying his very best to replace himself
| with an AI.
| pfdietz wrote:
| Which, admittedly, seems like a much harder problem.
|
| A world in which AI churns out amazing proofs would be
| pretty radical though.
| Xcelerate wrote:
| Terence is fascinating in how different his thinking is
| even from most other mathematicians.
| vlovich123 wrote:
| I think he's trying to replace his grad students so that he
| can solve even more interesting problems.
| mekoka wrote:
| The real irony being that they show up to work just to discover
| that it was a software programming position.
| hehehheh wrote:
| But they can't quit once they taste that sweet total comp.
| drewcoo wrote:
| The "golden abacus" instead of "golden handcuffs?"
|
| Or as my undergrad mathematics advisor described friends
| who left academics for finance, "they spend their days
| clipping (stock) coupons instead of solving math problems -
| not as interesting but more interest."
| divbzero wrote:
| s/stock/bond/
| hehehheh wrote:
| You could be apply for grants all day and doing uber at
| the weekends you sell out!
| belter wrote:
| Rumor has it that Ballmer resigned after asking this question
| to a candidate named Aphyr...
| rileymat2 wrote:
| With these types of trick questions, it is always interesting
| what is an acceptable trick and what is not. The question did not
| specify whole numbers as it does not specify a random selection,
| but one is in bounds and the other not.
| jhfdbkofdchk wrote:
| I always felt that part of the interview process is the
| candidate asking clarifying questions as well as making and
| stating assumptions.
| mdswanson wrote:
| It is. Or at least it was for some of us. I didn't care if
| the candidate ever got the right answer. I cared about the
| thinking, the questions, the strategies, and the
| conversation.
| TZubiri wrote:
| And if some interpretations lead to trivial solutions, but
| one leads to a complex problem, it's likely that their
| intention is the latter. A kind of tacit communication
| MarkusQ wrote:
| Actually, it may just as likely be that the interviewer
| is looking to see if you over complicate things. So
| _ask_.
| jnordwick wrote:
| I hate that. It turns the problem into one of those lateral
| thinking puzzles we were told some basic information and then
| the answer winds up being something totally wildly different.
| It wasn't being very random in the end not being very
| productive
| kadoban wrote:
| Are we describing interviews here, or the process of
| software engineering in practice? It could be either imo.
|
| Those clarifying questions and some of the thinking through
| consequences are the only really topical part of SE
| interviews, the rest is just math you won't use on the job
| 99.99% of the time anyway.
| petesergeant wrote:
| > it is always interesting what is an acceptable trick and what
| is not
|
| I have not found the type of person who asks trick questions to
| be the type of person who finds it interesting to have the
| trick questions they've posed to be prodded.
|
| Completely tangential, but something I enjoyed reading that
| feels in the same realm:
| https://blog.plover.com/math/logic/annoying-boxes-solution.h...
| krackers wrote:
| >I enjoyed reading that feels in the same realm [annoying
| boxes]
|
| I had to reread that a few times to figure out what he was
| saying. All that comes down to is the fact that in his
| presentation technically there's nothing linking the
| propositional value of the box labels to the box contents. In
| most puzzles this linkage specified "outside the puzzle
| world" but in this case it's specified "inside the puzzle
| world" and so nothing can be deduced from it. But any sane
| person would assume the two align (especially in the setting
| of a puzzle), and so there's the gotcha.
|
| Seems very different from the kind of "trick" questions in
| interview which are closer to one-way questions where the
| problem is trivial with some key insight but quite hard
| otherwise.
| petesergeant wrote:
| > any sane person would assume
|
| I disagree, and when I first encountered it it seemed
| pretty obvious to me, but maybe I'm just used to question
| where the answer can be "not enough information"
| dullcrisp wrote:
| I assume the real point of the puzzle (which is lost in the
| post) is to demonstrate how not all statements have a
| definite truth value.
|
| If we assume that the label on the red box must be either
| true or false then we can prove that the treasure is in the
| red box. We'd be wrong though, since the treasure is in the
| green box.
| thaumasiotes wrote:
| Well, that might be the point of the parable of the
| dagger that he links to. It can't be the point of Mark
| Dominus's puzzle, because Mark Dominus doesn't understand
| it:
|
| > So if you said the treasure must be in the red box, you
| were simply mistaken. If you had a logical argument why
| the treasure had to be in the red box, your argument was
| fallacious, and you should pause and try to figure out
| what was wrong with it.
|
| He doesn't really elaborate on this, because he doesn't
| know the answer:
|
| > Here are some responses people commonly have when I
| tell them that argument A is fallacious:
|
| > "If the treasure is in the green box, the red label is
| inconsistent."
|
| > It could be. Nothing in the puzzle statement ruled this
| out. But actually it's not inconsistent, it's just
| irrelevant.
|
| This is an unfortunate point in an otherwise good essay.
| The problem in the puzzle is precisely that the red label
| is inconsistent, in the ordinary sense that no matter
| what you assume about it, a contradiction will result.
| Its truth implies its falsity, and its falsity implies
| its truth. Holding the location of the treasure fixed, no
| Boolean model exists in which the red label has a truth
| value at all.
|
| The puzzle is an example of the Cretan paradox; there's
| not much more to it than that. It catches more interest
| because it's presented as if it were a different kind of
| puzzle than it is.
| Scarblac wrote:
| No, that is a red herring, as he explains. It's not about
| the labels at all, there's no reason to assume the writer
| of the labels even knew anything about the actual
| location of the treasure. They're not part of the puzzle
| rules.
| thaumasiotes wrote:
| That won't stop them from being inconsistent.
| Scarblac wrote:
| No, the point is that even if both labels had said "the
| treasure is in the red box" then it still could have been
| in the green box. There is no reason why the labels
| should be expected to say the truth, they're just labels.
| petesergeant wrote:
| Quite. It's the difference between:
|
| > You wake up in front of a box which has a label that
| says "treasure inside". Should you assume there is
| treasure inside?
|
| to which the answer is clearly "maaaaybe?" and
|
| > You wake up in a world with accurately labelled boxes,
| in front of a box which has a label that says "treasure
| inside". Should you assume there is treasure inside?
|
| Where the answer is yes, and if the person setting the
| problem says "hahah no!!!" you can say "well look, that
| wasn't a fair puzzle".
|
| It is primarily a "do you have sufficient information"
| problem, like in the GMAT, with a level of misdirection
| thrown in.
| wat10000 wrote:
| I don't see why anyone would assume a link between the
| labels and the contents. We see this in the real world all
| the time. You see a tin of delicious cookies, then open it
| to discover disappointing sewing supplies. The sign on the
| door says Open, but the owner just forgot to flip it and
| the store is actually closed. Some joker puts a Ferrari
| badge on their Kia.
| dwattttt wrote:
| > I have not found the type of person who asks trick
| questions to be the type of person who finds it interesting
| to have the trick questions they've posed to be prodded.
|
| I find it depends entirely on whether the person is asking a
| trick question to try prove themselves smart (and are
| sensitive about it), or as in this case, are confident in
| their own intelligence, and want to assess yours.
| ivanbalepin wrote:
| Not confident but overconfident in this case. Clearly
| nobody has ever told him it's a crappy question (unless
| you're interviewing for a math PhD or something), and wrong
| on top of that, and he didn't have enough self-awareness to
| double check. Or maybe somebody did tell him, but he didn't
| care to listen.
| thrw42A8N wrote:
| Or maybe he's testing how you deal with that situation.
| It's a job interview, not a school exam.
| jonahx wrote:
| Technically true but if real numbers are allowed you don't have
| a puzzle. Rather, you have a silly puzzle that consists in
| checking if the interviewee will say, "Waaaiiiit a second, is
| _any_ number allowed? Because then you can never win! " and the
| interviewer saying, "Nicely done!". Nevertheless, the
| assumption should be stated.
|
| The random selection omission is intentional.
| rileymat2 wrote:
| And that's all hinged in the expectations of the intent of
| the question, if it is attention to details, the real number
| scenario is completely reasonable. If it is not, you can pick
| apart these types of puzzles and seem overly hard to work
| with.
| drewcoo wrote:
| Those problems allow follow-up questions to better define
| things. In fact, as initially stated, the problems are usually
| so vague as to require follow-ups.
| GuB-42 wrote:
| It also doesn't mention if Ballmer is able to change the number
| during the game. If he is only "thinking" about a number
| without writing it down beforehand, nothing stops him from
| doing it, as long as it is consistent with all the statements
| he made.
|
| This trick actually makes the problem easier, you always need 7
| tries, and the payoff, and not just the expected value is $940.
| Of course, if these are not whole numbers, the payoff is $0.
|
| Now you can continue the interview whether you would cheat if
| you are guaranteed not to get caught, as it is the assumption
| you made for Ballmer here ;)
| joshka wrote:
| Previous comments yonder:
|
| - https://news.ycombinator.com/item?id=41434637
|
| - https://news.ycombinator.com/item?id=41463330
| jnordwick wrote:
| Can't this be solved to some sort of DP way of solving the sub
| problem?
|
| Do the payout between 0 and 1 as the percentage of the amount.
|
| With a range of 1 to 1 to pay off is obviously one
|
| With a range of 1 to 2 the payout is .5
|
| At three values it becomes more interesting. There are two
| strategies for the candidate either a binary search for the
| endpoints.
|
| At four values you still have one level of binary search possible
| but after that it devolves down to the two value problem.
|
| At five values. If the interviewer thinks the candidate would
| choose binary search and it becomes too too value problems on
| each side after removing the middle element.
|
| There's definite problems with this but I wonder if he's already
| possible pay off matrix
| jonahx wrote:
| It's possible it could help but it wouldn't be lead to a
| typical clean DP problem, because you need the full mixed
| strategy vectors at each level. That requires N real numbers
| that sum to 1, for each player.
|
| Assuming you've found such a strategy for N, when you go to N+1
| you still need to find the (N+1) element vector representing
| the probability that you select each number as your first
| guess, and you likewise need to know your opponent's
| probability vector for adversarially choosing a number. Once
| you guess at those vectors you can use your recursively built
| up DP sub-solutions to get the value of the game, but you are
| still stick with solving the optimization problem of finding
| those mixed strategy vectors for N+1, and will probably need
| something like CFRM or a similar technique to find them.
___________________________________________________________________
(page generated 2024-11-23 23:01 UTC)