|
So someone asked me a go what kind of interview questions i ask people as staking candidates in my poker ring.
Sometimes i get bored and throw out some brainteasers... Usually these require a bit of thought, a lot of inductive reasoning and a bit of lateral/out of the box thinking
This is one of my favourite questions, and relates to a real life game my dad once played haha
There is a room of 1000 people. In this game, there is a referee that flips the coin, standing in front of everyone else.
Everyone pre-emptively picks heads or tails. The coin at the front lands, and everyone who chose correctly stays standing, and everyone who chose wrong sits down.
Then you play the game again, until there is one person left, and that last person wins the prize!
Oh, and if nobody is left standing, then nobody wins the prize 
What is the optimal strategy? Does it even matter what you choose?
How should your strategy change if there are only 10 people?
I'll give a few hints here too, and thoughts and discussions, try not to spoiler until you've thought about the question hard first
+ Show Spoiler +Hint 1: + Show Spoiler +Obviously in a perfect, game theoretic world, where everyone chooses randomly, your chances of winning are 1/1000 no matter what you pick (on average). But that would be a boring question Hint 2: + Show Spoiler +People in general pick heads more than tails. Why is that? Hint 3: + Show Spoiler +It's a pretty well known fact that in rock paper scissors, your average person hates picking the same choice 3x in a row. Hint 4: + Show Spoiler +Remember that assuming you picked correctly, the only people who are left will have picked exactly the same as you. Even if you cannot improve your odds from the previous rounds, is it possible to improve your odds by considering future rounds? Hint 5: + Show Spoiler +That is, if you pick T first, but are unsure what you pick for the second round, consider if you are in any better position if you went TTT as opposed to THT
Hint 6: + Show Spoiler +Did you know if you have no randomisation in your strategy, and someone else picks the exact same strategy as you, your chances of winning are zero? Hint 7: + Show Spoiler +Is it more likely that someone is going to pick the exact same strategy as you if there are 1000 people or 10 people? Hint 8: + Show Spoiler +When my dad played this game, there were 100 people in the room. 94 people chose heads first and got knocked out! Hint 9: + Show Spoiler +So if TTT is the best choice for the first 3 picks, then what are the chances of someone playing the same strategy as you? Is T all the way a good strategy? Hint 10: + Show Spoiler +I lied, there isn't exactly an optimal strategy, as this is very game theoretic! In fact, the only optimal strategy in one sense is if everyone picks random all the time! What i am really looking for is a MAXIMAL strategy. And of course, maximal strategies are very tough to come up with! A good strategy would be for example, TTT and then afterwards always picking random. But are there better strategies which beat this? You arn't just playing against 1 person!
|
original post
+ Show Spoiler +So I recently had a homework assignment where the whole class had to write Rock Paper Scissors program and winning program gets extra credit. Essentially, the program had a requirement to beat default programs, such as one that went all rock and programs that repeated. It also had to beat programs that had a slight bias towards one but is relatively random. (more often goes scissors then your program must more often go rock or something like that).
To do so, one method (of many) was to create some sort of database where you look at the x previous things your opponent did and what your opponent did to follow it. For example, if your opponent goes RR = > S 5 times and RR => P none and RR = > R 45 times, then you would throw out P. Also, you to beat these programs you could write a program that considered your own moves as well as the enemy's or something.
In this situation, since you always have a 50% chance of getting eliminated, it is optimal to choose your minority. Considering that, you could write a program that observes your opponents and guesses their moves based of previous decisions and try to be the minimum and then pray or bribe. Also trying to rig the coin is a good strategy.
Anyways, programs could be written to beat a 2% bias towards scissors 99%+ of the time out of 1K games O__O Relatively amazing. Also, some programs completely dominated mine that did the above T___T Really fun assignment, but of course this one is a lot more luck based.
edit: the above example for looking at previous 2 moves could be done for previous, previous 3 etc. also can do something where you compare peoples responses based of overall statistics of previous rounds. etc
edit
edit: im retarded
edit2: wait im not
|
Very similar ideas, though H's and T's is a much easier concept to get around - also the idea of randomisation and strategy bias doesn't come in till very late in the thought process
Especially in this case, it is very dangerous to over-think yourself - you must first consider the field of players you are up against and how that should be affecting your strategy
|
United States24755 Posts
This question seems too open ended to me. Rather than giving hints we can optionally take into account you should decide what should and shouldn't be taken into account. For example, why don't you make a list of betting behavior that we should accept as fact? Otherwise we won't really make any progress on this issue.
What can we take as given in this question? If that's up to us then every answer is correct and not very useful.
|
This is weird. This isn't like RPS where you play against other players so all that psyschological stuff comes into play. Here you just choose H or T and pray referee spins that coin well for you. Having said that, solution is obvious.
+ Show Spoiler +
Edit: Oh wait im stupid. But my solution still stands :p.
|
Really neat idea, thanks for posting. 
I guess assuming every sequence of flips is equiprobable, you maximize your chance of winning at each step by choosing the next flip that the fewest other people would choose. It's interesting that unlike poker, at every step, you're competing against people who've made the exact same choices as you to date. So you can't really get any extra information out of them dynamically just based on their choices, like "this guy is a bluffer", etc. (Simplification: Although maybe you can get a psychological "read" on them and guess what they might choose in the future... but to simplify things I'll leave that out.) This simplifies things dramatically.
I don't think it matters that much how many people there are. In any case, you want to choose the next choice that probabilistically speaking, the fewest others will choose. (Simplification: Other people may change their choices based on the number though, so in an ideal world you would account for that.)
So I think a very good approximation to an optimal strategy is if you could discover the distribution of what people would choose in this situation and pick the one that at each step that the fewest people will choose next time. This is mostly a psychology problem.
e.g.
1. Since most people pick heads, start with tails.
2. Given a history of T, since other people feel that they want to act "random", they're likely to switch to H, so stick with T.
3. Given a history of TT, since other people still feel that they want to act "random", stick with T.
...
6. Given a history of TTTTT, since you're probably up against really stubborn people, switch to H.
...
20. Given a history of TTTTTTTHHHHHTHTHT or whatever, probably someone else is doing the same analysis as you, so switch it up away from this strategy.
If we were taking this really seriously I'd try to gather a lot of data on this.
If we were taking this even more seriously, I'd try to factor in the possibility that a coin is biased. Most coin flipping is probably fair to 2 decimal places, but given a history of TTTTTTTTTTTTT this should give you some evidence that the coin may not be fair. You'd probably want to use Bayesian analysis, factoring in your prior belief as to the distribution of the fairness of the coin & flipping process. (Given that history of mass tails I'd probably still switch at some point to heads, based on the psychology, but it's a tradeoff -- a less likely coinflip but more likely to win.)
|
Couldn't you just lie and stay standing? I didn't see anything that implied the decision had to be made "officially,"
|
8751 Posts
On December 06 2010 02:41 LazyMacro wrote:
Couldn't you just lie and stay standing? I didn't see anything that implied the decision had to be made "officially,"
neither is there any implication that an official who officially heard your pick compels you to sit down. it's simply that you make a choice before the flip and if your choice is wrong you sit down. in other words, no there's no room for lying. you must make a choice before the flip and if the choice is wrong you must sit down. there's no communication going on, so no room for lying.
|
Well, this question was quite impossible to answer until you told us that
+ Show Spoiler +
+ Show Spoiler +Using that we know that tails will be the pick for the first round since it's the most uncommon pick and we therefore have a higher chance of being alone in the end.
Later on you will want to take whatever has just been drawn. So, if the referee get's heads, you should bet on heads next time.
Here we have a problem however, your series would just look like TTTTTTTT using this method. We can assume that at least one of your co-competitors has "broken the system" similar to you so just going TTTTT the entire time will not be optimal. Therefore you should mix in some heads. Now, the later in the game that you switch to heads, the more likely it is that you will bump out the guy who has understood and not just some fluke who got by on luck.
Therefore, you should go TTTTTTTTTTTTTTTT all the way until only two persons are standing and then go heads. This falls apart if more than one person has figured it out so a general rule of thumb could be something like TTTTTHTTTTTHTTTTTHTTTTTH. That should weed out the smart people while you are not going THHTHHTHHTHHTHH like a normal person would do.
|
This game is the basis for making money on the stockmarket.
|
Err, don't you just have 999 pick heads, 1 pick tails, and repeat all the way down?
Or is "optimal" very important, in which case you want to get rid of 1/2 all the way down.
IE 10--> 5 stay --> 2//3 stay --> 1//2 stay --> 1 stays.
I didn't look at hints, it just seems really easy to me, im probably oversimplifying it.
Oh ok, you're 1 of 1000 people? that makes more sense. I guess you always want to choose the minority since its 50:50 but you remove more competitors.
I guess according to the hints you keep choosing tails until you think anyone now choosing tails is doing it for a strategy.
|
On December 06 2010 02:06 micronesia wrote:
This question seems too open ended to me. Rather than giving hints we can optionally take into account you should decide what should and shouldn't be taken into account. For example, why don't you make a list of betting behavior that we should accept as fact? Otherwise we won't really make any progress on this issue.
What can we take as given in this question? If that's up to us then every answer is correct and not very useful.
I suppose in some ways i am being very unfair, and also being very unspecific, which is actually kind of the point
I'm deliberately missing out key information and im requiring the guy i interview to use some inductive reasoning, with the risk that he knows he could just be flat out wrong. Indeed in poker this kind of reasoning can have absolutely catastrophic results, but at the same time it is indicative of all the highest level thinkers.
Indeed, if i gave you a list of behaviours which you could take for granted, the answer is really kinda trivial and anyone could work it out, though the hints give a lot away
Oh about the stockmarket, just had my JPmorgan Trading interviews... wish me luck :x
|
|
|
|
|
|
EPT
