pith. sign in

arxiv: 2606.22520 · v1 · pith:M2QQH6TZnew · submitted 2026-06-21 · 💻 cs.DS

Submodular Welfare Maximization with Budget Constraints in the Random-Order Model

Max Klimm , Martin Knaack This is my paper

Pith reviewed 2026-06-26 09:41 UTC · model grok-4.3

classification 💻 cs.DS
keywords submodular welfare maximizationbudget constraintsrandom-order modelcompetitive ratioonline allocationmultilinear extensionitem assignment
0
0 comments X

The pith

Online algorithm achieves roughly 1/14.85 competitive ratio for multi-agent submodular welfare with budgets in random order.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops algorithms for allocating randomly arriving items to agents with budgets to maximize a monotone submodular objective over assignments. It gives a polynomial-time algorithm with competitive ratio approximately 1/14.85 that works for any number of agents, improving the prior single-agent bound of 1/54.4. For the unit-cost and unit-budget special case it reaches 1/6.86 instead of the earlier 1/9.66. The approach repeatedly uses (1-1/e)-approximations to multilinear extensions of offline subproblems. A reader would care because the model captures many practical online resource allocation tasks that exhibit diminishing returns.

Core claim

We present a polynomial-time α-competitive algorithm with α ≈ 1/14.85 for the general budgeted submodular welfare maximization problem in the random-order model with an arbitrary number of agents. For the special case in which all item costs and budgets equal 1 we obtain a 1/6.86-competitive algorithm. Both algorithms rely on repeatedly computing (1-1/e)-approximations of the multilinear extensions of offline variants of the arising subproblems; super-polynomial runtime improves the ratios by this approximation factor.

What carries the argument

Repeated computation of (1-1/e)-approximations to the multilinear extensions of offline subproblems to guide irrevocable item assignments under random arrival order.

If this is right

  • The result directly covers welfare maximization with submodular valuations together with agent-specific costs and budgets.
  • The unit-cost unit-budget case yields an improved guarantee for the online submodular matching problem.
  • Allowing super-polynomial runtime multiplies the competitive ratios by the factor (1-1/e).
  • The algorithms run in polynomial time and therefore apply to practical online allocation settings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The random-order assumption might be relaxed via techniques that generate or simulate random permutations from other arrival processes.
  • The same subproblem-approximation template could be tested on related constrained submodular problems such as online sensor placement or coverage maximization.
  • Running the algorithms on concrete instances drawn from combinatorial auctions would reveal how close the achieved ratios come to the theoretical bounds in practice.

Load-bearing premise

Items arrive in a uniformly random order so that the analysis can average performance over all possible permutations.

What would settle it

An explicit instance with a monotone submodular function, agent budgets, and item costs such that the algorithm's expected value over random arrival orders falls below 1/14.85 times the offline optimum.

Figures

Figures reproduced from arXiv: 2606.22520 by Martin Knaack, Max Klimm.

