Pith. sign in

REVIEW 4 minor 87 references

Online Fair Division with Budget Constraints

T0 review · 0 major / 4 minor · reviewed 2026-07-31 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read No deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness for budget-constrained online allocation, but bounding the spread of value-per-size ratios restores sharp guarantees.

desk verdict New online model for budgeted fair division, a strong impossibility theorem, and tight small-item frontiers; a few acknowledged open edges, but no load-bearing flaws. read the letter →

arxiv 2607.23310 v1 pith:OUY5D6SR submitted 2026-07-25 cs.GT cs.AIcs.LGcs.MAecon.TH

Saar Cohen , Nicholas Teh , Paul W. Goldberg , Michael J. Wooldridge This is my paper · ORCID
classification cs.GTcs.AIcs.LGcs.MAecon.TH MSC 68W2791B32
keywords onlinefairdivisionbudgetconstraintsfeasibleenvy-freenessdensityspreadresourceaugmentationlearning-augmentedalgorithmsgeneralizedassignmentcharity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Online fair division under budget constraints means goods arrive one at a time and must be assigned forever to an agent with enough remaining capacity or to charity. The paper proves that in full generality no deterministic algorithm can guarantee any fixed approximation to feasible envy-freeness, even with two symmetric agents. It then shows that a single structural parameter—the ratio of the highest to lowest value per unit of budget, called the density spread—is the pivot: bounded spread yields a (1/Γ)-FEF1 guarantee under a simple greedy rule. With common valuations and very small goods, the best achievable guarantee is exactly 1/(1+ln Γ), and this frontier shifts to min{1,(1+ε)/(1+ln Γ)} when the algorithm is given extra budget ε. A prediction-based algorithm using joint value-size type counts reproduces any offline fair allocation when predictions are perfect and degrades gracefully otherwise.

What carries the argument

The load-bearing object is the density spread Γ, the ratio of the largest to smallest value-per-unit-size among individually feasible, positively valued goods. Feasible envy-freeness up to k goods (FEF_k) compares each agent's bundle only with budget-feasible subsets of every recipient's bundle, including charity. The positive results run through two mechanisms: POSITIVE-GREEDYFIT, which assigns a positive-value good to a feasible agent with minimum current bundle value, and the threshold policy Threshold(α), which only assigns a good when the recipient's current value is below α times the good's density. The threshold policy's residual-capacity and balanced-acceptance invariants are what yi

What would settle it

Run any deterministic algorithm on the two-agent, common-valuation, common-size instance with density spread γ=2, unit budgets, and item size δ→0, and check whether it achieves α-FEF1 for some α>1/(1+ln 2)≈0.59; the frontier theorem predicts that for every such α there is a hard finite sequence, so a single counterexample would refute it.

Watch

Extended reading notes

Core claim

The paper's central claim is that irrevocable online allocation with budgets and charity makes feasible envy-freeness (FEF) intractable in the worst case, but the difficulty is governed by how much value-per-unit-budget varies across goods. It proves that no deterministic online algorithm can guarantee any fixed α-FEF_k for any k, even for two agents with equal unit budgets, common valuations, uniform item sizes, and a known horizon. It then establishes bounded density spread as the structural condition that restores tractability: a greedy min-value-fit algorithm is (1/Γ)-FEF1 under common valuations, and with common valuations, common sizes, and globally small goods a threshold policy attai

Load-bearing premise

The sharp optimal-frontier results assume that all agents measure every good's size identically and that goods become arbitrarily small; exact agent-to-agent FEF1 relies on every assigned good being feasible for every agent, which the paper acknowledges may fail with agent-specific sizes and leaves open.

Editorial extensions

