2004/11/09 by Kimmo Eriksson, Eriksson, Kimmo, Jonas Sjöstrand +4
Computer Science · Mathematics · #91A15 #91B08 #91B40 #Combinatorics (math.CO) #Distributed Control Multi-Agent Systems #FOS: Mathematics #Mobile Agent-Based Network Management #Optimization and Search Problems #math.CO #msc:91A15 #msc:91B08 #msc:91B40
paper · pdf · doi:10.48550/arxiv.math/0411212
16 pages
arxiv created 2004/11/09 · openalex publication_date 2004/11/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the "secretary problem", well-known in the theory of optimal stopping, an employer is about to interview a maximum of N secretaries about which she has no prior information. Chow et al. proved that with an optimal strategy the expected rank of the chosen secretary tends to approximately 3.87. We study a two-sided game-theoretic version of this optimal stopping problem, where men search for a woman to marry at the same time as women search for a man to marry. We find that in the unique subgame perfect equilibrium, the expected rank grows as the square root of N and that, surprisingly, the leading coefficient is exactly 1. We also discuss some possible variations.