Figure 1
Figure 1. Figure 1: Problem classes for online problems in the random-order model with submodular objectives and [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
read the original abstract

We study an online item-allocation problem with budgets and a submodular objective. A set of $m$ agents is known in advance, and each agent $j$ has a known budget. A set of $n$ items arrives over time in a uniformly random order. When item $i$ arrives, its cost $c_{i,j}$ for each agent $j$ is revealed, and the algorithm must irrevocably assign $i$ to an agent without violating any budget constraint. The goal is to maximize a monotone submodular function defined over all possible assignments $[n] \times [m]$. At the time of decision, the algorithm has only oracle access to this submodular function restricted to items seen so far. This model subsumes welfare maximization with submodular valuations, agent-specific item costs, and agent-specific budgets. We measure the performance of an algorithm by its competitive ratio, i.e., the worst-case ratio between the algorithm's expected value and that of the offline optimum, which knows all item costs and the full submodular function in advance. Prior work only considered the case of a single agent and achieved a $1/54.4$-competitive algorithm. We generalize and improve this result to a polynomial-time $\alpha$-competitive algorithm with $\alpha \approx 1/14.85$ for an arbitrary number of agents. We also study the special case in which all item costs and all budgets equal $1$, which yields an online submodular matching problem. Prior work achieved a polynomial $1/9.66$-competitive algorithm for this problem; we improve this to a factor of $1/6.86$. Both our algorithms rely on repeatedly computing $(1 - 1/e)$-approximations of the multilinear extensions of offline variants of the subproblems. If super-polynomial runtime is allowed, these subproblems can be solved optimally, and our competitive ratios improve by this factor.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies online submodular welfare maximization with per-agent budgets and item costs in the random-order model. Items arrive in random order; upon arrival an algorithm sees per-agent costs and must assign the item irrevocably without violating budgets, with only oracle access to the submodular function on seen items. The authors give polynomial-time algorithms achieving competitive ratios ≈1/14.85 (general case, arbitrary number of agents) and 1/6.86 (unit-cost/unit-budget special case), improving on prior single-agent 1/54.4 and unit 1/9.66 bounds. Both algorithms repeatedly invoke (1−1/e)-approximations to multilinear extensions of suitable offline subproblems; super-polynomial time yields the same ratios multiplied by (1−1/e).

Significance. If the claimed ratios hold, the work materially advances the state of the art for online submodular allocation under budget constraints. Extending the single-agent result to multiple agents while improving the ratio, and tightening the unit-cost bound, are both non-trivial. The explicit use of multilinear-extension oracles inside a random-order competitive analysis is a concrete technical contribution that may transfer to other online submodular problems.

minor comments (3)
  1. [§1] §1, paragraph after the unit-cost result: the sentence claiming the ratios are obtained by “repeatedly computing (1−1/e)-approximations” should be expanded with a one-sentence pointer to the precise offline subproblem solved at each step (e.g., which multilinear extension and which constraint set).
  2. [Abstract / §4] The numerical constants 1/14.85 and 1/6.86 appear without an accompanying equation or optimization program that produces them. Adding a short appendix or footnote that states the exact optimization problem whose solution yields these numbers would improve reproducibility.
  3. [Theorem statements] Notation for the submodular function f is introduced only in the model section; a one-line reminder of monotonicity and submodularity assumptions when the competitive-ratio theorems are stated would help readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the technical contributions, and recommendation of minor revision. No major comments were listed in the report, so we have no specific points requiring rebuttal or clarification at this time.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation relies on standard competitive-analysis techniques that combine random-order arrival with (1-1/e)-approximations to multilinear extensions of offline subproblems. These steps are independent of the target competitive ratios; the ratios 1/14.85 and 1/6.86 are obtained by analyzing the online-to-offline reduction rather than by fitting parameters to the output or by self-definitional equations. No load-bearing self-citations, uniqueness theorems imported from the authors' prior work, or renamings of known results appear in the provided text. The analysis is self-contained against external benchmarks such as the cited single-agent result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the random-order arrival model and the standard definition of monotone submodular functions; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption Items arrive in uniformly random order
    Explicitly stated as the arrival model in the problem definition.
  • domain assumption The objective is a monotone submodular function
    Stated as the welfare objective throughout the abstract.

pith-pipeline@v0.9.1-grok · 5890 in / 1328 out tokens · 17395 ms · 2026-06-26T09:41:56.221787+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

36 extracted references · 32 canonical work pages · 1 internal anchor

  1. [1]

    Improved online algorithms for knapsack and GAP in the random order model.Algorithmica, 83(6):1750–1785, 2021

    Susanne Albers, Arindam Khan, and Leon Ladewig. Improved online algorithms for knapsack and GAP in the random order model.Algorithmica, 83(6):1750–1785, 2021. doi:10.1007/S00453-021-00801-2

    work page doi:10.1007/s00453-021-00801-2 2021

  2. [2]

    Budget-feasible mechanism design for non- monotone submodular objectives: Offline and online.Mathematics of Operations Research, 47(3):2286– 2309, 2022

    Georgios Amanatidis, Pieter Kleer, and Guido Sch¨ afer. Budget-feasible mechanism design for non- monotone submodular objectives: Offline and online.Mathematics of Operations Research, 47(3):2286– 2309, 2022. doi:10.1287/MOOR.2021.1208

    work page doi:10.1287/moor.2021.1208 2022

  3. [3]

    Online budget-feasible mechanism design with predictions

    Georgios Amanatidis, Evangelos Markakis, Christodoulos Santorinaios, Guido Sch¨ afer, Panagiotis Tsamopoulos, and Artem Tsikiridis. Online budget-feasible mechanism design with predictions. In Ron Lavi and Jie Zhang, editors,Proceedings of the 18th International Symposium on Algorithmic Game Theory (SAGT), volume 15953 ofLNCS, pages 402–421, 2025. doi:10....

    work page doi:10.1007/978-3-032-03639-1 2025

  4. [4]

    Fully-Dynamic All-Pairs Shortest Paths: Faster and Allowing Negative Cycles , booktitle =

    Nir Andelman and Yishay Mansour. Auctions with budget constraints. In Torben Hagerup and Jyrki Katajainen, editors,Proceedings of the 9th Scandinavian Workshop on Algorithm Theory Algorithm Theory (SWAT), volume 3111 ofLNCS, pages 26–38. Springer, 2004. doi:10.1007/978-3-540-27810-8 4

    work page doi:10.1007/978-3-540-27810-8 2004

  5. [5]

    Birnbaum, Anna R

    Yossi Azar, Benjamin E. Birnbaum, Anna R. Karlin, Claire Mathieu, and C. Thach Nguyen. Improved approximation algorithms for budgeted allocations. In Luca Aceto, Ivan Damg˚ ard, Leslie Ann Goldberg, Magn´ us M. Halld´ orsson, Anna Ing´ olfsd´ ottir, and Igor Walukiewicz, editors,Proceedings of the 35th International Colloquium on Automata, Languages and P...

    work page doi:10.1007/978-3-540-70575-8 2008

  6. [6]

    Submod- ular secretary problem and extensions.ACM Transactions on Algorithms, 9(4):32:1–32:23, 2013

    MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, and Morteza Zadimoghaddam. Submod- ular secretary problem and extensions.ACM Transactions on Algorithms, 9(4):32:1–32:23, 2013. doi:10.1145/2500121

    work page doi:10.1145/2500121 2013

  7. [7]

    Maximizing a monotone submod- ular function subject to a matroid constraint.SIAM Journal on Computing, 40(6):1740–1766, 2011

    Gruia Calinescu, Chandra Chekuri, Martin P´ al, and Jan Vondr´ ak. Maximizing a monotone submod- ular function subject to a matroid constraint.SIAM Journal on Computing, 40(6):1740–1766, 2011. doi:10.1137/080733991

    work page doi:10.1137/080733991 2011

  8. [8]

    On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP.SIAM Journal on Computing, 39(6): 2189–2211, 2010

    Deeparnab Chakrabarty and Gagan Goel. On the approximability of budgeted allocations and improved lower bounds for submodular welfare maximization and GAP.SIAM Journal on Computing, 39(6): 2189–2211, 2010. doi:10.1137/080735503

    work page doi:10.1137/080735503 2010

  9. [9]

    Fischer, and Kevin Schewior

    Jos´ e Correa, Paul D¨ utting, Felix A. Fischer, and Kevin Schewior. Prophet inequalities for independent and identically distributed random variables from an unknown distribution.Mathematics of Operations Research, 47(2):1287–1309, 2022. doi:10.1287/MOOR.2021.1167

    work page doi:10.1287/moor.2021.1167 2022

  10. [10]

    Evgenii B. Dynkin. Optimal choice of the stopping moment of a Markov process.Doklady Akademii Nauk SSSR, 150:238–240, 1963

    1963

  11. [11]

    Approximation algorithms for allocation problems: Improving the factor of 1−1/e

    Uriel Feige and Jan Vondr´ ak. Approximation algorithms for allocation problems: Improving the factor of 1−1/e. InProceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 667–676, 2006. doi:10.1109/FOCS.2006.14

    work page doi:10.1109/focs.2006.14 2006

  12. [12]

    The submodular secretary problem goes linear.SIAM Journal on Computing, 47, 2018

    Moran Feldman and Rico Zenklusen. The submodular secretary problem goes linear.SIAM Journal on Computing, 47, 2018. doi:10.1137/16M1105220

    work page doi:10.1137/16m1105220 2018

  13. [13]

    Improved competitive ratios for submodular secre- tary problems (extended abstract)

    Moran Feldman, Joseph Naor, and Roy Schwartz. Improved competitive ratios for submodular secre- tary problems (extended abstract). In Leslie Ann Goldberg, Klaus Jansen, R. Ravi, and Jos´ e D. P. Rolim, editors,Proceedings of the 14th International Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX), pages 218–229, 2011. doi:1...

    work page doi:10.1007/978-3-642-22935-0 2011

  14. [14]

    Fisher, George L

    Marshall L. Fisher, George L. Nemhauser, and Laurence A. Wolsey. An analysis of approximations for maximizing submodular set functions - II.Mathematical Programming Studies, 8:73–87, 1978. 21

    1978

  15. [15]

    IVOA Recommendation: Simple Image Access Specification Version 1.0

    Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko. Tight approximation algorithms for maximum separable assignment problems.Mathematics of Operations Research, 36(3): 416–431, 2011. doi:10.1287/MOOR.1110.0499

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1287/moor.1110.0499 2011

  16. [16]

    Online budgeted matching in random input models with applications to adwords

    Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In Shang-Hua Teng, editor,Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 982–991, 2008

    2008

  17. [17]

    Online submodular welfare maximization: Greedy is optimal

    Michael Kapralov, Ian Post, and Jan Vondr´ ak. Online submodular welfare maximization: Greedy is optimal. In Sanjeev Khanna, editor,Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1216–1225, 2013. doi:10.1137/1.9781611973105.88

    work page doi:10.1137/1.9781611973105.88 2013

  18. [18]

    Submodular secretary problems: Cardinality, matching, and linear constraints

    Thomas Kesselheim and Andreas T¨ onnis. Submodular secretary problems: Cardinality, matching, and linear constraints. available underhttps://arxiv.org/abs/1607.08805, 2016

    Pith/arXiv arXiv 2016

  19. [19]

    Submodular secretary problems: Cardinality, matching, and linear constraints

    Thomas Kesselheim and Andreas T¨ onnis. Submodular secretary problems: Cardinality, matching, and linear constraints. In Klaus Jansen, Jos´ e D. P. Rolim, David Williamson, and Santosh S. Vem- pala, editors,Proceedings of the 20th International Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX), pages 16:1–16:22, 2017. doi:1...

    work page doi:10.4230/lipics.approx- 2017

  20. [20]

    An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions

    Thomas Kesselheim, Klaus Radke, Andreas T¨ onnis, and Berthold V¨ ocking. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In Hans L. Bodlaender and Giuseppe F. Italiano, editors,Proceedings of the 21st Annual European Symposium on Algorithms (ESA), pages 589–600, 2013. doi:10.1007/978-3-642-40450-4 50

    work page doi:10.1007/978-3-642-40450-4 2013

  21. [21]

    Primal beats dual on online packing lps in the random-order model.SIAM Journal on Computing, 47(5):1939–1964, 2018

    Thomas Kesselheim, Klaus Radke, Andreas T¨ onnis, and Berthold V¨ ocking. Primal beats dual on online packing lps in the random-order model.SIAM Journal on Computing, 47(5):1939–1964, 2018. doi:10.1137/15M1033708

    work page doi:10.1137/15m1033708 1939

  22. [22]

    Lipton, Evangelos Markakis, and Aranyak Mehta

    Subhash Khot, Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. Inapproximability re- sults for combinatorial auctions with submodular utility functions.Algorithmica, 52(1):3–18, 2008. doi:10.1007/S00453-007-9105-7

    work page doi:10.1007/s00453-007-9105-7 2008

  23. [23]

    Generalized assignment and knapsack problems in the random-order model

    Max Klimm and Martin Knaack. Generalized assignment and knapsack problems in the random-order model. In Nicole Megow and Amitabh Basu, editors,Proceedings of the 26th Integer Programming and Combinatorial Optimization Conference (IPCO), pages 341–354, 2025. doi:10.1007/978-3-031-93112- 3 25

    work page doi:10.1007/978-3-031-93112- 2025

  24. [24]

    Submodular maximization over multiple matroids via generalized exchange properties.Mathematics of Operations Research, 35(4):795–806, 2010

    Jon Lee, Maxim Sviridenko, and Jan Vondr´ ak. Submodular maximization over multiple matroids via generalized exchange properties.Mathematics of Operations Research, 35(4):795–806, 2010. doi:10.1287/MOOR.1100.0463

    work page doi:10.1287/moor.1100.0463 2010

  25. [25]

    Combinatorial auctions with decreasing marginal utilities.Games and Economic Behavior, 55(2):270–296, 2006

    Benny Lehmann, Daniel Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities.Games and Economic Behavior, 55(2):270–296, 2006. doi:10.1016/J.GEB.2005.02.006

    work page doi:10.1016/j.geb.2005.02.006 2006

  26. [26]

    Dennis V. Lindley. Dynamic programming and decision theory.Journal of the Royal Statistical Society. Series C, 10:39–51, 1961. doi:10.2307/2985407

    work page doi:10.2307/2985407 1961

  27. [27]

    The simulated greedy algorithm for several submodular matroid secretary problems.Theory of Computing Systems, 58(4):681–706, 2016

    Tengyu Ma, Bo Tang, and Yajun Wang. The simulated greedy algorithm for several submodular matroid secretary problems.Theory of Computing Systems, 58(4):681–706, 2016. doi:10.1007/S00224-015-9642- 4

    work page doi:10.1007/s00224-015-9642- 2016

  28. [28]

    Vazirani, and Vijay V

    Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, and Vijay V. Vazirani. Adwords and generalized online matching.Journal of the ACM, 54(5):22, 2007. doi:10.1145/1284320.1284321

    work page doi:10.1145/1284320.1284321 2007

  29. [29]

    Online multidimensional packing problems in the random-order model

    David Naori and Danny Raz. Online multidimensional packing problems in the random-order model. In Pinyan Lu and Guochuan Zhang, editors,Proceedings of the 30th International Sym- posium on Algorithms and Computation (ISAAC), volume 149 ofLIPIcs, pages 10:1–10:15, 2019. doi:10.4230/LIPICS.ISAAC.2019.10. 22

    work page doi:10.4230/lipics.isaac.2019.10 2019

  30. [30]

    Nemhauser, Laurence A

    George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approxima- tions for maximizing submodular set functions - I.Mathematical Programming, 14(1):265–294, 1978. doi:10.1007/BF01588971

    work page doi:10.1007/bf01588971 1978

  31. [31]

    Budgeted allocations in the full-information setting

    Aravind Srinivasan. Budgeted allocations in the full-information setting. In Ashish Goel, Klaus Jansen, Jos´ e D. P. Rolim, and Ronitt Rubinfeld, editors,Proceedings of the 11th International Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX), pages 247–253, 2008. doi:10.1007/978-3-540-85363-3 20

    work page doi:10.1007/978-3-540-85363-3 2008

  32. [32]

    Monotonek-submodular secretary prob- lems: Cardinality and knapsack constraints.Theoretical Computer Science, 921:86–99, 2022

    Zhongzheng Tang, Chenhao Wang, and Hau Chan. Monotonek-submodular secretary prob- lems: Cardinality and knapsack constraints.Theoretical Computer Science, 921:86–99, 2022. doi:10.1016/J.TCS.2022.04.003

    work page doi:10.1016/j.tcs.2022.04.003 2022

  33. [33]

    Online knapsack problem and budgeted truthful bipartite matching

    Rahul Vaze. Online knapsack problem and budgeted truthful bipartite matching. InPro- ceedings of the IEEE Conference on Computer Communications (INFOCOM), pages 1–9, 2017. doi:10.1109/INFOCOM.2017.8057223

    work page doi:10.1109/infocom.2017.8057223 2017

  34. [34]

    Optimal approximation for the submodular welfare problem in the value oracle model

    Jan Vondr´ ak. Optimal approximation for the submodular welfare problem in the value oracle model. In Cynthia Dwork, editor,Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 67–74, 2008. doi:10.1145/1374376.1374389

    work page doi:10.1145/1374376.1374389 2008

  35. [35]

    Maximizingk-submodular functions and beyond.ACM Transactions on Algorithms, 12(4):47:1–47:26, 2016

    Justin Ward and Stanislav Zivn´ y. Maximizingk-submodular functions and beyond.ACM Transactions on Algorithms, 12(4):47:1–47:26, 2016. doi:10.1145/2850419

    work page doi:10.1145/2850419 2016

  36. [36]

    Laurence A. Wolsey. Maximising real-valued submodular functions: Primal and dual heuristics for location problems.Mathematics of Operations Research, 7(3):410–425, 1982. doi:10.1287/moor.7.3.410. 23

    work page doi:10.1287/moor.7.3.410 1982