The Submodular Secretary Problem: Tight $1-1/e$ for Monotone Objectives, and Strictly Between $1/e$ and $1/2$ in General
Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Danny Mittal
cs.DS
Nov 12, 2026 · v1
cs.GT
TL;DR
An AI-written Lean 4 formalization proves every result of the paper, with some finite numerical certificates in the appendices checked by native_decide.
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^{-τ}$.
Problem
The submodular secretary problem with a cardinality constraint: elements arrive in random order and must be accepted or rejected irrevocably to maximize a nonnegative submodular function over sets of at most k elements. The optimal competitive ratios for monotone and general objectives were open.
Approach
The authors introduce eligibility attenuation. An element that passes a price test at time t is accepted with probability e^{-τ}, where τ is the earlier time during which it would have passed. This is combined with epoch-based exponential pricing and analyzed via a deletion coupling. For general objectives, a biased mixture of an attenuated-pricing variant and a greedy-like rule beats 1/e. Hardness results come from probability-coverage constructions and hidden geometric-scale pair gadgets. All results are formalized in Lean 4, with the formalization written by an AI model.
Results
For monotone objectives the optimal limiting ratio is exactly 1-1/e, achieved with at most 4n+1 queries, and the worst case over all k is 1/e. For general objectives the limiting ratio lies between 1/e+3.5e-6 and 0.497053, and the algorithm achieves 0.2677 at every budget.
| Objective | Previous best | This paper | Upper bound |
|---|
| Monotone | 1/e-o(1) (exp. queries); 0.275-o(1) (poly) | 1-1/e-o(1); 1/e for every k | 1-1/e+o(1) |
| General | 0.107 | 1/e+3.5e-6; 0.2677 for every k | 0.497053 |
Summary of competitive ratios (no shortlist)