For further information
or to submit your
on Social Computing
ACM TSC seeks to publish
work that covers the
full spectrum of social
systems, and design
TSC welcomes research
employing a wide range
of methods to advance
the tools, techniques,
practice of social
research that designs,
implements or studies
systems that mediate
social interactions among
users, or that develops
theory or techniques
for application in those
to select one. At each stage, you must
choose the current object or you can
pass on it, but either way, your decision
is irrevocable. Suppose further that:
˲ The only pertinent information
you get about the candidates is ordinal.
That is, you can judge how the new candidate compares to the earlier ones,
but you cannot assign a meaningful
˲ Your goal is to maximize the probability of getting the best of the N candidates; you are indifferent between all
In that case, the preceding algorithm—pass on the first N/e, then
choose the next one that is better than all
those—is provably optimal. Following
that algorithm, the probability is about
1/e that you will get the best partner.
The problem and its solution were
first published in Martin Gardner’s
“Mathematical Games” column. 3 Chapter 1 of Christian and Griffiths1 and its
15 pages of notes contain a thorough
discussion of the problem’s history,
variants, and applications; see also the
Wikipedia entry, Secretary Problem. 8
Given the extreme restrictions, it is
easy to see that the optimal rule to follow must have the form, “Pass on the
first f (N), then choose the next one that
is better” for some function f (N). Obviously, a candidate that is not better than
all those seen so far cannot be chosen,
since it cannot be the best. Moreover, all
the information that you have in choosing is the sequence of ordinals; and it is
easy to see that the order in which the
ones you have passed on carries no useful information.
bachelorettes. He is happy to date them
all, so N = 100. Therefore, following the
algorithm, his plan is first to date 37 of
them, and then to marry the next one
who is better than any of those 37.
However, the course of following algorithms never did run smooth. Date
17 is Chloe, who is amazing. Strephon
is completely smitten. However, a theorem is a theorem, and Strephon can
easily calculate that the probability is
0.83 that someone he has not met yet is
even better than Chloe. Goodbye Chloe.
The next 34 dates go by with no magic.
Date 52 is Phoebe. Phoebe is even more
amazing than Chloe. Patting himself
on the back for his wisdom and patience in passing up Chloe, Strephon
proposes to Phoebe. For Phoebe,
Strephon is date #40 out of 75, so she
is in her second stagea and she really
likes him. Sadly, though, she liked Colin, her #15, even better, so no dice.
Forty-five more women come and
go. Date 98 is Daphne. Daphne is as
amazing as Chloe except that she listens to the controversial avant-garde
composer Karlheinz Stockhausen, but
Strephon can live with that. The probability that one of the remaining two
women is better than Daphne is only
about 0.06. However, the goal of the
algorithm is to marry the best partner,
and Daphne is definitely not the best
partner, since she is inferior to Chloe.
Strephon knows better than to contravene an algorithm endorsed by a professor at Berkeley and published in the
Washington Post. Goodbye Daphne.
What the algorithm prescribes in
the case where Daphne is better than
Chloe but worse than Phoebe is not
clearly specified; it depends on whether
the goal is to marry the best partner of
all those on the list, or to marry the best
partner who would have accepted you.
You might suppose that Strephon
could try calling Chloe and begging
for forgiveness; but the theorem that
Strephon is relying on assumes that is
impossible. By assumption, Chloe has
already married someone else.
Enough of the melodrama; what is
the math? The theorem is as follows:
Suppose you will be presented with a sequence of options, from which you are
a There is a dating service in Arcadia that matches
first-stagers with first-stagers and second-stagers with second-stagers.
of the theorem are
almost never even
satisfied in real-world
in regard to dating.