## Abstract

The well-known secretary problem in sequential analysis and optimal stopping theory asks one to maximize the probability of finding the optimal candidate in a sequentially examined list under the constraint that accept/reject decisions are made in real-time. The problem is related to practical questions arising in online search, data streaming, daily purchase modeling and multi-arm bandit mechanisms. An extension is the postdoc problem, for which one aims to identify the second-best candidate with highest possible probability of success. We solve the postdoc problem for the nontraditional setting where the candidates are not presented uniformly at random but rather according to permutations drawn from the Mallows distribution. The optimal stopping criteria depend on the choice of the Mallows model parameter \theta: For \theta > 1 , we reject the first k^{\prime}(\theta) candidates and then accept the next left-to-right second-best candidate (second-best ranked when comparing with all appeared candidates). This coincides with the optimal strategy for the classical postdoc problem, where the rankings being drawn uniformly at random (\boldsymbol{i}.\boldsymbol{e}. \theta=1). For 0 < \theta\leqslant 1/2, we reject the first k^{\prime \prime}(\theta) candidates and then accept the next left-to-right best candidate; if no selection is made before the last candidate, then the last candidate is accepted. For 1/2 < \theta < 1 , we reject the first k_{1}(\theta) candidates and then accept the next left-to-right maximum, or reject the first k_{2}(\theta)\geqslant k_{1}(\theta) candidates and then accept the next left-to-right second-maximum, whichever comes first.

Original language | English (US) |
---|---|

Title of host publication | 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 3214-3219 |

Number of pages | 6 |

ISBN (Electronic) | 9781538682098 |

DOIs | |

State | Published - Jul 12 2021 |

Event | 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Virtual, Melbourne, Australia Duration: Jul 12 2021 → Jul 20 2021 |

### Publication series

Name | IEEE International Symposium on Information Theory - Proceedings |
---|---|

Volume | 2021-July |

ISSN (Print) | 2157-8095 |

### Conference

Conference | 2021 IEEE International Symposium on Information Theory, ISIT 2021 |
---|---|

Country/Territory | Australia |

City | Virtual, Melbourne |

Period | 7/12/21 → 7/20/21 |

## Keywords

- Mallows model
- postdoc problem
- secretary problem

## ASJC Scopus subject areas

- Theoretical Computer Science
- Information Systems
- Modeling and Simulation
- Applied Mathematics