betaFeedback

WorksComputer Science

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

Abstract

In the submodular secretary problem with a cardinality constraint, nn 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 kk elements. For monotone objectives we settle the problem: the optimal competitive ratio tends to exactly 1−1/e1-1/e as k→∞k\to\infty, and its worst case over all budgets kk is exactly 1/e1/e. The bound 1−1/e1-1/e cannot be exceeded even with unlimited computation, and it is achieved by a single algorithm with at most 4n+14n+1 value queries; previously the best ratio without a shortlist was 1/e−o(1)1/e-o(1), with exponentially many queries. For general objectives, where the best known ratio was about 0.1070.107, we show that the optimal limiting ratio lies strictly between 1/e1/e and 1/21/2: we achieve 1/e+3.5⋅10−61/e+3.5\cdot10^{-6} for large kk, and no algorithm achieves more than 0.4970530.497053. We also achieve 0.26770.2677 at every budget. The main new ingredient of our algorithm is eligibility attenuation: an element that passes the price test at time tt is accepted with probability e−τ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−τ1-e^{-τ}.

Introduction

In the classical secretary problem [7, 19], nn values are revealed in uniformly random order and we must stop at one of them, deciding irrevocably as each appears. Observing a 1/e1/e fraction of the values and then taking the next record selects the maximum with probability approaching 1/e1/e, which is optimal. Since the work of Hajiaghayi, Kleinberg, and Parkes [15] and Kleinberg [17], the random-order model has been used to study online selection of several elements, including under matroid constraints [6 ABH+26].

When the objective has decreasing marginal values, the natural formulation is the submodular secretary problem, introduced independently by Bateni, Hajiaghayi, and Zadimoghaddam [5] and Gupta, Roth, Schoenebeck, and Talwar [14]. We study its most basic constrained form. A ground set EE of nn elements arrives in uniformly random order, and the algorithm knows nn and an integer k≤nk \le n. When an element arrives, the algorithm may query a nonnegative submodular function f:2E→R≥0f : 2^E \to\mathbb{R}_{\ge0} on subsets of the elements that have arrived so far, and must then accept or reject the element immediately and irrevocably, accepting at most kk elements in total. Its competitive ratio is the infimum, over instances, of E[f(A)]/OPT\mathbb{E}[f(A)]/\mathrm{OPT}, where AA is the accepted set and OPT=max⁡∣S∣≤kf(S)\mathrm{OPT} = \max_{|S|\le k} f(S).

Offline, this problem has well-known benchmarks. For monotone ff, greedy achieves 1−(1−1/k)k≥1−1/e1-(1-1/k)^k \ge1-1/e [22], and no algorithm making polynomially many value queries does better asymptotically [21]. For general nonnegative ff, the measured continuous greedy algorithm achieves 1/e1/e [11]; this is a natural barrier for clean analyses, although more elaborate algorithms achieve slightly better constants [4, 8, 3]. Online, the known guarantees have remained far from these benchmarks. The ratio for monotone objectives improved from 0.0900.090 [5] to 0.1700.170 [10], and then Kesselheim and Tönnis Kesselheim and Tönnis [18] showed that repeatedly optimizing over the observed prefix gives 0.275−o(1)0.275-o(1) in polynomial time and 1/e−o(1)1/e-o(1) with exact, exponential-query optimization. For general objectives the best known ratios were 1/(8e2)1/(8e^2) [5] and then (e−1)2/(e2(1+e))≈0.107(e-1)^2/(e^2(1+e))\approx0.107 [12]. Agrawal, Shadravan, and Stein Agrawal, Shadravan, and Stein [2] reach 1−1/e−ε1-1/e-\varepsilon for monotone objectives, but only when the algorithm may keep a shortlist of O(k)O(k) candidates and make its final choice afterwards.

This leaves two basic questions open. Does the ability to delay decisions, which a shortlist grants, matter for monotone objectives? And can the 1/e1/e offline benchmark for general objectives be matched online?

Main results

Our main result answers both questions with a single algorithm, AttenuatedPricing (§ 3). To state it uniformly, we say that ff is μ\mu-monotone, for μ∈[0,1]\mu\in[0,1], if f(B)≥μf(S)f(B)\ge\mu f(S) whenever S⊆BS\subseteq B. Every nonnegative function is 00-monotone, and 11-monotone functions are exactly the monotone ones.

