Harvard Theory of Computation Seminar

The Hiring Problem and Lake Wobegon Strategies

Adam Kirsch, Harvard University

Place and Time: Monday, January 22, Maxwell Dworkin 319 Refreshments at 2:30pm, talk at 2:45pm

ABSTRACT

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), Ravi Kumar (Yahoo! Research), Michael Mitzenmacher (Harvard), Eli Upfal (Brown), and Sergei Vassilvitskii (Stanford).