Analytic Insights into an Adapted Algorithm for the Score-Based Secretary Problem

Abstract

In this paper, we study some basic analytic properties of a sequence of func-tions $\left\{S_{n}^{\mu, \sigma}\right\}$ that is directly derived in an adaptive algorithm originating from the clas-sical score-based secretary problem. More specifically, we show that: 1. the uniqueness of maximum points of the function sequence $\left\{S_{n}^{\mu, \sigma}\right\}$; 2. the maximum point sequence of $\left\{S_{n}^{\mu, \sigma}\right\}$ monotone increases to infinity as n tends to infinity. All of the proofs are elementary but nontrivial.

Keywords

Secretary problem / adaptive algorithm / expected score / uniqueness of maximum points