ITH Poker Forum

[darvon]

There is a famous problem in Mathematics that I have heard called "The Miss America Problem". I need the answer for RL, and I want to check my memory, but I can't find a write-up via Google. I need some help. I will describe the problem, you might know it by another name, or you simply may be better at Google than I.


The Miss America Problem:

You are judging a beauty contest. You need to pick the most beautiful girl among 50. But the judging system is unusual. The girls come out one at a time on stage and then go offstage. You may only pick your selection while the girl is onstage. Once you pick the girl, all the prior girls and all the girls not yet to come onstage are discarded. Once a girl goes offstage she cannot be selected. There are 50 girls.

What is the strategy to pick the prettiest girl you can from this system.

[darvon]

Call off the dogs.

Ifound that it is also called The Secretary Problem or The Sultan's Dowry Problem and I retrieved the solution for the optimal strategy and it matched my memory from 35 years ago.

So why can't I remember what I had for lunch yesterday?

[the_hawk]

Hadn't seen this one before. The solution is incredibly simple and (to my mind, given it's simplicity) amazingly powerful.

[mconstab]

The solution is incredibly simple

Not to me it isn't

[Damien]

I googled it and I still don't really understand the solution (but I am not a maths guy). Look at about a third of them and then pick the first one that comes out that is prettier than any of the previous? But what if all the really hot ones come out early? Bah, maybe Hawk or someone can explain it better.

[the_hawk]

But what if all the really hot ones come out early?

A few points spring to mind after thinking about it a bit.

This should be noted as a pretty good (the best) strategy for picking THE best candidate. You "only" have a 37% chance (slightly higher if N is small), but given the constraints you face, that sounds pretty good to me. The intuitively amazing thing to me is that you have a 37% chance even if the number of candidates is enormous.

Also note that there seems to be a certain amount of "all or nothing" in this strategy - it's directed towards picking THE best candidate rather than an "acceptable" alternative.

Nonetheless, and in terms of Damien's question, you only have a really serious problem if THE hottest one comes out early - in that case you're forced to pick the last candidate and you're down to random chance, which is obviously pretty poor especially where N is large.

If the second-hottest overall is the hottest that comes out early, you're home and dry.

If the p'th hottest overall is the hottest that comes out early, you're guaranteed one of the (p-1) hottest of the whole field, each of these with equal probability.

Maybe putting it like that helps?

[the_hawk]

Let's think about it a bit more. For simplicity's sake, let's say that you summarily reject the first third (rather than the correct 1/e) proportion of candidates, and let's suppose the total number of candidates is relatively large.

There is a 1/3 chance of the top candidate appearing early, in which case you are stuffed.

There is a (2/3 * 1/3) = 2/9 chance of the second-top candidate but not the top candidate appearing early, in which case you are guaranteed a win.

There is a (2/3 * 2/3) = 4/9 chance of neither of the top two candidates appearing early, which means there is a 2/9 chance of eventually picking the top overall candidate and a 2/9 chance of picking the second-top candidate.

So, unless I've ballsed it up (and those fractions are not quite right) it's not as all-or-nothing as it first seems; you have something approaching a 2/3 chance of picking one of the top two candidates overall. That is perhaps even less intuitive than the original result. Have I messed it up?

EDIT: the bolded bit above is not right. If the third top candidate doesn't appear early either, then there is a chance you will end up picking that one. Back to the drawing board.

[the_hawk]

