Submodular Secretary Problem

The submodular secretary problem is an online selection problem in which elements arrive in a uniformly random order and a nonnegative submodular function measures the value of the accepted set. An algorithm must accept or reject each arriving element irrevocably, subject to a cardinality budget (Bateni et al. 2013). The input size and budget are known in advance. In the value-oracle model, queries may involve only elements already seen. The competitive ratio compares the expected value obtained with the optimal value of a size-at-most- subset of the full input. There is no extra shortlist from which to choose later.

For a nondecreasing objective, Abdi et al. (2026) proved that the optimal competitive ratio tends to as . Over all cardinality budgets, the sharp worst-budget ratio is . For general nonnegative submodular functions, if denotes the optimal ratio at budget , their bounds are

while . These bounds do not establish existence of a limit for .

A ratio of 0.2677 is attainable for every budget with at most oracle queries. Their general-objective and monotone-objective guarantees use at most queries. The strict improvement above uses a separate polynomial-query construction for sufficiently large budgets (Abdi et al. 2026). The authors report substantive AI assistance in the mathematical development and formalization.