We introduce the hiring problem, in which a growing company
continuously interviews and decides whether to hire applicants. This
problem is similar in spirit but quite different from the
well-studied secretary problem. It captures aspects of decision
making under uncertainty, and specifically issues that arise in
systems where items are bought or sold at negotiated prices in an
imperfect information market.

We analyze natural strategies of hiring above the current
average, considering both the mean and the median averages; we call
these Lake Wobegon strategies. Like the hiring problem itself,
our strategies are intuitive, simple to describe, and amenable to
mathematically and economically significant modifications. We
demonstrate several intriguing behaviors of the two strategies.
Specifically, we show dramatic differences between hiring above the
mean and above the median. We also show that both strategies are
intrinsically connected to the lognormal distribution, leading to
only very weak concentration results, and the marked importance of
the first few hires on the overall outcome.

Joint work with Andrei Broder (Yahoo! Research), Adam Kirsch
(Harvard), Ravi Kumar (Yahoo! Research), Eli Upfal (Brown),
and Sergei Vassilvitskii (Stanford).