Optimality of Nonadaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes

• 成果类型: Article; Early Access
• 署名作者: Udwani, Rajan
• 署名单位: University of California System; University of California Berkeley
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.0916
• 发表日期: 2026-07-03
• 关键词: online resource allocation; stochastic outcomes; submodular functions; competitive ratio; nonadaptive algorithms

摘要

We generalize the problem of online submodular welfare maximization to incorporate various stochastic elements that have gained significant attention in recent years. We show that a nonadaptive Greedy algorithm, which is oblivious to the realization of these stochastic elements, achieves the best possible competitive ratio among all polynomial-time algorithms, including adaptive ones, unless NP = RP. This result holds even when the objective function is not submodular but instead satisfies the weaker submodular order property. Our results unify and strengthen existing competitive ratio bounds across well-studied settings and diverse arrival models, showing that, in general, adaptivity to stochastic elements offers no advantage in terms of competitive ratio. To establish these results, we introduce a technique that lifts known results from the deterministic setting to the generalized stochastic setting. The technique has broad applicability, enabling us to show that, in certain special cases, nonadaptive Greedy-like algorithms outperform the Greedy algorithm and achieve the optimal competitive ratio. We also apply the technique in reverse to derive new upper bounds on the performance of Greedy-like algorithms in deterministic settings by leveraging upper bounds on the performance of nonadaptive algorithms in stochastic settings.