This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Eriksson, K. Articles by Strimling, P. Search for Related Content

Optimal Expected Rank in a Two-Sided Secretary Problem

Department of Mathematics and Physics, Mälardalen University, SE-721 23 Västerås, Sweden
Department of Mathematics and Physics, Mälardalen University, SE-721 23 Västerås, Sweden
Department of Mathematics and Physics, Mälardalen University, SE-721 23 Västerås, Sweden
kimmo.eriksson{at}mdh.se
jonas.sjostrand{at}mdh.se
pontus.strimling{at}mdh.se

In a two-sided version of the famous secretary problem, employers search for a secretary at the same time as secretaries search for an employer. Nobody accepts being put on hold, and nobody is willing to take part in more than N interviews. Preferences are independent, and agents seek to optimize the expected rank of the partner they obtain among the N potential partners. We find that in any subgame perfect equilibrium, the expected rank grows as the square root of N (whereas it tends to a constant in the original secretary problem). We also compute how much agents can gain by cooperation.

Subject classifications: games/group decisions; strategic secretary problem; dynamic programming/optimal control; optimal stopping.
History: Received June 2005; revision received June 2006; accepted June 2006.