pith. sign in

arxiv: 2606.08328 · v1 · pith:I5FLY575new · submitted 2026-06-06 · 💻 cs.DS

Optimal Online Equitable Allocation with Indivisible Resources

Ramiro N. Deo-Campo Vuong This is my paper

Pith reviewed 2026-06-27 18:52 UTC · model grok-4.3

classification 💻 cs.DS
keywords online allocationindivisible goodsdiscrete polymatroidsmajorizationequitable allocationcompetitive ratiosbrick-laying algorithm
0
0 comments X

The pith

Brick-Laying, a greedy algorithm that minimizes the sum of squared loads, achieves majorization minimax-optimality for online allocation of indivisible resources under discrete polymatroid constraints.

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

The paper establishes that in online settings where indivisible resources must be allocated to agents subject to discrete polymatroid constraints, the Brick-Laying algorithm delivers a strong form of optimality. This algorithm makes myopic decisions by always choosing the allocation that minimizes the current sum of squared loads across agents. If true, this means one simple rule works universally for any number of agents or resources and provides optimal guarantees for every Schur-concave or Schur-convex objective without needing to know the objective in advance. A reader would care because equitable allocation arises in load balancing, routing, and marketplaces, and this removes the need for objective-specific tuning or knowledge of future arrivals.

Core claim

Brick-Laying achieves a universal and objective-free notion of optimality called majorization minimax-optimality for the online discrete polymatroid allocation setting. As a result, it simultaneously guarantees minimax optimal competitive ratios and regret for all Schur-concave and Schur-convex objectives for any number of agents and resources. The proof relies on majorization comparisons and the conjugates of integer partitions to characterize worst-case instances, revealing a connection between partition geometry and online allocation.

What carries the argument

The Brick-Laying algorithm, which greedily minimizes the sum of squared loads on agents at each step, using majorization to compare allocations and integer partition conjugates to identify worst cases.

If this is right

  • It guarantees minimax optimal competitive ratios and regret for all Schur-concave and Schur-convex objectives.
  • The guarantees hold for any number of agents and resources and are agnostic to problem scale.
  • Worst-case instances can be characterized using conjugates of integer partitions.
  • Majorization provides a way to compare allocations without depending on specific objectives.

Where Pith is reading between the lines

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

  • The structural connection between partition geometry and allocation might extend to other online combinatorial problems.
  • Similar greedy rules could be analyzed in stochastic arrival models using the same majorization tools.
  • This approach might simplify analysis in related areas like online fair division or scheduling.

Load-bearing premise

The majorization minimax-optimality notion transfers directly from the prior work to the online discrete polymatroid setting without additional structural assumptions.

What would settle it

Finding a specific online instance of discrete polymatroid allocations where some other algorithm produces an allocation that is strictly better in the majorization minimax sense than Brick-Laying would falsify the claim.

Figures

Figures reproduced from arXiv: 2606.08328 by Ramiro N. Deo-Campo Vuong.

