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

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.

Funding: Financial support from the Division of Civil, Mechanical and Manufacturing Innovation [Grant 2340306] and Google [Research Scholar Award] is gratefully acknowledged.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2024.0916.