Optimal Expected Rank in a Two-Sided Secretary Problem

DOI10.1287/OPRE.1070.0403MaRDI QIDQ3392125zbMATH OpenOpenAlexFDO

Authors Kimmo Eriksson, Jonas Sjöstrand, Pontus Strimling

Publication date 13 August 2009

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0411212

Mathematics Subject Classification ID

Dynamic programming (90C39) Applications of game theory (91A80) Matching models (91B68)

Abstract: 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.

Recommendations

• Effects of competition in a secretary problem
• A secretary problem with two decision makers
• scientific article; zbMATH DE number 67285
• Bilateral Secretary Problem Recognizing the Maximum or the Second Maximum of a Sequence
• scientific article; zbMATH DE number 3876957

Cited in

(13)

• Asymmetric equilibria in dynamic two-sided matching markets with independent preferences
• Analysis and design of selection committees: a game theoretic secretary problem
• A new method for computing asymptotic results in optimal stopping problems
• A sequential selection game with vetoes
• The job search problem as an employer–candidate game
• Effects of competition in a secretary problem
• Incentivizing hidden types in secretary problem
• NASH EQUILIBRIUM IN TWO-SIDED MATE CHOICE PROBLEM
• Optimal stopping for dynamic recruitment problem with probabilistic loss of candidates
• Equilibria of two-sided matching games with common preferences
• The secretary problem of minimizing the expected rank: a simple suboptimal approach with generalizations
• Evolution of decisions in population games with sequentially searching individuals
• Instability of matchings in decentralized markets with various preference structures

This page was built for publication: Optimal Expected Rank in a Two-Sided Secretary Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3392125)