Figure 1
Figure 1. Figure 1: The graph on the left shows an instance P of online batched semi-matching with n = 3 agents and m = 5 resources, arriving over two rounds. On the right, we give the intermediate loads of brick-laying and OPT(BL,P), where ℓt(i) is the load on agent i after round t. In round 1, brick-laying is indifferent between loads (2, 1, 0) and (1, 2, 0); in round 2, the only majorization-minimal allocation is (1, 0, 1)… view at source ↗
Figure 2
Figure 2. Figure 2: The graph on the left illustrates the nested instance Pb with 5 rounds output by Algorithm 2 given instance P. On the right, we show the intermediate loads of brick-laying after each epoch and the loads of a hindsight solution we construct in Lemma 1. Note that this is not OPT(BL, Pb), but rather, demonstrates that OPT(BL,P) is still feasible (up to permutation) in Pb. Against the strategy P in [PITH_FULL… view at source ↗
read the original abstract

Equitable allocation of indivisible goods to agents in online settings is an algorithmic primitive with applications for load balancing, network routing, online marketplaces, and multi-agent systems. We consider a general setting in which allocations are constrained to be bases of discrete polymatroids that arrive online. Our work demonstrates that a simple, myopic algorithm called Brick-Laying, which greedily minimizes the sum of squared loads on agents, achieves a universal and objective-free notion of optimality called majorization minimax-optimality [BDK26] for this setting. As a consequence, Brick-Laying simultaneously guarantees minimax optimal competitive ratios and regret for all Schur-concave and Schur-convex objectives, and for any number of agents and resources (despite being agnostic to problem scale). Departing from popular primal-dual analysis, we employ majorization to compare allocations. We leverage the conjugates of integer partitions -- which act as a discrete dual to majorization -- to characterize worst-case instances for the Brick-Laying algorithm. Our approach reveals a novel structural connection between the geometry of partitions and online equitable allocation.

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

1 major / 0 minor

Summary. The paper claims that the Brick-Laying algorithm (greedy minimization of sum of squared loads) achieves majorization minimax-optimality [BDK26] for online allocation of bases of discrete polymatroids. As a consequence it simultaneously guarantees minimax-optimal competitive ratios and regret for every Schur-concave and Schur-convex objective, for any number of agents and resources, while remaining agnostic to problem scale. The argument departs from primal-dual methods and instead uses majorization comparisons together with conjugates of integer partitions to identify worst-case instances.

Significance. If the central claim holds, the result supplies a simple myopic algorithm with a strong, objective-free optimality guarantee in a general online polymatroid setting. The explicit link drawn between the geometry of partition conjugates and worst-case online equitable allocation constitutes a novel structural contribution.

major comments (1)
  1. [Abstract] Abstract: the claim that majorization minimax-optimality transfers directly to the online discrete-polymatroid setting is load-bearing for every subsequent guarantee, yet the abstract supplies neither a proof sketch nor any indication of how the online arrival order or the general independence structure of an arbitrary discrete polymatroid is incorporated into the majorization lattice or the conjugate-partition characterization. This leaves open whether additional structural assumptions (e.g., partition-matroid restrictions or total orders compatible with the greedy choice) are required.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback. We address the single major comment below and will revise the abstract accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the claim that majorization minimax-optimality transfers directly to the online discrete-polymatroid setting is load-bearing for every subsequent guarantee, yet the abstract supplies neither a proof sketch nor any indication of how the online arrival order or the general independence structure of an arbitrary discrete polymatroid is incorporated into the majorization lattice or the conjugate-partition characterization. This leaves open whether additional structural assumptions (e.g., partition-matroid restrictions or total orders compatible with the greedy choice) are required.

    Authors: The majorization minimax-optimality is established directly for arbitrary discrete polymatroids with no additional assumptions such as partition-matroid restrictions or compatible total orders. The proof proceeds via direct majorization comparisons between allocation vectors that exploit the exchange axioms of discrete polymatroid bases; these comparisons hold for the Brick-Laying greedy choice independently of any further structure. The online arrival order is incorporated by using conjugate partitions to characterize the extremal load vectors that arise under adversarial sequences, which apply to any polymatroid independence structure. We will revise the abstract to include one sentence indicating that the argument relies on majorization lattice comparisons together with conjugate-partition worst-case analysis. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation applies external optimality notion to new setting via independent analysis.

full rationale

The paper imports the majorization minimax-optimality definition from the external reference [BDK26] and demonstrates that the Brick-Laying algorithm achieves it in the online discrete polymatroid setting by leveraging conjugates of integer partitions to characterize worst-case instances. This constitutes an application and extension rather than a self-referential reduction. No quoted equations or steps exhibit self-definitional equivalence, fitted parameters renamed as predictions, or load-bearing self-citations that collapse the central claim to unverified prior work by the same authors. The approach is self-contained against the stated assumptions and provides new structural connections between partition geometry and allocation.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the external definition of majorization minimax-optimality from [BDK26] and on the modeling choice that feasible allocations are exactly the bases of discrete polymatroids arriving online. No free parameters or new invented entities appear in the abstract.

axioms (2)
  • domain assumption Allocations must be bases of discrete polymatroids that arrive online.
    This defines the feasible set and arrival model for the problem.
  • domain assumption Majorization minimax-optimality as defined in [BDK26] is the appropriate universal optimality notion.
    The paper adopts this prior notion without re-deriving it.

pith-pipeline@v0.9.1-grok · 5719 in / 1458 out tokens · 23135 ms · 2026-06-27T18:52:41.369649+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

45 extracted references · 2 canonical work pages

  1. [1]

    , title=

    Arnold, Barry C. , title=. 1987 , doi=

    1987

  2. [2]

    arXiv preprint arXiv:2511.08538 , year=

    Fair Multi-agent Persuasion with Submodular Constraints , author=. arXiv preprint arXiv:2511.08538 , year=

    arXiv

  3. [3]

    Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Online nash social welfare maximization with predictions , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

    2022

  4. [4]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Fair price discrimination , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  5. [5]

    Water-Filling is Universally Minimax Optimal , journal=

    Banerjee, Siddhartha and. Water-Filling is Universally Minimax Optimal , journal=. 2026 , doi=

    2026

  6. [6]

    ACM SIGMETRICS Performance Evaluation Review , volume=

    Using approximate majorization to characterize protocol fairness , author=. ACM SIGMETRICS Performance Evaluation Review , volume=. 2001 , publisher=

    2001

  7. [7]

    Acm Sigact News , volume=

    On-line bipartite matching made simple , author=. Acm Sigact News , volume=. 2008 , publisher=

    2008

  8. [8]

    Foundations and Trends

    The design of competitive online algorithms via a primal—Dual approach , author=. Foundations and Trends. 2009 , publisher=

    2009

  9. [9]

    ACM Transactions on Economics and Computation (TEAC) , volume=

    The unreasonable fairness of maximum Nash welfare , author=. ACM Transactions on Economics and Computation (TEAC) , volume=. 2019 , publisher=

    2019

  10. [10]

    Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages=

    Approximation algorithms for minimum norm and ordered optimization problems , author=. Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages=

  11. [11]

    arXiv preprint arXiv:2305.18861 , year=

    A general framework for learning-augmented online allocation , author=. arXiv preprint arXiv:2305.18861 , year=

    arXiv

  12. [12]

    Random Structures & Algorithms , volume=

    Disjoint bases in a polymatroid , author=. Random Structures & Algorithms , volume=. 2009 , publisher=

    2009

  13. [13]

    Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages=

    Online matching with concave returns , author=. Proceedings of the forty-fourth annual ACM symposium on Theory of computing , pages=

  14. [14]

    Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Randomized primal-dual analysis of ranking for online bipartite matching , author=. Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2013 , organization=

    2013

  15. [15]

    Symposium on Simplicity in Algorithms (SOSA) , pages=

    An Economics-Based Analysis of RANKING for Online Bipartite Matching , author=. Symposium on Simplicity in Algorithms (SOSA) , pages=. 2021 , organization=

    2021

  16. [16]

    Operations research , volume=

    The greedy procedure for resource allocation problems: Necessary and sufficient conditions for optimality , author=. Operations research , volume=. 1986 , publisher=

    1986

  17. [17]

    Building Bridges II: Mathematics of L

    Tighter bounds for online bipartite matching , author=. Building Bridges II: Mathematics of L. 2020 , publisher=

    2020

  18. [18]

    Management Science , volume=

    Batching and optimal multistage bipartite allocations , author=. Management Science , volume=. 2025 , publisher=

    2025

  19. [19]

    arXiv preprint arXiv:1808.08477 , year=

    Discrete decreasing minimization, Part II: Views from discrete convex analysis , author=. arXiv preprint arXiv:1808.08477 , year=

    arXiv

  20. [20]

    Mathematical Programming , volume=

    Decreasing minimization on M-convex sets: algorithms and applications , author=. Mathematical Programming , volume=. 2022 , publisher=

    2022

  21. [21]

    Mathematical Programming , volume=

    Decreasing minimization on M-convex sets: background and structures , author=. Mathematical Programming , volume=. 2022 , publisher=

    2022

  22. [22]

    2005 , publisher=

    Submodular functions and optimization , author=. 2005 , publisher=

    2005

  23. [23]

    , author=

    Zero-one matrices with zero trace. , author=. Pacific J. Math. , volume=

  24. [24]

    Classic Papers in Combinatorics , pages=

    A theorem on flows in networks , author=. Classic Papers in Combinatorics , pages=. 1957 , publisher=

    1957

  25. [25]

    ACM Transactions on Algorithms (TALG) , volume=

    Approximate majorization and fair online load balancing , author=. ACM Transactions on Algorithms (TALG) , volume=. 2005 , publisher=

    2005

  26. [26]

    Hardy, G. H. and Littlewood, J.E. and Pólya, G. , title=. 1988 , address=

    1988

  27. [27]

    Journal of Algorithms , volume=

    Semi-matchings for bipartite graphs and load balancing , author=. Journal of Algorithms , volume=. 2006 , publisher=

    2006

  28. [28]

    2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    The online submodular assignment problem , author=. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2024 , organization=

    2024

  29. [29]

    Journal of Algebraic Combinatorics , volume=

    Discrete polymatroids , author=. Journal of Algebraic Combinatorics , volume=. 2002 , publisher=

    2002

  30. [30]

    Journal of the ACM (JACM) , volume=

    A combinatorial strongly polynomial algorithm for minimizing submodular functions , author=. Journal of the ACM (JACM) , volume=. 2001 , publisher=

    2001

  31. [31]

    Theoretical Computer Science , volume=

    An optimal deterministic algorithm for online b-matching , author=. Theoretical Computer Science , volume=. 2000 , publisher=

    2000

  32. [32]

    Proceedings of the twenty-second annual ACM symposium on Theory of computing , pages=

    An optimal algorithm for on-line bipartite matching , author=. Proceedings of the twenty-second annual ACM symposium on Theory of computing , pages=

  33. [33]

    Online and Bandit Algorithms Beyond

    Kesselheim, Thomas and Molinaro, Marco and Singla, Sahil , booktitle=. Online and Bandit Algorithms Beyond. 2023 , organization=

    2023

  34. [34]

    40th Annual Symposium on Foundations of Computer Science (Cat

    Fairness in routing and load balancing , author=. 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039) , pages=. 1999 , organization=

    1999

  35. [35]

    focs , pages=

    Fairness measures for resource allocation , author=. focs , pages=

  36. [36]

    The American Mathematical Monthly , volume=

    Manfred Krause , title=. The American Mathematical Monthly , volume=. 1996 , publisher=. doi:10.1080/00029890.1996.12004747 , URL=

    work page doi:10.1080/00029890.1996.12004747 1996

  37. [37]

    and Olin, Ingram and Arnold, Barry C

    Marshall, Albert W. and Olin, Ingram and Arnold, Barry C. , title=

  38. [38]

    Mathematical Programming , volume=

    Optimal flows in networks with multiple sources and sinks , author=. Mathematical Programming , volume=. 1974 , publisher=

    1974

  39. [39]

    Journal of the ACM (JACM) , volume=

    Adwords and generalized online matching , author=. Journal of the ACM (JACM) , volume=. 2007 , publisher=

    2007

  40. [40]

    Foundations and Trends

    Online matching and ad allocation , author=. Foundations and Trends. 2010 , publisher=

    2010

  41. [41]

    Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Online Resource Allocation with Concave, Diminishing-Returns Objectives , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

    2026

  42. [42]

    Ryser, H. J. , year=. Combinatorial Properties of Matrices of Zeros and Ones , volume=. doi:10.4153/CJM-1957-044-3 , journal=

    work page doi:10.4153/cjm-1957-044-3 1957

  43. [43]

    Journal of Combinatorial Theory, Series B , volume=

    A combinatorial algorithm minimizing submodular functions in strongly polynomial time , author=. Journal of Combinatorial Theory, Series B , volume=. 2000 , publisher=

    2000

  44. [44]

    2002 , publisher=

    Combinatorial Optimization: Polyhedra and Efficiency , author=. 2002 , publisher=

    2002

  45. [45]

    International journal of game theory , volume=

    Cores of convex games , author=. International journal of game theory , volume=. 1971 , publisher=

    1971