If this is right

  • If the impossibility theorem is right, meaningful online fairness under budgets requires extra structure: bounded density spread, extra capacity, or predictions.
  • Under common valuations, the simple min-value greedy algorithm guarantees (1/Γ)-FEF1 with arbitrary item sizes, so a moderate bound on value-per-size variation already buys a fairness guarantee.
  • Giving the online algorithm larger budgets improves the guarantee: with augmentation ε≥Γ−1 the same greedy rule becomes exactly FEF1.
  • In the small-good common-valuation/common-size model, the optimal deterministic approximation factor is 1/(1+ln Γ) in the limit, and any ε>ln Γ yields exact FEF1 for sufficiently small goods.
  • Predicting joint value-size types is both sufficient and, in a precise sense, necessary: predictions of value and size marginals alone cannot guarantee exact FEF_k.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: the density-spread bound could be enforced in practice by pre-filtering or normalizing goods by value density, turning a fairness impossibility into an approximation that depends on how much preprocessing one is willing to do.
  • Editorial extension: the additive degradation result suggests an implementable design—run any offline fair-allocation solver on a predicted type multiset, then reserve capacity online; the fairness loss is at most the value-weighted prediction error, which is measurable in deployment.
  • Editorial extension: the threshold result predicts a sharp phase transition: for small goods with common valuations, extra budget beyond ln Γ buys exact fairness, while below it no algorithm can do better than 1/(1+ln Γ). This is testable on real arrival sequences.
  • Editorial extension: the impossibility of using value and size marginals separately implies that data-collection pipelines for online fair division should record joint value-size profiles, not aggregate statistics.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper introduces an online model of fair division under generalized assignment budget constraints. Goods arrive sequentially; each is irrevocably assigned to an agent with enough remaining budget or to charity, and fairness is evaluated against budget-feasible subsets of recipients' bundles. The paper proves a sweeping impossibility (Theorem 4.1): no deterministic online algorithm can guarantee any fixed multiplicative α-FEFk, even for two agents, equal unit budgets, common valuations, uniform item sizes, and a known horizon. It then shows that bounded density spread restores tractability: greedy algorithms achieve Γ^{-1}-FEF1 (common/scaled-common valuations) and Λ^{-1}-FEF1 (heterogeneous valuations). A resource-augmentation variant yields min{1,(1+ε)/Γ}-FEF1. Under common valuations, common sizes, and small goods, a threshold policy attains a sharp limiting frontier min{1,(1+ε)/(1+lnγ)} with matching lower bounds. A learning-augmented framework with joint value-size type predictions achieves consistency, additive robustness to prediction error, and lower bounds showing the necessity of joint predictions. All proofs are in appendices.

Significance. If correct, this is a significant contribution to online fair division. The impossibility result is clean and strong, isolating budget-feasible charity comparisons as the source of hardness. The positive guarantees are expressed directly in terms of input parameters (Γ, γ, ε, Λ, Δ), not fitted constants. I checked the phase construction behind Theorem 4.1 and the deterministic simulation-to-fixed-sequence argument; the suspected circularity concern does not land. The small-good frontier is carefully presented as a limiting result with boundary cases open and acknowledged. The only substantive limitation is that the frontier upper bound requires sizes common across agents; the paper explicitly acknowledges this and leaves agent-specific sizes open. This does not affect the central impossibility, whose hard instances use uniform sizes.

minor comments (4)
  1. [Abstract and Section 1] The abstract and the contribution bullet state that the optimal frontier holds "under common valuations and sufficiently small goods"; the frontier theorems (E.6, E.7) additionally require sizes common across agents, and the paper itself leaves agent-specific sizes open. Please state the common-size assumption in the abstract to avoid overstating the scope.
  2. [Theorem E.6(a)] The statement appears to include the endpoint α=1/(1+lnγ) in a closed interval, but the proof defines σ0=(1-α(1+lnγ))/(2+γ), which is positive only for strict inequality. The interval should be open; this is consistent with the surrounding text that boundary attainment is not claimed.
  3. [Section 6 / contributions] The bullet says the resource-augmentation results "establish matching lower bounds" for arbitrary item sizes. The matching limiting lower bound in Appendix E is derived under common sizes and small goods; for arbitrary sizes, Theorems 6.1 and 6.2 / Appendix G leave a gap. I suggest rewording to "quantify the improvement and provide lower bounds".
  4. [Theorem 7.5] The sentence "The result continues to hold if the total value and maximum item value are also provided" is redundant when the exact value multiset is already given. If the intent is to consider weaker aggregate advice, please clarify; otherwise delete.

Circularity Check

1 steps flagged · score 1.0 of 10

