José Correa, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk, Alexandros Tsigonias-Dimitriadis.
SODA 2021:
Proceedings of the Thirty-second Annual ACM-SIAM Symposium on Discrete
Algorithms, Virtual, January 10-13.
doi: 10.1137/1.9781611976465.122.
In the secretary problem we are faced with an online sequence of elements with values. Upon seeing an element we have to make an irrevocable take-it-or-leave-it decision. The goal is to maximize the probability of picking the element of maximum value. The most classic version of the problem is that in which the elements arrive in random order and their values are arbitrary. However, by varying the available information, new interesting problems arise. Also the case in which the arrival order is adversarial instead of random leads to interesting variants that have been considered in the literature.
In this paper we study both the random order and adversarial order secretary problems with an additional twist. The values are arbitrary, but before starting the online sequence we sample each element with a fixed probability p. The sampled elements become our information or history set and the game is played over the remaining elements. We call these problems the random order secretary problem with p-sampling (ROSp for short) and the adversarial order secretary problem with p-sampling (AOSp for short). Our main result is to obtain best possible algorithms for both problems and all values of p. As p grows to 1 the obtained guarantees converge to the optimal guarantees in the full information case. In the adversarial order setting, the best possible algorithm turns out to be a simple fixed threshold algorithm in which the optimal threshold is a function of p only. In the random order setting we prove that the best possible algorithm is characterized by a fixed sequence of time thresholds, dictating at which point in time we should start accepting a value that is both a maximum of the online sequence and has a given ranking within the sampled elements.
I presented the paper at SODA 2021 (online event). I also presented the paper at the ENS Paris Talgo seminar in February 2021, at the ENS Lyon MC2 seminar in March 2021, at the Paris game theory seminar in May 2021, and at the AGaPe workshop in December 2022.
José presented the paper at Columbia University DRO-IEOR Seminar. Tim presented at OMS Oberseminar at RWTH Aachen, at Kolloquium über Informatik at Universität zu Köln, and at the Eindhoven SPOR seminar at Eindhoven University of Technology. Alexandros prensented the paper at the Adone seminar of TUM.