Theorem 1.1 (Algorithm). There is a randomized algorithm for the submodular secretary problem with a cardinality constraint that knows only nn and kk, accepts at most kk elements on every execution, makes at most 4n+14n+1 value queries, each on a subset of the elements that have arrived, and satisfies the following, uniformly over n≥kn\ge k and ff. (a) If ff is nonnegative and submodular, then E[f(A)]≥(1/e−O(log⁡2(k+1)/k))OPT\mathbb{E}[f(A)]\ge(1/e-O(\log^2(k+1)/k))\mathrm{OPT}. (b) If ff is nonnegative, monotone, and submodular, then E[f(A)]≥(1−1/e−O(log⁡(k+1)/k))OPT\mathbb{E}[f(A)]\ge(1-1/e-O(\log(k+1)/\sqrt{k}))\mathrm{OPT}. (c) More generally, if ff is μ\mu-monotone, then E[f(A)]≥(1/e+μ(1−2/e)−O(log⁡(k+1)/k))OPT\mathbb{E}[f(A)]\ge(1/e+\mu(1-2/e)-O(\log(k+1)/\sqrt{k}))\mathrm{OPT}.

The same algorithm runs in all three cases and does not use μ\mu. The value-query model counts queries and treats real arithmetic as exact. Theorem 3.1 gives a bound with explicit constants.

For monotone objectives this is the best possible asymptotic ratio, even for computationally unbounded algorithms.

Theorem 1.2 (Hardness). Let AA be any randomized online algorithm, with unlimited computation and unlimited queries on subsets of arrived elements. (a) For every k≥2k\ge2 and ε>0\varepsilon>0, there is a monotone coverage instance with budget kk on which AA has ratio at most 1−(1−1/k)k+ε1-(1-1/k)^k+\varepsilon. (b) For every k≥64k\ge64, there is a monotone coverage instance with budget kk and at most k2k^2 elements on which AA has ratio at most 1−1/e+O(log⁡log⁡k/log⁡k)1-1/e+O(\log\log k/\log k).

Unlike the offline barrier of [21], Theorem 1.2 is information-theoretic, and it arises purely from the inability to see the future. Combining the two theorems pins down the problem.

Corollary 1.3 (Monotone objectives are settled). Let ρkmon\rho_k^{\mathrm{mon}} be the optimal competitive ratio for the monotone submodular secretary problem with budget kk, over all algorithms with unlimited computation. Then lim⁡k→∞ρkmon=1−1/e\lim_{k \to\infty}\rho_k^{\mathrm{mon}} = 1 - 1/e, and inf⁡k≥1ρkmon=ρ1mon=1/e\inf_{k \ge1}\rho_k^{\mathrm{mon}} = \rho_1^{\mathrm{mon}} = 1/e.

The limit follows from Theorems 1.1 and 1.2, and the worst case over budgets from Theorem B.1 (see § 1.2), since the case k=1k = 1 is the classical secretary problem. So both the asymptotic ratio and the ratio that can be guaranteed uniformly over all budgets are determined exactly. A shortlist is not needed to reach 1−1/e1 - 1/e, and unlimited computation does not help to exceed it.

For general objectives, 1/e1/e is not the limit.

Theorem 1.4 (Beyond 1/e1/e). There is a randomized algorithm that knows only nn and kk, accepts at most kk elements, and makes polynomially many value queries on subsets of arrived elements, whose ratio on nonnegative submodular objectives is at least 1/e+3.5⋅10−61/e + 3.5 \cdot10^{-6} for all sufficiently large kk, uniformly in nn.

The algorithm (§ 5) runs, with a small probability, a variant of Greedy restricted to a pool of promising elements, and otherwise a variant of AttenuatedPricing that measures its progress against two disjoint near-optimal sets at the start. Neither alone beats 1/e1/e on every instance, but their guarantees depend in opposite directions on one parameter of the instance, which neither of them computes.

In the other direction, there is a barrier strictly below 1−1/e1 - 1/e, which comes from nonmonotonicity.

Theorem 1.5 (General objectives). Let A\mathcal{A} be any randomized online algorithm, with unlimited computation and unlimited queries on subsets of arrived elements.

(a) For all n≥2n \ge2, 1≤k≤n1 \le k \le n, μ∈[0,1]\mu\in[0,1], and ε>0\varepsilon> 0, there is a normalized μ\mu-monotone submodular instance on which A\mathcal{A} has ratio at most 1+μ2+ε\frac{1+\mu}{2} + \varepsilon. In particular, for general objectives the ratio is at most 12+ε\frac{1}{2} + \varepsilon.

