Submodular secretary problem achieves optimal competitive ratios under constraints

The Submodular Secretary Problem: Tight $1-1/e$ for Monotone Objectives, and Strictly Between $1/e$ and $1/2$ in General

Data Structures and AlgorithmsComputer Science and Game Theory

Summary

The submodular secretary problem involves choosing items one by one that arrive in random order, trying to maximize a value that depends on the selected set. The authors figure out the best possible success rate for picking items when the value function is monotone and when it is general. For monotone cases, they prove the best success rate approaches about 63% as the number of items grows and give a simpler way to achieve it. For general cases, they show the best achievable success rate is between about 37% and 50%, improving prior results. They also introduce a method where the chance to pick an item depends on how often it would have passed earlier checks.

What this means in practice

  • For online market designers: Design online mechanisms for sequential offers where selections must be made immediately without recall, improving guaranteed value maximization under capacity constraints.
  • For resource allocation engineers: Develop online resource allocation algorithms that accept requests sequentially under size limits, optimizing submodular objectives with proven performance bounds.

Authors

Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Danny Mittal

Abstract

In the submodular secretary problem with a cardinality constraint, $n$ elements arrive in uniformly random order, and an algorithm must irrevocably accept or reject each one on arrival so as to maximize a nonnegative submodular function over sets of at most $k$ elements. For monotone objectives we settle the problem: the optimal competitive ratio tends to exactly $1-1/e$ as $k\to\infty$, and its worst case over all budgets $k$ is exactly $1/e$. The bound $1-1/e$ cannot be exceeded even with unlimited computation, and it is achieved by a single algorithm with at most $4n+1$ value queries; previously the best ratio without a shortlist was $1/e-o(1)$, with exponentially many queries. For general objectives, where the best known ratio was about $0.107$, we show that the optimal limiting ratio lies strictly between $1/e$ and $1/2$: we achieve $1/e+3.5\cdot10^{-6}$ for large $k$, and no algorithm achieves more than $0.497053$. We also achieve $0.2677$ at every budget. The main new ingredient of our algorithm is eligibility attenuation: an element that passes the price test at time $t$ is accepted with probability $e^{-τ}$, where $τ$ is the total earlier time during which it would have passed, which makes the probability that it has already been selected exactly $1-e^{-τ}$.
View PDFOpen arXiv