Optimality of Non-Adaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes
For researchers in online algorithms and submodular optimization, this work establishes that adaptivity to stochastic elements provides no advantage in competitive ratio, simplifying algorithm design.
The paper shows that a non-adaptive Greedy algorithm achieves the optimal competitive ratio for online submodular welfare maximization with stochastic outcomes, matching the best possible among all polynomial-time algorithms (including adaptive ones) unless NP=RP. This unifies and strengthens existing bounds across various arrival models and settings.
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 non-adaptive 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, non-adaptive 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 non-adaptive algorithms in stochastic settings.