Information-theoretic limits for online submodular welfare maximization
Consider online allocation with agents having monotone submodular valuation functions . Items arrive sequentially, and each item must be irrevocably assigned to an agent. The welfare of an allocation is , and the offline optimum is , where the form a partition of the items. Determine the optimal information-theoretic competitive ratio of online algorithms: in the adversarial-arrival model, is ; and in the independently and identically distributed arrival model, is the corresponding optimal ratio ? Here ranges over all online algorithms, with no computational-time restriction, and ranges over valid instances or arrival distributions in the relevant model.
References
- Online Submodular Welfare Maximization: Computation is not the Bottleneck — arXiv — Rajan Udwani, David Wajc
Source: arXiv
Progress summary
A new unrefereed preprint claims that no online method can beat the standard guarantees in either adversarial or independently random arrivals, but the claim has not been independently checked.
The problem concerns whether the familiar guarantees for online submodular welfare are fundamental information limits rather than merely limits of efficient computation. The new claim addresses Mehta’s question and attributes the obstruction to the correlation gap.
Known results
- Kapralov, Post, and Vondrák (2013): improving on under adversarial arrivals, or on under i.i.d. arrivals for coverage valuations, is computationally hard unless .
- A 2023 random-order result gives greedy ratios above , reaching at least generally and for some special classes; this does not settle adversarial or i.i.d. arrivals.
October 2026 claimed tightness
An arXiv preprint by Rajan Udwani and David Wajc claims that no online algorithm, regardless of computation time, exceeds under adversarial arrivals or under i.i.d. arrivals. It also claims the lower bounds for fractional algorithms whose marginal outputs are roundable in hindsight. The claim is unrefereed and has no independent verification in the retrieved sources.
Current status (as of October 2026): The computational barriers and random-order improvements are established, while the claimed information-theoretic tightness at and remains unverified.
Solutions 0
No solutions have been posted yet.