No significant circularity: core impossibility and greedy guarantees are self-contained; only minor self-citations in related work are not load-bearing.

  1. other [Appendix E, closing paragraphs after Theorem E.7]
    "The frontier theorems above rely critically on the assumption that item sizes are common across agents. ... However, the exact agent–agent FEF1 argument does not extend directly. ... Consequently, Theorems E.6 and E.7 establish the limiting frontiers only for the model with sizes common across agents. ... the corresponding upper bound for fully agent-specific sizes remains open."

    This is not a circular step but a self-acknowledged limitation: the appendix states that its agent–agent exact-FEF1 bound relies on Lemma E.3's common-size feasibility assumption and that the agent-specific-size upper bound is not derived. This is an explicit open-problem statement, which the reviewing rules require to be flagged, and it is weighed in the verdict. It does not make the central Theorem 4.1 circular because the hard instances for that theorem use uniform sizes, so the acknowledged gap does not reduce any derived result to its own input by construction.

full rationale

I examined the main derivation chain and found no step that reduces a claimed result to its own assumptions. (1) Theorem 4.1's lower bound is an internal phase construction: goods of size 1/Q with budget 1 force at least Q charity goods per phase; if an agent receives fewer than tau=floor(alpha(Q-k)/4) phase-t goods, the three-term value bound v(A_i) < 3*alpha(Q-k)/4*V_t < alpha(Q-k)*V_t follows from inequalities (4) and (5) and the definition of tau, while v(S\X) >= (Q-k)V_t for every X with |X|<=k; if no phase fails, L*tau > Q contradicts capacity. The deterministic fixed-sequence argument is standard and preserves the announced horizon. Nothing in this proof is fitted, predicted from data, or defined in terms of the target guarantee. (2) The greedy guarantees (Theorems 5.1, 5.2, 6.1) express approximation factors in terms of input-parameter density spread Gamma or cross-comparability Lambda; these are parameters of the instance, not constants fitted to the fairness outcome, so quoting a bound in terms of Gamma is not circular — it is a standard worst-case guarantee. (3) The learning-augmented consistency result (Theorem 7.2) inherits whatever offline guarantee the planner has; this is explicitly a lifting statement, not a derivation of the offline guarantee from nothing, and it is not presented as a new first-principles result. (4) The paper cites several works by the same author group (e.g., [54] for online EF1, [19, 53] for related online fairness), but Theorem 4.1 explicitly contrasts with [54] and does not rely on any self-cited theorem for its proof; the related-work self-citations are contextual, not load-bearing. (5) The one genuine limitation — the Appendix E frontier for agent-specific item sizes is left open after Lemma E.3 — is explicitly acknowledged in the text and does not undermine the central impossibility, whose hard instances use uniform sizes. Under the review rule that manuscript-stated limitations must be flagged, I record that passage in steps, but it is an honest open-problem statement rather than a circular reduction. Therefore the appropriate score is 1, reflecting only minor self-citation presence with no central content depending on it.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No numbers are fitted to data; the parameters α, ε, γ, Γ, Λ are input or instance parameters. The paper introduces no new physical or mathematical entities beyond the model's standard 'charity' recipient. All axioms are explicit model assumptions.

assumptions (4)
  • domain assumption Each good's value and size profile is fully observed at arrival and decisions are irrevocable.
    Core online model, Section 3.
  • domain assumption Valuations and sizes are additive; charity has no budget and holds all unallocated goods.
    Model definitions in Section 3, inherited from offline budgeted fair division.
  • domain assumption For fully heterogeneous valuations, agents' numerical values are directly comparable across agents.
    Explicit assumption in Section 5.2 before Theorem 5.2; if not true, the Λ^{-1}-FEF1 guarantee fails.
  • domain assumption An offline planner exists that returns a feasible allocation with the desired fairness guarantee on the predicted multiset.
    Learning-augmented framework Section 7.1 relies on the existence of e.g. the Barman et al. FEFx planner.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Fair Division with Budget Constraints." pith.science (2026). https://pith.science/paper/OUY5D6SR

@misc{pith2026260723310,
  author       = {Pith},
  title        = {Pith review of: Online Fair Division with Budget Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OUY5D6SR}},
  note         = {Machine review of arXiv:2607.23310}
}
read the original abstract

