Re: Twenty Beautiful Women

At 6:19 PM 7/27/96, David Sternlight wrote:
>Here's another:
>
>Twenty beautiful women are to pass before you, one by one (or 20 handsome
>men). You see only one at a time. You cannot speak to them. After seeing
>any one, you must pick her or reject her. If you reject her, you cannot
>change your mind. If you pick her the exercise terminates.
>
>What is the optimal strategy for insuring you get the most beautiful woman
>possible under the circumstances?

Look at the first 1/e of them, or about the first 36.8% of them. In this
case, the first 7 of them. Then pick the first one after this group which
is better than any of the first group.

While there is some chance that one will get to #20 and find that none of
#8-20 were better than #1-7, this strategy is the best compromise between
"committing too early" and "waiting too long."

--Tim May

Boycott "Big Brother Inside" software!
We got computers, we're tapping phone lines, we know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Licensed Ontologist         | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."

At 10:29 AM -0700 7/28/96, Timothy C. May wrote:
>At 6:19 PM 7/27/96, David Sternlight wrote:
>>Here's another:
>>
>>Twenty beautiful women are to pass before you, one by one (or 20 handsome
>>men). You see only one at a time. You cannot speak to them. After seeing
>>any one, you must pick her or reject her. If you reject her, you cannot
>>change your mind. If you pick her the exercise terminates.
>>
>>What is the optimal strategy for insuring you get the most beautiful woman
>>possible under the circumstances?
>
>Look at the first 1/e of them, or about the first 36.8% of them. In this
>case, the first 7 of them. Then pick the first one after this group which
>is better than any of the first group.
>
>While there is some chance that one will get to #20 and find that none of
>#8-20 were better than #1-7, this strategy is the best compromise between
>"committing too early" and "waiting too long."

Correct.

David

David Sternlight wrote:
> At 10:29 AM -0700 7/28/96, Timothy C. May wrote:
> >Look at the first 1/e of them, or about the first 36.8% of them. In this
> >case, the first 7 of them. Then pick the first one after this group which
> >is better than any of the first group.
> >
> >While there is some chance that one will get to #20 and find that none of
> >#8-20 were better than #1-7, this strategy is the best compromise between
> >"committing too early" and "waiting too long."
> 
> Correct.
> 

Prove it.

	- Igor.

Timothy C. May wrote:
> >Twenty beautiful women are to pass before you, one by one (or 20 handsome
> >men). You see only one at a time. You cannot speak to them. After seeing
> >any one, you must pick her or reject her. If you reject her, you cannot
> >change your mind. If you pick her the exercise terminates.
> >
> >What is the optimal strategy for insuring you get the most beautiful woman
> >possible under the circumstances?
> 
> Look at the first 1/e of them, or about the first 36.8% of them. In this
> case, the first 7 of them. Then pick the first one after this group which
> is better than any of the first group.
> 
> While there is some chance that one will get to #20 and find that none of
> #8-20 were better than #1-7, this strategy is the best compromise between
> "committing too early" and "waiting too long."

This "some chance" is 1/e (for a very large number of women), obviously.

There is 1/e chance that the best woman will be in the first 1/e 
fraction of women.

Also, I would appreciate if someone specified what exactly the goal 
function is.

	- Igor.

Igor Chudov @ home wrote:

> Also, I would appreciate if someone specified what exactly the goal
> function is.

Are you wunna them "funny boys"?




[ note clear cp relevance viz. a particular thread I've been nuking lately ]

______c_____________________________________________________________________
Mike M Nally * Tiv^H^H^H IBM * Austin TX    * For the time being,
       m5@tivoli.com * m101@io.com          *    
      <URL:http://www.io.com/~m101>         *    three heads and eight arms.

ichudov@algebra.com (Igor Chudov @ home) writes:

 > Also, I would appreciate if someone specified what exactly
 > the goal function is.

Me too.

This is an interesting problem, vaguely reminescent of the pie
judging contests commonly used as examples of non-parametric
statistics.  Given two pies, (or two women), a judge can
subjectively order them by tastiness, (or beauty), but there is
no concept of an continuous metric in which the ratings of
particular items are embedded.

This makes it somewhat difficult (at least for me) to determine
the function being maximized in this problem.  Do we mean a
strategy which gives the highest probability of choosing the most
beautiful woman over all possible orderings? If not, then we need
some way of saying whether we value N dates with the woman having
rank I over M dates with the woman having rank J, which requires
information the problem does not give us.  The first case is
ambiguous, since there are numerous strategies which differ only
in the probability of selecting items having other than the
highest rank, and the second implies the existence of some sort
of metric.

Indeed, what a person would regard as an strategy maximizing the
chances of choosing the "best" item overall depends very much
upon the choice of such a metric.  If we have 20 women whose
attractiveness is evenly spaced, one might proceed quite
differently than if the top 18 were attractive and almost
indistinguishable, and the other two had a contagious and fatal
disease.

If we make the leap of assigning the integers 1 to 20 to the
individuals, and seek a strategy which maximizes the mean
attractiveness over all possible orderings, then the problem can
be solved by backtracking from the last choice made.  This
results in a variable threshold at each stage in which we select
the current candidate if its rank in the items seen so far
exceeds the threshold, and proceed if this is not the case.

If we want a single partition point at which we choose the first
item better than any item before the partition point, then 1/e
seems believable, although I haven't personally worked out the
math.

--
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $