The Sultan's daughters

Today when I was supposed to be working on my thesis, I got sidetracked thinking about the Sultan and his daughters.  I took a look around the Net and didn't immediately find anything about this in the literature, so there's some possibility it may even be an original research problem.  I'm posting it here because I think it's interesting and to see if any readers have ideas on it.  Let me know if you're aware of anything published about it or if you think there isn't any and want to be in on trying to actually do some real research.  Posting in "software" because I don't really have a "math" category...  but maybe I should.  If it appears to be an open problem, I might even post a bounty on it.

Here's the deal.  The Sultan of a small Eastern country has one hundred daughters who need husbands.  (Substitute sons if you prefer, or precious works of art that need to be put in galleries or something of the kind if you object to using human beings as examples in this type of math problem at all.) He has decided to award his daughters' hands in marriage to readers of this Web site, including you.  The deal is that you will be introduced to the hundred daughters one at a time in random order (the Sultan has chosen a permutation uniformly at random from the 100!  possible permutations) and for each one you must give a permanently binding "yes" or "no" answer.  If you say "yes" to a daughter you marry her without reference to the others; if you say "no," you never get another chance with her.  You want to marry the most beautiful daughter.  You have no a priori knowledge - and this is important, so listen carefully - no a priori knowledge at all of the distribution of beauty over Oriental princesses, so when you meet any one daughter, the only meaningful judgement you can make is how she ranks relative to the others you've already rejected; you can't decide anything about how the future daughters rank relative to her, except what you may be able to guess from the fact that the permutation was chosen uniformly at random.  So...  what should you do?

The best case, and probably the one I'd write into the movie script:  you are already in love with one of the daughters.  Then it's easy.  You just say "no" to all of them until you meet your true love, say "yes" to her, and live happily ever after.  However, that violates the assumption that you haven't met the daughters before and have no a priori knowledge of them.  Closely related, and also technically a violation of the rules, is the incurable romantic's view that one of the daughters is destined for you and even though you've never met her before, you will recognize her with probability 1.0 at first sight.  The forbidden assumption in that one is that you magically get for free all the results of comparing her to future daughters; you may know that she's better than all her sisters met up to this point, but unless she's the last one (which only happens with probability 0.01) you can't assume you know she's better than the future daughters you haven't met.

The case that is usually used as an example in computer science courses actually has another issue involved, in that it's not beauty you're comparing the daughters on.  The Sultan already has a daughter picked out for you, and we'll assume that you'd be pleased with her, but he wants you to prove your worthiness by passing a test.  Each daughter comes with a dowry (a sum of money that the Sultan will give you if you marry her), all the dowries are distinct positive real numbers, as with beauty you have no a priori knowledge of the distribution of dowries, and the kicker is that the Sultan will only allow you to marry his daughter at all if you choose the one daughter he has picked out, who has the biggest dowry.  You're told each daughter's dowry when you meet the daughter and you have to say "yes" or "no" to her; you don't get to find out the dowry of the next daughter until you've made your binding decision about the current one.  (The Sultan's idea is that you should prove you're a shrewd enough businessman to be able to support his daughter after the dowry money runs out.) So you really do have to pick the most expensive daughter or you don't get a bride at all; second-best will not do.  You need the strategy that maximizes the probability of choosing the most expensive daughter.  This is called the Sultan's Dowry problem and it's the usual form of the problem.

Of course, the smart thing in such a case is to pay attention to whether you actually like the daughters, and if you ever meet one you like who is also the most expensive one seen so far, you say yes to her immediately and hope you guessed right.  If you're a proper romantic hero you might even say "yes" to a daughter who does NOT have the greatest dowry seen to date, who couldn't possibly be the "right" choice - thereby proving that you're willing to put love above the silly rules of the game, and either impressing the Sultan with your wisdom and daring, or else perhaps convincing the daughter to elope with you.  That too would be a plot for the movie script.  But that's beyond the scope of the question; we're assuming your goal is as stated, to maximize the probability of saying "yes" to the daughter with the greatest dowry.

