← All problems

Information-theoretic limits for online submodular welfare maximization

Consider online allocation with nn agents having monotone submodular valuation functions vi:2[m]→R≥0v_i:2^{[m]}\to\mathbb{R}_{\ge 0}. Items arrive sequentially, and each item must be irrevocably assigned to an agent. The welfare of an allocation (S1,…,Sn)(S_1,\ldots,S_n) is W=∑i=1nvi(Si)W=\sum_{i=1}^n v_i(S_i), and the offline optimum is OPT⁡=max⁡(T1,…,Tn)∑i=1nvi(Ti)\operatorname{OPT}=\max_{(T_1,\ldots,T_n)}\sum_{i=1}^n v_i(T_i), where the TiT_i form a partition of the items. Determine the optimal information-theoretic competitive ratio of online algorithms: in the adversarial-arrival model, is sup⁡Ainf⁡IE[WA(I)]/OPT⁡(I)=1/2\sup_A\inf_I \mathbb{E}[W_A(I)]/\operatorname{OPT}(I)=1/2; and in the independently and identically distributed arrival model, is the corresponding optimal ratio 1−1/e1-1/e? Here AA ranges over all online algorithms, with no computational-time restriction, and II ranges over valid instances or arrival distributions in the relevant model.

References

Progress summary

Refreshed
Open · solution reported

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 1/21/2 under adversarial arrivals, or on 1−1/e1-1/e under i.i.d. arrivals for coverage valuations, is computationally hard unless NP=RP\mathrm{NP}=\mathrm{RP}.
  • A 2023 random-order result gives greedy ratios above 1/21/2, reaching at least 0.5050.505 generally and 0.510.51 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 1/21/2 under adversarial arrivals or 1−1/e1-1/e 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 1/21/2 and 1−1/e1-1/e remains unverified.

Sources

Solutions 0

No solutions have been posted yet.