(b) For every sufficiently large kk, there is a normalized nonnegative submodular instance with budget kk on which A\mathcal{A} has ratio at most 0.4970530.497053, and in which every singleton has value at most 10−6OPT10^{-6}\mathrm{OPT}. This holds even if A\mathcal{A} observes the arrival times.

Together with Theorem 1.4, this separates the general problem from both of its natural benchmarks.

Corollary 1.6 (General objectives). Let ρk\rho_k be the optimal competitive ratio for nonnegative submodular objectives with budget kk, over all algorithms with unlimited computation. Then

1e<1e+3.5⋅10−6≤lim inf⁡k→∞ρk≤lim sup⁡k→∞ρk≤0.497053<12.\frac{1}{e} < \frac{1}{e} + 3.5 \cdot10^{-6} \le\liminf_{k \to\infty}\rho_k \le\limsup_{k \to\infty}\rho_k \le0.497053 < \frac{1}{2}.

So the limiting ratio for general objectives lies strictly between 1/e1/e and 1/21/2, and in particular strictly below the monotone limit 1−1/e1 - 1/e; the lower bound is achieved with polynomially many queries. Offline, unlimited queries solve the problem exactly, and so these barriers are purely a consequence of online decisions. For polynomial-query algorithms the offline bound of 0.4910.491 [23] is numerically stronger, but it has a different source, namely query complexity. The bound 12\frac{1}{2} in part (a) comes from pairs of elements that are valuable separately and worthless together, and part (b) goes below it with matroid gadgets (§ 7.2), which the pairs alone cannot do. For μ\mu-monotone objectives, since coverage functions are monotone, the upper bound is min⁡{1+μ2,1−1/e}\min\{\frac{1+\mu}{2}, 1 - 1/e\} up to o(1)o(1) terms, and the lower bound of Theorem 1.1(c) meets it only at μ=1\mu= 1.

Table 1 summarizes the landscape.

ObjectivePrevious best (no shortlist)This paperUpper bound
Monotone1/e−o(1)1/e - o(1) [18] (exponential queries); 0.275−o(1)0.275 - o(1) [18] (polynomial queries)1−1/e−o(1)1 - 1/e - o(1); 1/e1/e for every kk1−1/e+o(1)1 - 1/e + o(1) (Theorem 1.2)
General0.1070.107 [12]1/e+3.5⋅10−61/e + 3.5 \cdot10^{-6}; 0.26770.2677 for every kk0.4970530.497053 (Theorem 1.5); 0.4910.491 with polynomially many queries [23]

Table 1. Asymptotic competitive ratios for large kk. AttenuatedPricing makes at most 4n+14n + 1 queries and achieves 1−1/e−o(1)1 - 1/e - o(1) and 1/e−o(1)1/e - o(1); the entry 1/e+3.5⋅10−61/e + 3.5 \cdot10^{-6} is achieved by the mixture of § 5, which makes polynomially many queries, and the entry 0.26770.2677 holds for every kk (§ 1.2). The 0.4910.491 entry follows because an online algorithm can be simulated offline on a random permutation.

Every budget

The guarantees of Theorems 1.1 and 1.4 take effect only for large kk. We also give explicit guarantees at every budget, with no error term, uniformly in n≥kn \ge k. For general objectives, some algorithm making at most 6n+16n + 1 value queries has ratio at least 0.26770.2677 for every kk; the ratio is at least 0.37340.3734 for k=2k = 2, at least 0.30.3 for k≥52k \ge52, and at least 0.36760.3676 for k≥106k \ge10^{6} (Theorem A.1). It uses two picks for k≤3k \le3, for 4≤k≤294 \le k \le29 a multi-rank secretary rule that is restarted after every stop on a geometric time grid, and Poisson-tail prices with eligibility attenuation for larger kk. For monotone objectives, the ratio is at least 1/e1/e for every kk: exactly 1/e1/e for k=1k = 1, more than 0.36960.3696 for every k≥2k \ge2, and more than 1/21/2 for every k≥98k \ge98 (Theorem B.1). It uses exact optimization over the observed prefix for k≤21k \le21, with O(n21)O(n^{21}) queries, for 22≤k<10622 \le k < 10^{6} a price policy mixed with the single-choice rule, with at most n+1n + 1 queries, and for larger kk a variant of AttenuatedPricing. Since k=1k = 1 contains the classical secretary problem, 1/e1/e cannot be improved as a bound that holds for all kk simultaneously. These results are proved in the appendices.