Needed some Excel to work it out correctly, but I finally worked out you have a 50% chance of picking one of the top 2 candidates, and just over 60% chance of picking one of the top 10 candidates. (And that's the case for any size of N you like).

[superwomble]

Wouldn't a better way be to see all the candidates, then pick the best one?

[Damien]

Thanks for the maths Hawk. Is 1/e always about one-third (I don't even know what e represents)? What happens with a very small sample size, like 2 or 3? If its 2, and a plain jane comes out, do you reject her and hope for a super-model or take her in fear of getting an utter troll? With a large sample size, it seems like you are saying that you are really only screwed about a third of the time, when the hottest one comes out early. In a sample size of 100, if we're down to our last 5 and we still haven't seen one as gorgeous as the first that came out (and by this time, we've got a pretty good grasp of the range of hotness), shouldn't we snap up a pretty good looking one instead of risking ending up with a dog by waiting for number 100?

[the_hawk]

Thanks for the maths Hawk. Is 1/e always about one-third (I don't even know what e represents)?

Yeah, don't worry what e actually means / represents, it's a constant with value 2.7

What happens with a very small sample size, like 2 or 3? If its 2, and a plain jane comes out, do you reject her and hope for a super-model or take her in fear of getting an utter troll?

Look at the Wiki page: http://en.wikipedia.org/wiki/Secretary_problem and scroll down to just below the first batch of equations. The table there shows the optimal strategy for small N. In that table, r is such that you summarily reject (r-1) candidates and then follow the strategy as standard, and P is your chance of success of doing so.

The table shows that with 2 candidates you reject none (r=1) hence take the first candidate, and you have a 50% shot. You can't do any better than random chance. (Kinda obvious).

With three candidates, r=2 and so you reject the first; it turns out you also have a 50% chance overall. You can work that scenario through in your head. If the three candidates are Hottie, Moderate, Troll then you win (select Hottie) depending on the order they appear:

H-M-T: lose
H-T-M: lose
M-H-T: win
M-T-H: win
T-M-H: lose
T-H-M: win

Note that you only end up with the troll in the first of these scenarios (probability 1/6).

With a large sample size, it seems like you are saying that you are really only screwed about a third of the time, when the hottest one comes out early. In a sample size of 100, if we're down to our last 5 and we still haven't seen one as gorgeous as the first that came out (and by this time, we've got a pretty good grasp of the range of hotness), shouldn't we snap up a pretty good looking one instead of risking ending up with a dog by waiting for number 100?

Not if you want to maximise your chance of getting the ultimate hottie.

[Damien]

Even if you throw the math out the window, the solution makes intuitive sense, as you alluded to in you first post, Hawk. Your gut reaction would probably be to check out a bunch to get a feel for what you're working with and then pick the hottest one that comes out.

Kinda reminds me of this promotion that a local radio station runs where they throw out dollar amounts until you tell them to stop. Except, the dollar amounts go up in increments of 10 and at a certain point there is an explosion sound and you get nothing. So really not like this at all

In that game though, I don't think I've ever heard the explosion. Contestants usually stop it somewhere around $150 and the DJ says (ominously) "Well, good for you. Just so you know, you could have gotten more... a lot more." I wonder if there is any optimal strategy for that. My thought was to just listen as much as I can for when the explosion goes off, find an average explosion point, and then stop it right before that. But like i said, I rarely get to hear the explosion.

This has got me thinking whether there is an optimal strategy for Deal or No Deal. I'm sure there is, but i don't think I've ever worked it out.

[darvon]

Hawk, did you read the part about the Googol Game? After I solved my RL problem, I started thinking about Googol strategies.

[Dogs]

After I solved my RL problem

You really think you can make a comment like that and not elaborate? Particularly when your original title was 'The Miss America Problem'?

[leofric]

This has got me thinking whether there is an optimal strategy for Deal or No Deal. I'm sure there is, but i don't think I've ever worked it out.

I always assumed it was to accept any offer that was the mean (or better though it's unlikely you'd get that!).Everything else is just putting pressure on the individual with large sums of money.

If there were two boxes left - one with $100,000 and one with 1c then you should accept an offer of $50,000 but reject all offers below, that way you would maximise the return. Of course it's easier said than done with only one chance and an offer of a significant amount of money which would be valuable to you.

In effect its a very good example of what happens when we play poker with scared money.