Online submodular welfare maximization faces fundamental limits beyond computation
Online Submodular Welfare Maximization: Computation is not the Bottleneck
Data Structures and Algorithms
Summary
The paper studies how well algorithms can allocate resources fairly and efficiently when items arrive one by one, a problem common in online ads and matching tasks. The authors show that a simple greedy strategy is as good as possible even with unlimited computing power, settling a long-standing question. They prove that no algorithm can outperform this approach in general, under both random and worst-case scenarios. This means the difficulty lies in the problem’s nature, not in computation limits.
What this means in practice
- •For online advertising teams: Understand fundamental limits on allocation quality in real-time bidding systems and improve expectations for algorithm performance.
- •For resource allocation engineers: Know that improving beyond greedy strategies for dynamic resource assignments may require new problem assumptions rather than more computation.
A theory result. No direct application yet.
Authors
Rajan Udwani, David Wajc
Abstract
We revisit the online submodular welfare maximization problem (OSW), a vast generalization of numerous well-studied online allocation problems, including online bipartite matching, display ads and AdWords. A natural greedy OSW algorithm achieves a competitive ratio of $1/2$ [LLN06], and $1-1/e$ under i.i.d. arrivals [KPV13]. Both bounds are tight for polynomial-time algorithms unless NP=RP [KPV13]. The information-theoretic limits for OSW, in contrast, remained open. This prompted researchers to ask for tighter upper bounds [Mehta13] or conjecture the existence of better-competitive (slow) algorithms [Huang23, LTX+23, CHS24, Huang2024, HTW24}. We resolve Mehta's question and refute the subsequent conjectures, proving that the greedy algorithm is in fact tight for both adversarial and i.i.d. arrivals, regardless of computation time. Seemingly contradicting recent $(1-1/e)$-competitive fractional algorithms for OSW [HJP+24,Patton26], we show that this impossibility even holds for fractional algorithms, provided their outputs correspond to marginals that are roundable in hindsight. Conceptually, our proofs can be seen as identifying that a bottleneck for OSW, even under (deterministic) adversarial arrivals, is the inherently random notion of correlation gap [ADSY12].