Technical overview

We describe the algorithm by building it up in three steps. Throughout, give each element an independent uniform arrival time in [0,1][0,1], and write f(i∣A)=f(A∪{i})−f(A)f(i \mid A) = f(A \cup\{i\}) - f(A).

References

  1. [2]Shipra Agrawal, Mohammad Shadravan, and Cliff Stein. Submodular secretary problem with shortlists. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS), volume 124 of LIPIcs, pages 1:1–1:19, 2019.arxiv.org/abs/1809.05082
  2. [3]Niv Buchbinder and Moran Feldman. Constrained submodular maximization via new bounds for DR-submodular functions. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1820–1831, 2024.arxiv.org/abs/2311.01129
  3. [4]Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1433–1452, 2014.
  4. [5]MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Morteza Zadimoghaddam. Submodular secretary problem and extensions. ACM Transactions on Algorithms, 9(4):32:1–32:23, 2013.
  5. [6]Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 434–443, 2007.DOI
  6. [7]E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Mathematics Doklady, 4:627–629, 1963.
  7. [8]Alina Ene and Huy L. Nguyen. Constrained submodular maximization: beyond 1/e. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 248–257, 2016.arxiv.org/abs/1608.03611
  8. [9]Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40(4):1133–1153, 2011.
  9. [10]Moran Feldman, Joseph Naor, and Roy Schwartz. Improved competitive ratios for submodular secretary problems. In Proceedings of APPROX, volume 6845 of LNCS, pages 218–229, 2011.
  10. [11]Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 570–579, 2011.DOI
  11. [12]Kaito Fujii. An improved algorithm for the submodular secretary problem with a cardinality constraint. arXiv:1905.04941, 2019.arxiv.org/abs/1905.04941
  12. [13]Moran Feldman and Rico Zenklusen. The submodular secretary problem goes linear. SIAM Journal on Computing, 47(2):330–366, 2018.
  13. [14]Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. Constrained non-monotone submodular maximization: offline and secretary algorithms. In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE), pages 246–257, 2010.arxiv.org/abs/1003.1517
  14. [15]Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, and David C. Parkes. Adaptive limited-supply online auctions. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 71–80, 2004.DOI
  15. [16]Dennis Joyce. A refined analysis for matroid secretary with submodular objectives. arXiv:2610.11516, 2026.arxiv.org/abs/2610.11516
  16. [17]Robert Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 630–631, 2005.DOI
  17. [18]Thomas Kesselheim and Andreas Tönnis. Submodular secretary problems: cardinality, matching, and linear constraints. In Proceedings of APPROX/RANDOM, volume 81 of LIPIcs, pages 16:1–16:22, 2017.arxiv.org/abs/1607.08805
  18. [19]D. V. Lindley. Dynamic programming and decision theory. Journal of the Royal Statistical Society, Series C, 10(1):39–51, 1961.DOI
  19. [20]Paul Liu, Aviad Rubinstein, Jan Vondrák, and Junyao Zhao. Cardinality constrained submodular maximization for random streams. In Advances in Neural Information Processing Systems (NeurIPS), 2021. arXiv:2111.07217.arxiv.org/abs/2111.07217
  20. [21]George L. Nemhauser and Laurence A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3(3):177–188, 1978.DOI
  21. [22]George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 14(1):265–294, 1978.DOI
  22. [23]Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1098–1116, 2011.
  23. [24]Aviad Rubinstein and Junyao Zhao. Maximizing non-monotone submodular functions over small subsets: beyond 1/2-approximation. In Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP), volume 229 of LIPIcs, pages 106:1–106:17, 2022.arxiv.org/abs/2204.11149
  24. [25]Mohammad Shadravan. Improved submodular secretary problem with shortlists. arXiv:2010.01901, 2020.arxiv.org/abs/2010.01901
  25. [26]Rajan Udwani and David Wajc. Online submodular welfare maximization: computation is not the bottleneck. arXiv:2610.16060, 2026.arxiv.org/abs/2610.16060

Paper details

vlnc:W_u2fvugqk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Opus 5.5, Claude Fable 5.2

View statement
Looking for related papers…
Contents