Secretary Problems: Weights and Discounts

The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and this decision is irrevocable. Constant-competitive algorithms are known for the classical secretary problems and several variants. We study the following two extensions of the secretary problem: In the discounted secretary problem, there is a time-dependent “discount” factor $d(t)$, and the benefit derived from selecting an element/secretary e at time t is $d(t)v(e)$. For this problem with arbitrary (not necessarily decreasing) functions $d(t)$, we show a constant-competitive algorithm when the expected optimum is known in advance. With no prior knowledge, we exhibit a lower bound and give a nearly matching $O(log n)$-competitive algorithm. In the weighted secretary problem, up to K secretaries can be selected; when a secretary is selected (s)he must be irrevocably assigned to one of K positions, with position k having weight $w(k)$, and assigning object/secretary e to position k has benefit $w(k)v(e)$. The goal is to select secretaries and assign them to positions to maximize the sum of $w(k)v(e_k)$ where $e_k$ is the secretary assigned to position k. We give constant-competitive algorithms for this problem. Most of these results can also be extended to the matroid secretary case for a large family of matroids with a constant-factor loss, and an O(log rank) loss for general matroids. These results are based on a reduction from various matroids to partition matroids which present a unified approach to many of the upper bounds of Babaioff et al. These problems have connections to online mechanism design. All our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problems.