We study an online variant of discrete fair division under generalized assignment budget constraints. Goods arrive one at a time and must be assigned irrevocably to a feasible agent or to charity, which holds all unallocated goods, while fairness is evaluated only against budget-feasible subsets of every recipient's bundle. We first show that, without additional structure, no deterministic online algorithm can guarantee any fixed approximation to feasible envy-freeness, even in highly symmetric instances. We then identify bounded density spread as a structural condition that restores meaningful guarantees, obtaining approximation algorithms for arbitrary item sizes and showing that, under common valuations and sufficiently small goods, these guarantees can be strengthened to an optimal deterministic frontier. We further study resource augmentation, where the online algorithm is allowed slightly larger budgets than the fairness benchmark, and characterize the resulting improvement in the achievable guarantees. Finally, we develop a learning-augmented framework based on predicting joint value-size types, proving consistency under perfect predictions, robustness to prediction error, and showing that separate predictions of value and size marginals are insufficient to recover strong fairness guarantees.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

87 extracted references · 2 linked inside Pith

  1. [1]

    Online fair division: A survey

    Martin Aleksandrov and Toby Walsh. Online fair division: A survey . InProceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 13557–13562, 2020

    2020

  2. [2]

    Online fair division: Analysing a food bank problem

    Martin Damyanov Aleksandrov, Haris Aziz, Serge Gaspers, and Toby Walsh. Online fair division: Analysing a food bank problem. InProceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI), pages 2540–2546, 2015

    2015

  3. [3]

    Better collective decisions via uncertainty reduction

    Shiri Alouf-Heffetz, Laurent Bulteau, Edith Elkind, Nimrod Talmon, and Nicholas Teh. Better collective decisions via uncertainty reduction. InProceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 24–30, 2022

    2022

  4. [4]

    Online fair division for personalized 2-value instances

    Georgios Amanatidis, Alexandros Lolos, Evangelos Markakis, and Victor Turmel. Online fair division for personalized 2-value instances. InProceedings of the 18th International Symposium on Algorithmic Game Theory (SAGT), pages 209–227, 2025

    2025

  5. [5]

    Online fair division meets reordering buffers.arXiv preprint, arXiv:2607.01159, 2026

    Georgios Amanatidis, Giulio Giaconi, Evangelos Markakis, and Nicos Protopapas. Online fair division meets reordering buffers.arXiv preprint, arXiv:2607.01159, 2026

    arXiv 2026

  6. [6]

    Best of many in both worlds: Online resource allocation with predictions under unknown arrival model.arXiv preprint arXiv:2402.13530, 2024

    Lin An, Andrew A Li, Benjamin Moseley , and Gabriel Visotsky . Best of many in both worlds: Online resource allocation with predictions under unknown arrival model.arXiv preprint arXiv:2402.13530, 2024

    arXiv 2024

  7. [7]

    Strategyproof scheduling with predictions

    Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. Strategyproof scheduling with predictions. InProceed- ings of the 14th Innovations in Theoretical Computer Science Conference (ITCS), page 11, 2023

    2023

  8. [8]

    Online nash social welfare maxi- mization with predictions

    Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maxi- mization with predictions. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algo- rithms (SODA), pages 1–19. SIAM, 2022

    2022

