Single-choice secretary problems with ordinal advice.

Abstract: We examine variations of the classical secretary problem in a new setting, where the decision-maker (DM) can request one (or more) bits of ordinal information from agents before they arrive. Specifically, each agent has private information (their weight) that is publicly revealed upon arrival. As usual, the DM must irrevocably decide whether to select the agent or not after this step. Additionally, at any given time, the DM can privately ask yes-or-no questions to agents who have not yet arrived, and the agents can only answer ordinal questions based on comparing their private information with the information publicly available up to that point. We refer to this additional information as ordinal advice. For example, the DM may ask if the agent’s hidden value is higher than that of all agents who have arrived so far, but he cannot ask if that value is the largest of the entire list as the agent does not have information about the other agents that haven’t arrived.

The goal is to select the agent with the highest weight from the list. We consider different ways in which the agents can arrive, such as randomly, in an adversarial order, or with a random sample of agents that are revealed beforehand. In the latter case, the DM is the one who chooses the number of applicants included in the sample, and the rest of the input is presented in an order chosen by an adversary either before or after the realization of the sample set. We explore the impact of varying the amount of ordinal advice allowed by considering the cases where the DM can ask for zero, one, or multiple rounds of ordinal advice. We present algorithms that achieve optimal competitive ratios for almost all the settings considered. Notably, we observe that ordinal advice improves the performance in every scenario, with the exception of the adversarial-order setting.

Posted on May 15, 2023 in ACGO, Seminars