In that case it turns out that the winning strategy is simple:  you say "no" to the first 37 daughters, but make a note of the greatest dowry among them.  Then you say "yes" to the first daughter whose dowry exceeds the greatest in the first 37.  If you follow this policy, you have about a 37% chance of picking the most expensive daughter, and that's the best possible chance.  There are a couple of ways it can go wrong:  the most expensive daughter might be one of the first 37, in which case you'll say no to her, never see another as good, and end up single; or the best one in the first 37 might be the third or worse overall, and then it could happen that you see someone better than her but not best overall (such as the second-best) before you see the best overall, and you say yes to that one and the Sultan sends you away unmarried because you guessed wrong.  You can do the math (it's not terribly hard) and prove that this strategy really does maximize the chance of saying "yes" to the daughter with the greatest dowry.

In case you're wondering, the reason it's 37 is that that is 100*exp(-1).

But are those two "you lose" results really equivalent?  In the classic Sultan's Dowry problem, they are; the rules of the game are set up to demand that you must choose the one most expensive dowry or else lose, and all "lose" results are the same.  That's not very realistic, assuming you think this story has any realism to it at all in the first place.  Suppose the Sultan doesn't make that rule; he just wants to get these daughters off his hands, and you just want a good bride; you can decide for yourself what "good" means.  In that case, saying "yes" to the second-most-desirable daughter is probably much better than saying "no" to them all and ending up single.  It makes sense to follow a strategy that would accept a greater risk of getting the second-best bride in exchange for a reduced risk of getting no bride.  In fact, the Sultan's daughters are all pretty sweet and you'd certainly be happy with any of the top ten.  With that in mind, can you choose a better strategy?

First, let's think about what a strategy actually is.  At any given moment, you're faced with one daughter and you have to decide yes or no to her.  You have access to the entire history of rankings of previous daughters, but it doesn't really matter what order they appeared in because all permutations are equally likely.  Let's say you've rejected five daughters already, and the current daughter is better than any of the previous five.  It could be that the previous five daughters appeared in strictly increasing order of preference, or in strictly decreasing order of preference, or in any of the 118 (=5!-2) other orders, but that doesn't matter because you've already rejected them permanently, and the remaining information and choices available to you are now independent of that.  All that's important is that you've rejected five daughters, the current daughter is ranked number 1 among the ones you've looked at, and there are 94 remaining if you reject her.  These notions can be formalized; what it comes down to is that a strategy is a function that tells you what to do when you have already rejected i number of daughters, the current daughter has rank r, and there are n-i-1 daughters remaining, for all values of i, r, and n.  Any two strategies that have the same probability of accepting given the same values of those variables, are equivalent.  So a strategy can be thought of as a function that takes those three inputs and gives you a number from 0 to 1 which represents the probability that you should accept.

How good is a strategy?  You could assign some kind of value to the ranking of daughters and to the no-marriage outcome.  Normally that would be called a utility function.  In the classic version of the problem the utility function is equal to 1 if you marry the most expensive daughter and 0 in all other cases.  The expected value of the utility is then exactly the probability that you marry the most expensive daughter, and that's what you're trying to maximize.  It's easy to translate other, more realistic, goals into utility functions too.  For instance, if you want to maximise the probability of marrying one of the top ten daughters and don't care which, you assign utility 1 to the top ten daughters and 0 to all the other options (including remaining single).  It's also possible to imagine more complicated utility functions that would assign different utility levels to different daughters beyond a simple one or zero.  It's possible to imagine an inverted situation where there are one or two daughters you want to absolutely avoid (having no bride at all would be preferable) but any of the others would be fine; in that case you assign some positive utility to the no-marriage option, or maybe always leave the no-marriage option at zero but give some negative utility to the bottom few daughters.  It seems reasonable that almost all the goals you might want could be expressed as trying to maximize the expected value of some function of the ranking of the daughter you marry (or the no-marriage outcome).  Moreover, that function ought to increase as the daughter's preference rank improves - if you didn't prefer her over her lower-ranked sister, then she would be the lower-ranked sister.

So the situation is a triple of "how many daughters already seen," "rank of the current daughter relative to those already seen," and "how many remaining." That last could be eliminated if you assume there always are 100 daughters, but I'm thinking about the general case here.  The strategy is a function that tells you, based on the situation, with what probability you should accept the current daughter.  I suspect that the best strategies will always end up giving results of accepting with probability 0 or 1.  With a given strategy, the outcome (which daughter you marry, or whether you remain single) is a random variable; the utility is a function of that random variable; and you want a strategy that maximizes the expectation of the utility.  The utility is monotonically increasing with higher-ranking daughters; if you'd have a certain level of satisfaction with the third-best daughter then you must have at least that much satisfaction with the second-best or very-best daughter.

Suppose we can guarantee that for all nonnegative monotonically increasing utility functions, strategy A gives you a better expected utility than strategy B. In that case, strategy A would seem to be a better choice.  No matter whether you're holding out for the best bride, or just want one in the top ten, or even just any bride who is not in the bottom ten, you're better off with strategy A. In such a situation let's say that strategy A dominates strategy B. That is not a total order on strategies - there will often be pairs of A and B where neither one dominates the other.  But if dominance exists, it's desirable.  If you have a strategy B that is dominated by some strategy A, then you definitely don't want to use strategy B. Whatever the best strategy is will depend on your utility function, but it will always be one that is not dominated by any other strategy.  (See PimpMaster C explains the efficiency frontier for more about this.)

I think that optimal strategies will always be monotonic in the rank of the current daughter.  That is, if your optimal strategy would accept a daughter whose rank is r among the i+1 daughters you have seen up to this point (i already rejected, plus her) with probability p, then it must also accept any daughter of rank less than r (that is, better than her) with probability at least p.  The argument goes like this:  suppose you have a strategy B that does not have that property (for some i, r, p).  Construct a strategy A that does have that monotonicity property by raising all the acceptance probabilities for better-ranked daughters at this time to at least p; strategies A and B are otherwise identical.  Well, because of the way the Sultan chose the permutation of daughters, the rankings of future daughters (should you reject) are independent of the rankings you've seen up to this point.  So the expected value of the two strategies, should you reject this daughter, must be the same.  And your optimal strategy has already decided that the current daughter is worth accepting with probability p - so a p chance of marrying her is better than the unknown result of rejecting her.  In that case, all her higher-ranked sisters must be at least as good by definition, so you'd better be also willing to marry any of them with probability at least p.  Therefore optimal strategies are monotonic in current-daughter rank.

I'm less sure of this, but I think a similar argument applies to time (which is the same as number of previously-rejected daughters).  If you would accept a daughter ranked #1 among ten, then you'd better also accept one ranked #1 among twenty.  All you win by rejecting is the potential for meeting someone better in the future, and that potential can't possibly increase when you decrease the number of future daughters.  (Given that the Sultan chose a random permutation of daughters.)

So already we've put a whole bunch of restrictions on what the strategy function looks like.  Can it be restricted further?  I think it can probably also be restricted to be deterministic, but I'm not sure of that.  All that stuff is based on dominance - describing the properties that an optimal function has to have regardless of what monotonic nonnegative utility function you use.  The really interesting part, which I'm going to leave open, is how the strategy depends on the utility function.  For instance, if you're going with the "I want one in the top ten" utility function, it seems like you should reject until you have a large enough sample that you're pretty sure you've seen one of the top eleven daughters.  I don't know how many that is or exactly what "pretty sure" ought to mean in this case, but it's certainly possible to do calculations to balance out all the issues and get an answer to that.  I think it'll mean rejecting only about ten.  Then you accept the next one who's above roughly the 90th percentile of the ones you've seen, and you have a very good chance of getting one in the top ten.  (Much better than 37%.)

What if the Sultan didn't choose his permutation of daughters uniformly at random?  In particular, what if the Grand Vizier, who is evil and hates you, has tampered with the random selection to arrange the daughters into a permutation designed to screw up your strategy?

Let us assume that the Grand Vizier is as evil as possible - he's an online adaptive adversary.  He gets to know your complete strategy (including probabilities of what you'll do in any situation, but NOT actually influence your coin flips) and your complete utility function (including your ranking of the daughters' desirability), and he even gets to reorder the daughters after every round, in order to make it go as badly for you as possible.

If you don't know the Grand Vizier is on your case and you're following one of these optimal (for uniform permutations) strategies, it seems like what the Grand Vizier ought to do to make trouble for you is arrange the daughters in order of decreasing desirability.  Any strategy of the double-monotonic "take a sample and then say yes to the first one who's good enough relative to the sample" form seems to hit its worst case.  You won't get the best daughter unless you were prepared to accept the first one you saw, with no information, anyway.  (And in that case you could get the same effect from the more robust randomized strategy described below.) You probably won't get the second- or third-best bride either, and in fact, they just keep getting worse and worse and you probably end up single or stuck with the worst daughter of all, the one you meet last, if you consider her better than remaining single.

Note that the Grand Vizier doesn't seem to gain anything for being online adaptive, nor for being randomized.  He could simply choose one worst permutation of daughters in advance based on your strategy instead of changing the permutation on the fly, because after each round you're either married, or there's no useful information from previous rounds except the number of daughters you've rejected.

If you know the Grand Vizier is tampering with the order of daughters, there's a very simple way you can limit the damage - make your choices in such a way that the distribution of outcomes is independent of the order of daughters.  Accept the first daughter with probability 1/100.  Accept the second with probability 1/99 if you're still single.  Accept the third with probability 1/98 if you're still single; and so on.  All these choices are independent of ranking of the current daughter.  You end up with one bride uniformly at random no matter what order the Grand Vizier chooses.  That's a 1/100 chance of getting the best, a 1/100 chance of getting the worst, a 1/2 chance of getting one above the median, and so on.  The Grand Vizier shall have no claim over your mind nor cause you chilblains.

Is it possible to do better in the clutches of the Grand Vizier, given that you and he both know about the other?  I think not, but don't have a proof off the top of my head.  It sounds like one of those Nash equilibrium things.  It's possible to come up with some very complicated strategic stuff that I think will all wash out in the payoff matrix.  I'm also not sure what happens to this strategy if some of the daughters are worse than remaining single.  It may be as simple as you have to scale the probabilities uniformly so that even on the last daughter you still have a chance of saying "no"; or it may be that you just have to marry a random daughter and accept the risk of getting one of the bad ones, up to the point where the expected value of playing the game at all becomes worse than the expected value of just telling them all to go to Hell.