Show all 87 references
  1. [9]

    Universal and tight online algorithms for generalized-mean welfare

    Siddharth Barman, Arindam Khan, and Arnab Maiti. Universal and tight online algorithms for generalized-mean welfare. InProceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 4793–4800, 2022

    2022

  2. [10]

    Guaranteeing envy-freeness under generalized assignment constraints

    Siddharth Barman, Arindam Khan, Sudarshan Shyam, and KVN Sreenivas. Guaranteeing envy-freeness under generalized assignment constraints. InProceedings of the 24th ACM Conference on Economics and Computation (EC), pages 242–269, 2023

    2023

  3. [11]

    How to make envy vanish over time

    Gerdus Benade, Aleksandr M Kazachkov, Ariel D Procaccia, and Christos-Alexandros Psomas. How to make envy vanish over time. InProceedings of the 19th ACM Conference on Economics and Computation (EC), pages 593–610, 2018

    2018

  4. [12]

    Kazachkov, Ariel D

    Gerdus Benadè, Aleksandr M. Kazachkov, Ariel D. Procaccia, Alexandros Psomas, and David Zeng. Fair and efficient online allocations.Operations Research, 72(4):1438–1452, 2024

    2024

  5. [13]

    Dynamic fair division with partial informa- tion.Operations Research, 73(4):1876–1896, 2025

    Gerdus Benadè, Daniel Halpern, and Alexandros Psomas. Dynamic fair division with partial informa- tion.Operations Research, 73(4):1876–1896, 2025

    2025

  6. [14]

    The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy, 119(6):1061–1103, 2011

    Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes.Journal of Political Economy, 119(6):1061–1103, 2011

    2011

  7. [15]

    Repeatedly matching items to agents fairly and efficiently

    Ioannis Caragiannis and Shivika Narang. Repeatedly matching items to agents fairly and efficiently . In Proceedings of the 16th International Symposium on Algorithmic Game Theory (SAGT), pages 347–364, 2023

    2023

  8. [16]

    Envy-freeness up to any item with high nash welfare: The virtue of donating items

    Ioannis Caragiannis, Nick Gravin, and Xin Huang. Envy-freeness up to any item with high nash welfare: The virtue of donating items. InProceedings of the 20th ACM Conference on Economics and Computation (EC), pages 527–545, 2019. 11

    2019

  9. [17]

    The unreasonable fairness of maximum nash welfare.ACM Transactions on Economics and Computation, 7(3):1–32, 2019

    Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare.ACM Transactions on Economics and Computation, 7(3):1–32, 2019

    2019

  10. [18]

    A little charity guarantees almost envy-freeness.SIAM Journal on Computing, 50(4):1336–1358, 2021

    Bhaskar Ray Chaudhury , Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. A little charity guarantees almost envy-freeness.SIAM Journal on Computing, 50(4):1336–1358, 2021

    2021

  11. [19]

    Approximate proportionality in online fair division

    Davin Choo, Winston Fu, Derek Khu, Tzeh Yuan Neoh, Tze-Yang Poon, and Nicholas Teh. Approximate proportionality in online fair division. InProceedings of the 43rd International Conference on Machine Learning (ICML), 2026

    2026

  12. [20]

    Plant-and-steal: Truthful fair allocations via predictions

    Ilan R Cohen, Alon Eden, Talya Eden, and Arsen Vasilyan. Plant-and-steal: Truthful fair allocations via predictions. InProceedings of the 38th International Conference on Neural Information Processing Systems (NeurIPS), pages 110057–110096, 2024

    2024

  13. [21]

    A general framework for learning-augmented online allo- cation

    Ilan Reuven Cohen and Debmalya Panigrahi. A general framework for learning-augmented online allo- cation. InProceedings of the 50th International Colloquium on Automata, Languages, and Programming (ICALP), pages 43:1–43:21, 2023

    2023

  14. [22]

    Delayed assignments in online non-centroid clustering with stochastic arrivals

    Saar Cohen. Delayed assignments in online non-centroid clustering with stochastic arrivals. InPro- ceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1091–1100, 2026

    2026

  15. [23]

    Online coalitional skill formation

    Saar Cohen and Noa Agmon. Online coalitional skill formation. InProceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 494–503, 2023

    2023

  16. [24]

    Online learning of partitions in additively separable hedonic games

    Saar Cohen and Noa Agmon. Online learning of partitions in additively separable hedonic games. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), pages 2722–2730, 2024

    2024

  17. [25]

    Online friends partitioning under uncertainty

    Saar Cohen and Noa Agmon. Online friends partitioning under uncertainty . InProceedings of the 27th European Conference on Artificial Intelligence (ECAI), pages 3332–3339. IOS Press, 2024

    2024

  18. [26]

    Decentralized online learning by selfish agents in coalition formation

    Saar Cohen and Noa Agmon. Decentralized online learning by selfish agents in coalition formation. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI), 2025

    2025

  19. [27]

    Online learning of fair coalition structures

    Saar Cohen and Noa Agmon. Online learning of fair coalition structures. InProceedings of the 28th European Conference on Artificial Intelligence (ECAI), pages 4937–4944, 2025

    2025

  20. [28]

    Online learning of coalition structures by selfish agents

    Saar Cohen and Noa Agmon. Online learning of coalition structures by selfish agents. InProceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 13709–13717, 2025

    2025

  21. [29]

    Temporal fair division

    Benjamin Cookson, Soroush Ebadian, and Nisarg Shah. Temporal fair division. InProceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 13727–13734, 2025

    2025

  22. [30]

    Fairness in temporal slot assignment

    Edith Elkind, Sonja Kraiczy , and Nicholas Teh. Fairness in temporal slot assignment. InProceedings of the 15th International Symposium on Algorithmic Game Theory (SAGT), pages 490–507, 2022

    2022

  23. [31]

    Fair division of chores with budget constraints

    Edith Elkind, Ayumi Igarashi, and Nicholas Teh. Fair division of chores with budget constraints. In Proceedings of the 17th International Symposium on Algorithmic Game Theory (SAGT), pages 55–71, 2024

    2024

  24. [32]

    Temporal elections: Welfare, strategyproofness, and proportionality

    Edith Elkind, Tzeh Yuan Neoh, and Nicholas Teh. Temporal elections: Welfare, strategyproofness, and proportionality . InProceedings of the 27th European Conference on Artificial Intelligence (ECAI), pages 3292–3299, 2024

    2024

  25. [33]

    Temporal fairness in multiwinner voting

    Edith Elkind, Svetlana Obraztsova, and Nicholas Teh. Temporal fairness in multiwinner voting. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 22633–22640, 2024. 12

    2024

  26. [34]

    Temporal fair division of indivisible items

    Edith Elkind, Alexander Lam, Mohamad Latifian, Tzeh Yuan Neoh, and Nicholas Teh. Temporal fair division of indivisible items. InProceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 676–685, 2025

    2025

  27. [35]

    Not in my backyard! temporal voting over public chores

    Edith Elkind, Tzeh Yuan Neoh, and Nicholas Teh. Not in my backyard! temporal voting over public chores. InProceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI), pages 3814–3820, 2025

    2025

  28. [36]

    Verifying proportionality in tem- poral voting

    Edith Elkind, Svetlana Obraztsova, Jannik Peters, and Nicholas Teh. Verifying proportionality in tem- poral voting. InProceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 13805– 13813, 2025

    2025

  29. [37]

    Online ad assignment with free disposal

    Jon Feldman, Nitish Korula, Vahab Mirrokni, Shanmugavelayutham Muthukrishnan, and Martin Pál. Online ad assignment with free disposal. InProceedings of the 5th International Workshop on Internet and Network Economics (WINE), pages 374–385. Springer, 2009

    2009

  30. [38]

    Dynamic fair division with minimal disrup- tions

    Eric Friedman, Christos-Alexandros Psomas, and Shai Vardi. Dynamic fair division with minimal disrup- tions. InProceedings of the 16th ACM conference on Economics and Computation (EC), pages 697–713, 2015

    2015

  31. [39]

    Approximation algorithm for computing budget-feasible ef1 alloca- tions

    Jiarui Gan, Bo Li, and Xiaowei Wu. Approximation algorithm for computing budget-feasible ef1 alloca- tions. InProceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 170–178, 2023

    2023

  32. [40]

    Minimizing cumulative envy in allocating a sequence of items

    Paul Goldberg, Isaac Robinson, and Nicholas Teh. Minimizing cumulative envy in allocating a sequence of items. InProceedings of the 19th International Symposium on Algorithmic Game Theory (SAGT), 2026

    2026

  33. [41]

    Achieving a fairer future by changing the past

    Jiafan He, Ariel D Procaccia, Alexandros Psomas, and David Zeng. Achieving a fairer future by changing the past. InProceedings of the 28th International Joint Conference on Artificial Intelligence, pages 343– 349, 2019

    2019

  34. [42]

    How to match when all vertices arrive online

    Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. How to match when all vertices arrive online. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 17–29, 2018

    2018

  35. [43]

    The long arm of Nashian allocation in onlinep-mean welfare maximization

    Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang. The long arm of Nashian allocation in onlinep-mean welfare maximization. InProceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 98:1–98:18, 2025

    2025

  36. [44]

    Speed is as powerful as clairvoyance.Journal of the ACM, 47 (4):617–643, 2000

    Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance.Journal of the ACM, 47 (4):617–643, 2000

    2000

  37. [45]

    An optimal algorithm for on-line bipartite matching

    Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. InProceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), pages 352–358, 1990

    1990

  38. [46]

    Dynamic fair division problem with general valuations

    Bo Li, Wenyang Li, and Yingkai Li. Dynamic fair division problem with general valuations. InProceed- ings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 375–381, 2018

    2018

  39. [47]

    Fairness in repeated matching: A maximin perspective

    Eugene Lim, Tzeh Yuan Neoh, and Nicholas Teh. Fairness in repeated matching: A maximin perspective. InProceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), pages 17111–17119, 2026

    2026

  40. [48]

    On approximately fair allocations of indivisible goods

    Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On approximately fair allocations of indivisible goods. InProceedings of the 5th ACM Conference on Electronic Commerce (EC), pages 125–131, 2004

    2004

  41. [49]

    Competitive caching with machine learned advice.Journal of the ACM, 68(4):1–25, 2021

    Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice.Journal of the ACM, 68(4):1–25, 2021. 13

    2021

  42. [50]

    John Wiley & Sons, Inc., 1990

    Silvano Martello and Paolo Toth.Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., 1990

    1990

  43. [51]

    Adwords and generalized online matching.Journal of the ACM, 54(5):22–es, 2007

    Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching.Journal of the ACM, 54(5):22–es, 2007

    2007

  44. [52]

    Cambridge University Press, 2021

    Michael Mitzenmacher and Sergei Vassilvitskii.Algorithms with Predictions, page 646–662. Cambridge University Press, 2021

    2021

  45. [53]

    Understanding efx allocations: Counting and variants

    Tzeh Yuan Neoh and Nicholas Teh. Understanding efx allocations: Counting and variants. InProceed- ings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 14036–14044, 2025

    2025

  46. [54]

    Online fair division with additional information

    Tzeh Yuan Neoh, Jannik Peters, and Nicholas Teh. Online fair division with additional information. In Proceedings of the 43rd International Conference on Machine Learning (ICML), 2026

    2026

  47. [55]

    Strengthening proportionality in tem- poral voting

    Bradley Phillips, Edith Elkind, Nicholas Teh, and Tomasz W˛ as. Strengthening proportionality in tem- poral voting. InProceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 3823–3832, 2026

    2026

  48. [56]

    Improving online algorithms via ml predictions

    Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (NeurIPS), 2018

    2018

  49. [57]

    Cambridge University Press, 2021

    Tim Roughgarden.Beyond the worst-case analysis of algorithms. Cambridge University Press, 2021

    2021

  50. [58]

    Online ad allocation with predictions

    Fabian Spaeh and Alina Ene. Online ad allocation with predictions. InProceedings of the 37th Interna- tional Conference on Neural Information Processing Systems (NeurIPS), pages 17265–17295, 2023

    2023

  51. [59]

    Online al- gorithms for the Santa Claus problem

    Max Springer, MohammadTaghi Hajiaghayi, Debmalya Panigrahi, and Mohammad Khani. Online al- gorithms for the Santa Claus problem. InProceedings of the 36th International Conference on Neural Information Processing Systems (NeurIPS), pages 30732–30743, 2022

    2022

  52. [60]

    Constraints in fair division.ACM SIGecom Exchanges, 19(2):46–61, 2021

    Warut Suksompong. Constraints in fair division.ACM SIGecom Exchanges, 19(2):46–61, 2021

    2021

  53. [61]

    The price of proportional representation in temporal voting.Proceedings of the 35th International Joint Conference on Artificial Intelligence (IJCAI), 2026

    Nicholas Teh. The price of proportional representation in temporal voting.Proceedings of the 35th International Joint Conference on Artificial Intelligence (IJCAI), 2026

    2026

  54. [62]

    Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm

    Yajun Wang and Sam Chiu-wai Wong. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. InProceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 1070–1081. Springer, 2015

    2015

  55. [63]

    Online fair allocations with binary valuations and beyond

    Yuanyuan Wang and Tianze Wei. Online fair allocations with binary valuations and beyond. InPro- ceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), pages 17267–17275, 2026

    2026

  56. [64]

    Budget-feasible maximum nash social welfare is almost envy-free

    Xiaowei Wu, Bo Li, and Jiarui Gan. Budget-feasible maximum nash social welfare is almost envy-free. InProceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), pages 465–471, 2021

    2021

  57. [65]

    Multiwinner temporal voting with aversion to change

    Valentin Zech, Niclas Boehmer, Edith Elkind, and Nicholas Teh. Multiwinner temporal voting with aversion to change. InProceedings of the 27th European Conference on Artificial Intelligence (ECAI), pages 3236–3243, 2024

    2024

  58. [66]

    Fairness-efficiency tradeoffs in dynamic fair division

    David Zeng and Alexandros Psomas. Fairness-efficiency tradeoffs in dynamic fair division. InProceed- ings of the 21st ACM Conference on Economics and Computation (EC), pages 911–912, 2020

    2020

  59. [67]

    Multi-agent online scheduling: Mms allocations for indivisible items

    Shengwei Zhou, Rufan Bai, and Xiaowei Wu. Multi-agent online scheduling: Mms allocations for indivisible items. InProceedings of the 40th International Conference on Machine Learning (ICML), pages 42506–42516, 2023

    2023

  60. [68]

    Yunhong Zhou, Deeparnab Chakrabarty , and Rajan M. Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. InProceedings of the 17th International Conference on World Wide Web (WWW), pages 1243–1244, 2008. 14 A Additional Related Work A.1 Online Fa...

    2008

  61. [69]

    Our learning-augmented framework differs fundamentally from these approaches

    investigated semi-online allocation of indivisible goods and chores under additive and submodular val- uations, obtaining fairness and efficiency guarantees in a substantially weaker adversarial model than the fully adaptive setting considered here. Our learning-augmented fram...

  62. [70]

    valuations are common, sov i =vfor every agenti

  63. [71]

    sizes are common across agents, sos i =sfor every agenti

  64. [72]

    every original budget equals1; and

  65. [73]

    The algorithm is told the valid boundγ

    the realized density spread satisfiesΓ≤γaccording to Definition 3.2. The algorithm is told the valid boundγ. The horizon model is stated separately in each theorem. Throughout this appendix,Γdenotes the realized density spread of the instance, whereasγdenotes the valid upper b...

  66. [74]

    there arenagents with original unit budgets

  67. [75]

    valuations are common

  68. [76]

    every good has the same sizeδ≤σ max

  69. [77]

    the realized positive-density spread is exactlyγ; 27

  70. [78]

    The statement holds both when the horizon is announced before the first arrival and when it is not announced

    the final allocation is notα-FEF1. The statement holds both when the horizon is announced before the first arrival and when it is not announced. Proof.ForM≥1, defineS M :=M 1−γ −1/M . SinceS M →lnγ, first chooseMand then choose an integerQsufficiently large that, withδ:= 1 Q, ...

  71. [79]

    release the initial goodq

  72. [80]

    release all level goods through the end of levelj ∗

  73. [81]

    ifs i(g)≤ εBi for alli, g, then AUG-GREEDYFIT(ε)is exactly FEF1

    release exactly(M−j ∗)Pzero-value goods, each having common sizeδ. This sequence has exactly 1 + (j∗ + 1)P+ (M−j ∗)P= 1 + (M+ 1)P=T arrivals. In the known-horizon model, the master simulation and the actual execution have the same an- nounced horizon and the same arrival prefi...

  74. [82]

    the exact minimum positive density ρmin := min{ρ(g) :v(g)>0, s(g)≤1}

  75. [83]

    The valueρ min is supplied in the original numerical scale of the instance

    a valid upper boundγ≥1on the ratio of maximum to minimum positive density among individually feasible goods, as in Definition 3.2. The valueρ min is supplied in the original numerical scale of the instance. No additional information is provided: in particular, the algorithm is...

  76. [84]

    every good has size at mostσ max

  77. [85]

    the minimum and maximum positive densities are exactlyρ min andρ max, respectively

  78. [86]

    the realized density spread is exactlyγ; and

  79. [87]

    Proof.We reduce the claimed lower bound to the frontier lower bound of Theorem E.4 by scaling every value by the advised minimum density

    the algorithm doesnotproduce anα-FEF1 allocation. Proof.We reduce the claimed lower bound to the frontier lower bound of Theorem E.4 by scaling every value by the advised minimum density . Fix a deterministic online algorithmAreceiving the advice(ρ min, γ). We define a determi...

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.