100 Wives

In a grand gesture, the sultan offers his guest a wife from his own harem. For good measure, the bride comes with a rich dowry. However, there is a catch. The guest may only see each woman once. One by one, they come and say,

"Honored guest, my dowry is the richest of all you have seen today. Will you marry me?"

or

"Honored guest, you have seen a dowry greater than mine today. I cannot marry you."

If the guest chooses a bride, and another woman has a greater dowry than the one that the one that the guest chose, the woman.. or women if there are several.. will be offended, and will arrange for the man to be assassinated. If the guest says "no" to the greatest dowry, the sultan considers him greedy, ungrateful, and insulting, and has him executed.

The guest ponders.. and then Abal the wild rose comes with her offer, followed by Ablaa the perfectly formed, Ain the precious, Almas the diamond, Amber the jewel..

How will the guest maximize his chances of choosing the right bride?

I think the guy is screwed 99/100 times, regardless of his strategy.

Not quite that bad as only some of the women.. more like one in five than one in 100.. are available.

So does the man have to choose whether or not to accept an offer right when it is made, without hearing the later women ? If he can choose at the end the problem is simple, just choose the last women who said she had the biggest dowry so far.

Originally posted by talzamir
In a grand gesture, the sultan offers his guest a wife from his own harem. For good measure, the bride comes with a rich dowry. However, there is a catch. The guest may only see each woman once. One by one, they come and say,

"Honored guest, my dowry is the richest of all you have seen today. Will you marry me?"

or

"Honored guest, you have seen a ...[text shortened]... Amber the jewel..

How will the guest maximize his chances of choosing the right bride?

isnt this a case of choosing when the odds are best that the one who says she has the biggest so far actually has the biggest of all. At a guess between #50 & #75.

My probability isnt up to doing it!

An exact answer eludes me too. As I see it, the real decision to make is to decide how long one should skip taking a bride so I did some monte carlo on it. The right choice can be any number, but the second to last - the last girl to say "no" to despite her having the highest dowry to date.. is more manageable. The best strategy I've found is to keep saying no until about 30-35 girls have passed, and then say "yes" to the next one who states she has the highest dowry yet. In one case out of the three the highest dowry comes very early, and there is not much you can do about it, and sometimes the latter two thirds include a dowry that is higher than any in the first third, but arrives sooner than the overall highest. The survival rate is better than one in a hundred though.. about one in four or thereabouts.

Easy enough do more or optimise, but, on 20 attempts that strategy got the suitor to say "yes" too early eight times, wait too long six times, and get a happy ending six times so the ballpark figure seems ok.

Originally posted by talzamir
An exact answer eludes me too. As I see it, the real decision to make is to decide how long one should skip taking a bride so I did some monte carlo on it. The right choice can be any number, but the second to last - the last girl to say "no" to despite her having the highest dowry to date.. is more manageable. The best strategy I've found is to keep saying ...[text shortened]... he survival rate is better than one in a hundred though.. about one in four or thereabouts.

I tried a dynamic programming approach to find the best strategy and must say I'm getting odds far below 25% of choosing correctly. My best strategy only claims 3,3% chance of making the right choice. My calculations are below.

Say strategy n is the strategy to wait until the nth woman and then choose the first who claims the largest dowry so far. Say p(n) are the odds that this strategy gives the right choice. Strategy 100 waits for the last woman. There is a 1% chance she has the largest dowry, so p(100) = 1%.

Now go to strategy 99. There is a 1/99 chance she claims the largest dowry so far. There is also a 1/2 chance that if she does, the 100th women still has a larger dowry. Then there is a 98/99 chance she doesn't have the largest dowry so far. In that case we'll wait for the 100th women, and waiting gives us the succes chance of strategy 100. In numbers this gives p(99) = 1/99*1/2+98/99*p(100).

In general we get the following formula. p(i) = 1/i*(1/(100-i+1)) + ((i-1)/i)*p(i+1).

Anyone sees anything wrong with this approach ? Might be a problem with the excel implementation as well.

I get a very nice curve with that function with that, and it seems that the optimal strategy would be p(71), which takes quite a bit of nerves. It feels counter-intuitive to wait that long.. and it doesn't match my, admittedly limited, go at monte carlo, which suggests that the optimal choice would be to prepare to say yes a lot sooner, and to have a far better chance of success. With a bit over 16,000 runs, the average number of women who have the largest dowry to date is about 5.2, ranging from 1 to 13. With a slightly smaller database, 146 runs of 100 random numbers each, the top strategy seems to be about p(40), and of those who would've chosen it, about 30-40% would have survived.

I wonder why our numbers differ so drastically? I don't know if my figures are right, but after enough experimenting I'm fairly sure that the one in three to two in five seems the right ballpark figure for chance of survival with optimal strategy?

Originally posted by talzamir
I get a very nice curve with that function with that, and it seems that the optimal strategy would be p(71), which takes quite a bit of nerves. It feels counter-intuitive to wait that long.. and it doesn't match my, admittedly limited, go at monte carlo, which suggests that the optimal choice would be to prepare to say yes a lot sooner, and to have a far be ...[text shortened]... to two in five seems the right ballpark figure for chance of survival with optimal strategy?

The average of 5.2 "highest dowries so far" does make sense. It's easy to calculate that there is a 1/i chance that the i-th women has the highest dowry so far. Sum that for i from 1 to 100 you get 5.1874...

Might have to check my calculations if they are that far from the monte carlo experiments. Do you see anything wrong with them ?

D'oh pretty obvious mistake. This is obviously incorrect
"Now go to strategy 99. There is a 1/99 chance she claims the largest dowry so far. There is also a 1/2 chance that if she does, the 100th women still has a larger dowry."

If the 99th claims the largest dowry so far, the odds of the 100th having an even larger one aren't 1/2, it's 1/100. The odds of one random dowry being bigger than another one are 1/2, but if the 99th claims she has the largest so far (meaning she has at least the second largest overall), the only way for the 100th to beat her is to have the largest one overall, the odds of which are 1/100.

So the new formula would be (1/i)*(1-((100-i)/100))+((i-1/i)*p(i+1). This makes strategy 38 the best one, with a survival chance of 37,1043... % Seems pretty close to the Monte Carlo results.

What if you attempt a strategy of "wait for n 'no's in a row and select the next 'yes'"?

It seems like if you wait until there are, say, 8 consecutive 'no's then the likelihood that the next 'yes' is atleast one of the top few dowries is fairly high. And it makes more sense to me than just "wait for n women and select the next 'yes'" It would seem to increase your odds of selecting the highest dowry if it is in the first 30 or so.

It kind of reminds me of how you know when to stop popping microwave popcorn 🙂

Originally posted by forkedknight
What if you attempt a strategy of "wait for n 'no's in a row and select the next 'yes'"?

It seems like if you wait until there are, say, 8 consecutive 'no's then the likelihood that the next 'yes' is atleast one of the top few dowries is fairly high. And it makes more sense to me than just "wait for n women and select the next 'yes'" It would seem ...[text shortened]...

It kind of reminds me of how you know when to stop popping microwave popcorn 🙂

A very tricky one to calculate, but it might work.

A couple of questions about the original problem.
First is that can we assume that the women always tell the truth?
Second is that the problem posits that we can speak to each woman only once, so it presupposes that the suitor can talk to all 100 women before making his decision. Is this so?
If both of the above are true, wouldn't the solution be to choose the last woman who says marry me?
If the suitor must make a decision at that moment, and can't choose that woman later, than there is no 100% solution in my view.