Secretaries
Eric and Rachael Farmer
solution in the FAQ:
A sultan has granted a commoner a chance to marry one of his hundred
daughters. The commoner will be presented the daughters one at a time.
When a daughter is presented, the commoner will be told the daughter's
dowry. The commoner has only one chance to accept or reject each daughter;
he cannot return to a previously rejected daughter. The sultan's catch is
that the commoner may only marry the daughter with the highest dowry. What
is the commoner's best strategy assuming he knows nothing about the
distribution of dowries?
1. Almost every solution to this problem that I've seen states without
proof the not-so-obvious claim that the best strategy consists of rejecting
k daughters outright, then accepting the next daughter that is better than
all those seen so far. Given this, the solution is relatively
straightforward, and has a very nice form.
Puzzle: prove this claim.
2. The sultan, in my opinion, is an eccentric old bastard, allowing the
commoner to marry only the daughter with the highest dowry. The implication
of this catch is that the best strategy should maximize the probability of
accepting the best daughter. This is a rather unrealistic goal, especially
when this problem is expressed as hiring one of a sequence of applicants for
a secretarial position.
Puzzle: assuming the commoner may marry whichever daughter he accepts, what
is the commoner's best strategy for maximizing the expected rank of his
chosen bride?
Eric Farmer
Eric and Rachael Farmer
Call this either some preliminary results, or a hint:
SPOILER?...
Conjecture for problem 2: If m of n daughters remain to be presented, then
accept the next daughter only if she is at least the k-th best so far, where
k is (approximately) n/m.
I have solved the problem exactly for any number n of daughters, and the
general strategy appears to be of the above form, but I have yet to find a
relatively simple way of describing it *.
* Consider, for example, the solution to the original problem (this is in
the FAQ): reject m daughters, then accept the next daughter better than all
others seen so far, where m is the least such that:
m/n > m/n (1/(m+1) + ... + 1/(n-1))
I'm having difficulty reproducing this "relatively simple" inequality. What
do the left and right sides represent? Because, for example, the right side
is NOT the probability of accepting the best daughter by rejecting the m-th
one (which is what the FAQ solution seems to claim). However,
m/n (1/m + 1/(m+1) + ... + 1/(n-1))
IS that probability- BUT only when m is at least the critical value for the
problem!
Eric Farmer
Nick Wedd
>daughters. The commoner will be presented the daughters one at a time.
>When a daughter is presented, the commoner will be told the daughter's
>dowry. The commoner has only one chance to accept or reject each daughter;
>he cannot return to a previously rejected daughter. The sultan's catch is
>that the commoner may only marry the daughter with the highest dowry. What
>is the commoner's best strategy assuming he knows nothing about the
>distribution of dowries?
>
>1. Almost every solution to this problem that I've seen states without
>proof the not-so-obvious claim that the best strategy consists of rejecting
>k daughters outright, then accepting the next daughter that is better than
>all those seen so far. Given this, the solution is relatively
>straightforward, and has a very nice form.
>
>Puzzle: prove this claim.
Only the ordering of the dowries is relevant, not their absolute values.
Given this, and assuming as you must that the daughters have been
randomly shuffled ( pause for fantasy about the eunuchs putting them in
two piles and riffle-shuffling them - would the plumper ones end up at
the bottom of the stack? ) the only sensible strategies must be as
described above.
>2. The sultan, in my opinion, is an eccentric old bastard, allowing the
>commoner to marry only the daughter with the highest dowry. The implication
>of this catch is that the best strategy should maximize the probability of
>accepting the best daughter. This is a rather unrealistic goal, especially
>when this problem is expressed as hiring one of a sequence of applicants for
>a secretarial position.
>
>Puzzle: assuming the commoner may marry whichever daughter he accepts, what
>is the commoner's best strategy for maximizing the expected rank of his
>chosen bride?
I think we now have insufficient information.
Should we assume that the distribution of dowries is rectangular?
Should we look at the first k dowries, hypothesise about the possible
distributions which the dowries might be selected from, consistent with
the sultan's knowledge of mathematics, and work out what to do next?
Can we be certain that there won't be some with negative dowries?
Nick
--
Nick Wedd ni...@maproom.co.uk
Eric and Rachael Farmer
>>A sultan has granted a commoner a chance to marry one of his hundred
>>daughters. The commoner will be presented the daughters one at a time.
>>When a daughter is presented, the commoner will be told the daughter's
>>dowry. The commoner has only one chance to accept or reject each
daughter;
>>he cannot return to a previously rejected daughter. The sultan's catch is
>>that the commoner may only marry the daughter with the highest dowry.
What
>>is the commoner's best strategy assuming he knows nothing about the
>>distribution of dowries?
>>
>>1. Almost every solution to this problem that I've seen states without
>>proof the not-so-obvious claim that the best strategy consists of
rejecting
>>k daughters outright, then accepting the next daughter that is better than
>>all those seen so far. Given this, the solution is relatively
>>straightforward, and has a very nice form.
>>
>>Puzzle: prove this claim.
>
>Only the ordering of the dowries is relevant, not their absolute values.
>Given this, and assuming as you must that the daughters have been
>randomly shuffled ( pause for fantasy about the eunuchs putting them in
>two piles and riffle-shuffling them - would the plumper ones end up at
>the bottom of the stack? ) the only sensible strategies must be as
>described above.
I guess this wasn't as immediately clear to me, especially since the optimal
strategy is NOT of that form in the following:
>>2. The sultan, in my opinion, is an eccentric old bastard, allowing the
>>commoner to marry only the daughter with the highest dowry. The
implication
>>of this catch is that the best strategy should maximize the probability of
>>accepting the best daughter. This is a rather unrealistic goal,
especially
>>when this problem is expressed as hiring one of a sequence of applicants
for
>>a secretarial position.
>>
>>Puzzle: assuming the commoner may marry whichever daughter he accepts,
what
>>is the commoner's best strategy for maximizing the expected rank of his
>>chosen bride?
>
>I think we now have insufficient information.
>
>Should we assume that the distribution of dowries is rectangular?
>Should we look at the first k dowries, hypothesise about the possible
>distributions which the dowries might be selected from, consistent with
>the sultan's knowledge of mathematics, and work out what to do next?
>Can we be certain that there won't be some with negative dowries?
Actually, the actual values of the dowries in (1) ARE relevant (see the
FAQ), and in this case, for at least some numbers of daughters (2 in
particular; again, see the FAQ) the "common" solution is incorrect. The
problem is still interesting if we assume knowledge only of the relative
order of preference of the daughters seen so far (in which case that
solution is correct), and that is what I've assumed in problem (2) as well.
Eric Farmer