Optimality of Non-Adaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes
Rajan Udwani · Operations Research · 2025
Simplicity Meets Optimality in Online Resource Allocation Online platforms frequently manage sequential allocation decisions where outcomes are uncertain, such as selecting which products to display to a user. While it is often assumed that complex “adaptive” algorithms—those reacting to real-time feedback like user choices—are necessary for optimal performance, Rajan Udwani’s paper, “Optimality of Nonadaptive Algorithms in Online Submodular Welfare Maximization with Stochastic Outcomes,” challenges this assumption. The paper introduces a general framework and a “lifting” technique that translates established results from deterministic settings to those involving stochastic outcomes. Using this framework, Udwani demonstrates that nonadaptive Greedy-like algorithms, which remain oblivious to specific outcome realizations, achieve the best possible competitive ratios across diverse settings and arrival models. The findings suggest that for a broad class of objectives, including submodular functions, adaptivity offers no theoretical advantage. This allows for the use of simpler, more robust algorithms in environments where outcomes may be delayed or difficult to monitor.