Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

Online Fair Division with Additional Information

T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper proves that frequency predictions—the multiset of each agent's future values, without order—let online fair division match offline share-based fairness guarantees exactly, and that normalization information alone yields EF1 for…

desk verdict A careful, genuinely new map of what future information buys in online fair division; the main theorems hold up, including the EFX impossibility that the stress-test flagged. read the letter →

arxiv 2505.24503 v3 pith:QCOGUP2D submitted 2025-05-30 cs.GT cs.AI

Tzeh Yuan Neoh , Jannik Peters , Nicholas Teh This is my paper
classification cs.GTcs.AI MSC 68W2791B32
keywords onlinefairdivisionfrequencypredictionsnormalizationinformationenvy-freenessuptoonegoodmaximinsharefairnesslearning-augmentedalgorithmsshare-based
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

The paper asks how much information about the future is needed to allocate indivisible goods fairly when goods arrive one by one and must be assigned irrevocably. It shows that with no information, no positive approximation to EF1 is possible and PROP1 cannot be guaranteed on long streams. With normalization information—only each agent's total value—it provides an algorithm that is EF1 for two agents and PROP1 for any number of agents, and proves matching impossibilities for stronger notions. Its main positive result is that with frequency predictions, the multiset of values each agent will see but not the order, any share-based fairness notion achievable offline becomes achievable online, matching the best-known offline approximation, including $(3/4+3/3836)$-MMS for any number of agents.

What carries the argument

The machinery is a meta-algorithm built on picking sequences and identically-ordered (IDO) valuations. Given each agent's frequency multiset $V_i$, it sorts the values in decreasing order and attaches them to future goods in that fixed order, producing a single-shot IDO instance; any offline share-feasible allocation on that instance defines a picking sequence. Online, Algorithm 2 simulates the picking sequence on the remaining goods, allocating each arriving good to the agent who would have picked it, and the proof lemma shows each agent's realized value is at least the value she would get in the offline IDO allocation. For normalization information, Algorithm 1 instead maintains a certificate $x_i = v_i(A_i) + \frac{n-1}{n}\max\{M_i, v_i(g)\}$ that tracks whether one outside good added to the current bundle reaches $1/n$, which is what makes EF1 witnessable for two agents and PROP1 witnessable for all $n$.

What would settle it

Test the noisy guarantee by fixing a predicted multiset at 1-Wasserstein distance $\delta$ from the true multiset and applying the nearest-unused-value instantiation rule on a stream designed so that every realized value is matched to a predicted value $\delta$ away per step; if the cumulative error $\eta_i$ exceeds any constant times $\delta \cdot m$ while $s(\hat{V}_i,n)$ stays fixed, the $(1-\varepsilon_i)$ guarantee in Theorem 5.7 cannot be written as a function of prediction distance alone.

Watch

Extended reading notes

Core claim

The central claim is Theorem 5.1: for any share-based fairness notion $s$ that is feasible in the single-shot setting, there is an online algorithm using frequency predictions that gives every agent $i$ a bundle worth at least $s(V_i,n)$. The proof is constructive: from the predicted multisets it builds an identically-ordered valuation profile, takes any offline allocation that meets the share on that profile, reads off the picking sequence that produces it, and then runs Algorithm 2 online, where each arriving good goes to the agent who would pick it in the simulated sequence. A domination lemma shows each agent's realized value is at least her value in the offline allocation, so the share guarantee transfers. This yields the best-known offline MMS ratio, EFX for two agents, and more, while impossibilities limit further progress for EFX with three or more agents.

Load-bearing premise

The result that frequency predictions match offline guarantees assumes the predicted multisets are exactly the true multisets and the horizon $m$ is known; with noisy predictions the advertised guarantee is expressed through the algorithm's own instantiation error, and the paper does not bound that error by a natural distance between predicted and true multisets.

Editorial extensions

If this is right

  • Frequency predictions turn online fair division into offline fair division for every share-based axiom: round-robin share, minimum EFX share, and the current best MMS approximation all transfer unchanged.
  • With normalization information alone, the paper's Algorithm 1 reaches the exact boundary: EF1 for two agents and PROP1 for all $n$ are achievable, while no positive EFX (even $n=2$) and no positive EF1 ($n\ge 3$) can be guaranteed.
  • Without any information, only negative results hold: no positive EF1 approximation for $n\ge 2$, and PROP1 is violated on sufficiently long streams.
  • Under noisy advice the guarantees degrade gracefully: normalization error causes additive EF1 loss for $n=2$ and a multiplicative $\kappa$-PROP1 loss for all $n$; frequency error multiply degrades the share by $(1-\varepsilon_i)$.
  • For identical valuations, EF1 is achievable with no information, and with normalization the $0.618$-EFX approximation is exactly tight for two agents, while zero-competitive EFX remains for $n\ge 3$.

Reading between the lines

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

  • The open instantiation-rule question in Section 5.1 is the hinge for practice: if a future result bounds $\eta_i$ by a constant times the 1-Wasserstein distance between predicted and true multisets, then Theorem 5.7 becomes a genuine prediction-robustness guarantee rather than a certificate defined by the algorithm's own matching choices.
  • The paper's dichotomy suggests a general principle: for share-based fairness the order of arrivals is informationally irrelevant once the multiset is known, whereas envy-based notions like EF1 for $n\ge 3$ may need additional structure such as identical valuations or type-specific arrivals.
  • Because frequency predictions can be obtained by forecasting type counts when goods fall into types, the model is directly testable in applications like ad impressions or compute slots where category-level demand forecasts are standard.
  • The conjectured impossibility of EF1 for $n\ge 3$ with frequency predictions, if settled positively, would show that even perfect distributional information cannot overcome the need for order information in envy-based guarantees.
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

2 major / 4 minor

Summary. The paper studies online fair division of indivisible goods under an adaptive adversary and ex post guarantees, comparing three information models: no future information, normalization information (each agent's total value), and frequency predictions (each agent's value multiset without order). It proves that without information no deterministic online algorithm can guarantee a positive approximation of EF1, and PROP1 is impossible on sufficiently long streams. With normalization information, Algorithm 1 is shown to return EF1 allocations for two agents and PROP1 allocations for any number of agents, complemented by impossibilities for positive EFX (n≥2) and positive EF1 (n≥3), plus noisy-total robustness guarantees. With frequency predictions, a meta-algorithm (Theorem 5.1) is proposed that lifts any feasible single-shot share-based guarantee to the online setting, yielding the best-known offline MMS approximation, EFX for two agents, and an impossibility result for positive EFX when n≥3. The identical-valuations section adds an EF1 algorithm without information, a positive-EFX impossibility without information, a tight golden-ratio EFX algorithm for two agents with normalization, and a positive-EFX impossibility for n≥3 with normalization.

Significance. If correct, the frequency-prediction meta-algorithm is a substantial contribution: it shows that unordered multiset information is sufficient to transfer a broad class of offline share guarantees, including the current best MMS approximation, to an online setting with adversarially ordered arrivals. The normalization-information algorithm, with its explicit certificate invariant, is also a clean new result, and the identical-valuation tight bound for two agents is a nice addition. The paper is generally well organized and the main transfer proof of Theorem 5.1 is conceptually appealing. The primary concerns are the incomplete EFX impossibility proof for n≥3 with frequency predictions, which supports a headline entry in Table 1, and the fact that the noisy-frequency guarantee is expressed through an algorithm-chosen instantiation error rather than a bound in terms of prediction quality.

major comments (2)
  1. [Section 5, Theorem 5.6, Case 2] The proof of Case 2 contains an uncovered branch. After g2 is allocated to agent 2, the proof claims that if at least one of {g3,...,g_{n+1}} is allocated to agent 2 and agent 1 receives no good from {g4,...,g_n}, then v1(A2\{g}) ≥ K^2 for g ∈ argmin_{g'∈A2} v1(g'). This is false when agent 2's additional good is g_{n+1}: by the valuation table v1(g_{n+1}) = ε, so with A2 = {g2, g_{n+1}} the minimum is ε and v1(A2\{g}) = v1(g2) = K, not K^2. The subsequent cardinality step also fails in this branch: for n = 4, the allocation A1 = {g1}, A2 = {g2, g5}, A3 = {g3}, A4 = {g4} satisfies the case's premise, yet no agent is left empty; the EFX violation comes from agent 3 envying agent 2 after removing g2, a pair not analyzed by the proof. Thus Theorem 5.6, and the '✗†' entry for EFX under frequency predictions in Table 1, are not established as written. The proof needs either a complete case analysis covering this branch or a modified adversarial construction.
  2. [Section 5.1, Theorem 5.7] The noisy-frequency guarantee is stated in terms of the algorithm's own instantiation error η_i, and the paper does not provide any instantiation rule with a worst-case bound on η_i in terms of a natural distance between predicted and true multisets, such as 1-Wasserstein distance. Consequently, the abstract's claim that guarantees 'degrade gracefully with the error parameters' under noisy frequency predictions is not yet a robustness guarantee with respect to prediction quality: if a predictor is approximately right but the instantiation rule is poorly chosen, η_i can be large and the bound becomes vacuous. The authors should either prove a bound for a concrete natural instantiation rule, or explicitly state in the main text that the advertised robustness is with respect to the end-to-end instantiation error, leaving the prediction-error dependence as an open question.
minor comments (4)
  1. [Section 3, Example 3.2] The discussion of the flaw in the Kahana-Hazon example would be clearer if the proposed alternating algorithm's PROP1 guarantee were proved explicitly, since the example is used to justify relying on Theorem 3.3 for the PROP1 impossibility.
  2. [Section 5, Lemma 5.2] In the proof of Lemma 5.2, the phrase 'as only k−1 goods have been selected before this turn' is not the correct reason for the bound v_i(h_{k,v}) ≥ top_i(k); the bound holds because, for any set of k−1 removed goods, the best remaining value is at least the k-th largest value of the multiset. Please rephrase to avoid confusing the global turn count with the agent's own pick count.
  3. [Section 4, Theorem 4.3] In the proof of Theorem 4.3, the expression '1−2 −k3+1' is ambiguous: it should be typeset as either 1−2^{-k^3+1} or 1−2^{-(k^3+1)}. The same ambiguity appears in the valuation table in that proof.
  4. [Section 6, Theorem 6.3] In the proof of Theorem 6.3, expressions such as 'converges to √5−1/2' should be parenthesized as (√5−1)/2 to avoid confusion with √5 − 1/2.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the share-lifting theorem is a genuine black-box reduction and self-citations are auxiliary.

full rationale

The central derivation (Theorem 5.1) is not circular. It assumes only that a share s is feasible in the single-shot offline model, constructs a picking sequence from an IDO offline allocation, and then proves (Lemma 5.2 and Lemma 5.3) that Algorithm 2, run on the true frequency multisets, gives every agent at least the value of that offline allocation. The guarantee is an inequality established from the picking-sequence structure, not a restatement of the feasibility assumption. Theorems 4.1 and 4.2 are self-contained invariant arguments using normalization information; no parameter is fitted and no predicted quantity is renamed as a guarantee. Theorem 5.7 is a Lipschitz-style robustness bound expressed through the algorithm's own instantiation error eta_i; the paper explicitly flags (Section 5.1) that bounding eta_i by a multiset-distance is left open, which is a limitation but not a circular reduction. Self-citations (Elkind et al. 2025a for Proposition 6.1; Choo et al. 2025; Lim et al. 2026; Neoh and Teh 2025) are auxiliary, reproduced, or merely contextual, and none is load-bearing for the share-lifting claim. A separate correctness concern, unrelated to circularity, is that the proof of Theorem 5.6, Case 2, omits the branch where agent 2's extra good is g_{n+1}; this does not affect the circularity verdict.

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

The paper introduces no free parameters fitted to data and no invented physical or model entities. Its central claims rest on standard fair-division domain assumptions (additive nonnegative valuations, adaptive adversary, ex post evaluation), on the exactness of the normalization or frequency information, and on prior offline feasibility results used as black boxes. The IDO valuation profile and the online instantiation rule are analytical constructs, not entities with independent evidential requirements.

assumptions (7)
  • domain assumption Valuations are additive and nonnegative (Section 2).
    All definitions, algorithms and proofs assume additive set functions v_i(S)=sum_{g in S} v_i(g); results do not extend to submodular or other valuations without new analysis.
  • domain assumption The adversary is adaptive and the final allocation is judged ex post (Section 2, Appendix A).
    Impossibility results rely on the adversary choosing future goods after seeing past allocations; positive algorithms must work in this strong model. Under weaker adversaries or ex ante evaluation, the landscape may differ.
  • domain assumption Normalization information means the algorithm knows each agent's total value exactly or within certified bounds (Sections 2, 4, 4.1).
    Algorithm 1 removes an agent once its certificate reaches 1/n; this only works if the scaled totals are known.
  • domain assumption Frequency predictions provide the exact multiset of each agent's values over all goods, and the algorithm knows the number of goods m (Section 5).
    Algorithm 2 and Theorem 5.1 require V_i to be the true multiset and m to be known; the meta-algorithm simulates picking on remaining goods using the predicted multisets.
  • standard math The offline share s is feasible for every single-shot instance, including the IDO profile constructed by sorting each multiset (Section 5).
    The lift to online relies on the existence of an offline allocation meeting s(V_i,n); for MMS, RRS and MXS this is established in cited work (Akrami-Garg 2024, Conitzer et al. 2017, Caragiannis et al. 2023).
  • standard math EF1 implies 0.5-MMS for two agents, and MMS implies PROP1 (Section 2).
    Used to relate Algorithm 1's EF1 guarantee to 0.5-MMS; cited as prior facts from Amanatidis et al. and Caragiannis et al.
  • standard math Plaut and Roughgarden's leximin++ cut-and-choose returns an EFX allocation for two agents in the offline single-shot setting (used in Theorem 5.5).
    The online EFX result for n=2 builds directly on this offline procedure as a black box.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Fair Division with Additional Information." pith.science (2026). https://pith.science/paper/QCOGUP2D

@misc{pith2026250524503,
  author       = {Pith},
  title        = {Pith review of: Online Fair Division with Additional Information},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QCOGUP2D}},
  note         = {Machine review of arXiv:2505.24503}
}
read the original abstract

We study the problem of fairly allocating indivisible goods to agents in an online setting, where goods arrive sequentially and must be allocated irrevocably. Focusing on the popular fairness notions of envy-freeness, proportionality, and maximin share fairness (and their approximate variants), we investigate how access to future information changes what guarantees are achievable. Without any information, we prove strong impossibility results even for approximate fairness. With normalization information (agents' total values), we provide an algorithm that achieves stronger fairness guarantees than previously known results, and show matching impossibilities for stronger notions. With frequency predictions (value multisets without order), we design a meta-algorithm that lifts a broad class of offline ''share-based'' guarantees to the online setting, matching the best-known offline bounds. Finally, we provide learning-augmented variants of both models: under noisy totals or noisy frequency predictions, our guarantees are robust and degrade gracefully with the error parameters.

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Perpetual Fully-Online Approximate Fairness

    cs.GT 2026-05 unverdicted novelty 8.0 of 10

    Introduces deficit-based fully-online algorithms for approximate perpetual fairness with ilde O(\sqrt{t/n}) guarantees in full-history and discounted settings.

  2. Online Fair Division Meets Reordering Buffers

    cs.GT 2026-07 unverdicted novelty 6.0 of 10

    With buffers of size linear in k and number of agents, algorithms achieve EF1 at every step and EF at most steps for personalized k-value mixed manna instances, extending to general additives with ratio dependence.

Reference graph

Works this paper leans on

99 extracted references · 76 canonical work pages · cited by 2 Pith papers

  1. [1]

    Breaking the 3/4 barrier for approximate maximin share

    Hannaneh Akrami and Jugal Garg. Breaking the 3/4 barrier for approximate maximin share. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 74--91, 2024

    2024

  2. [2]

    Semi-online scheduling revisited

    Susanne Albers and Matthias Hellwig. Semi-online scheduling revisited. Theoretical Computer Science, 443: 0 1--9, 2012

    2012

  3. [3]

    Online fair division: A survey

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

    2020

  4. [4]

    Online fair division: Analysing a food bank problem

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

    2015

  5. [5]

    Fair allocation over time, with applications to content moderation

    Amine Allouah, Christian Kroer, Xuan Zhang, Vashist Avadhanula, Nona Bohanon, Anil Dania, Caner Gocmen, Sergey Pupyrev, Parikshit Shah, Nicolas Stier-Moses, and Ken Rodr\' guez Taarup. Fair allocation over time, with applications to content moderation. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pages 25-...

    2023

  6. [6]

    Better collective decisions via uncertainty reduction

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

    2022

  7. [7]

    Comparing approximate relaxations of envy-freeness

    Georgios Amanatidis, Georgios Birmpas, and Vangelis Markakis. Comparing approximate relaxations of envy-freeness. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 42--48, 2018

    2018

  8. [8]

    Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination

    Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theoretical Computer Science, 841: 0 94--109, 2020

    2020

Show all 99 references
  1. [9]

    Voudouris, and Xiaowei Wu

    Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Herv\' e Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322 0 (C), 2023

    2023

  2. [10]

    Voudouris

    Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A. Voudouris. Don't roll the dice, ask twice: The two-query distortion of matching problems and beyond. SIAM Journal on Discrete Mathematics, 38 0 (1): 0 1007--1029, 2024

    2024

  3. [11]

    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. In Proceedings of the 18th International Symposium on Algorithmic Game Theory (SAGT), pages 209--227, 2025

    2025

  4. [12]

    Li, Benjamin Moseley, and Gabriel Visotsky

    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

    2024 arXiv

  5. [13]

    Online bin packing with predictions

    Spyros Angelopoulos, Shahin Kamali, and Kimia Shadkami. Online bin packing with predictions. Journal of Artificial Intelligence Research, 78: 0 1111--1141, 2023

    2023

  6. [14]

    A polynomial-time algorithm for computing a pareto optimal and almost proportional allocation

    Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy. A polynomial-time algorithm for computing a pareto optimal and almost proportional allocation. Operations Research Letters, 48 0 (5): 0 573--578, 2020

    2020

  7. [15]

    Best of both worlds fairness under entitlements

    Haris Aziz, Aditya Ganguly, and Evi Micha. Best of both worlds fairness under entitlements. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 941--948, 2023 a

    2023

  8. [16]

    Computing welfare-maximizing fair allocations of indivisible goods

    Haris Aziz, Xin Huang, Nicholas Mattei, and Erel Segal-Halevi. Computing welfare-maximizing fair allocations of indivisible goods. European Journal of Operational Research, 307 0 (2): 0 773--784, 2023 b

    2023

  9. [17]

    Fair shares: Feasibility, domination, and incentives

    Moshe Babaioff and Uriel Feige. Fair shares: Feasibility, domination, and incentives. Mathematics of Operations Research, 49 0 (4): 0 2180--2211, 2024

    2024

  10. [18]

    Fair-share allocations for agents with arbitrary entitlements

    Moshe Babaioff, Tomer Ezra, and Uriel Feige. Fair-share allocations for agents with arbitrary entitlements. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC), page 127, 2021

    2021

  11. [19]

    Strategyproof scheduling with predictions

    Eric Balkanski, Vasilis Gkatzelis, and Xizhi Tan. Strategyproof scheduling with predictions. In Proceedings of the 14th Innovations in Theoretical Computer Science (ITCS), page 11:1–11:22, 2023

    2023

  12. [20]

    Single-leg revenue management with advice

    Santiago Balseiro, Christian Kroer, and Rachitesh Kumar. Single-leg revenue management with advice. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), page 207, 2023

    2023

  13. [21]

    Online nash social welfare maximization with predictions

    Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1--19, 2022

    2022

  14. [22]

    Proportionally fair online allocation of public goods with predictions

    Siddhartha Banerjee, Vasilis Gkatzelis, Safwan Hossain, Billy Jin, Evi Micha, and Nisarg Shah. Proportionally fair online allocation of public goods with predictions. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pages 20--28, 2023

    2023

  15. [23]

    Approximation algorithms for maximin fair division

    Siddharth Barman and Sanath Kumar Krishnamurthy . Approximation algorithms for maximin fair division. ACM Transactions on Economics and Computation, 8 0 (1): 0 5:1--5:28, 2020

    2020

  16. [24]

    Sundaram

    Siddharth Barman and Ranjani G. Sundaram. Uniform welfare guarantees under identical subadditive valuations. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI), pages 46--52, 2020

    2020

  17. [25]

    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. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 4793--4800, 2022

    2022

  18. [26]

    Fair and efficient multi-resource allocation for cloud computing

    Xiaohui Bei, Zihao Li, and Junjie Luo. Fair and efficient multi-resource allocation for cloud computing. In Proceedings of the 18th Conference on Web and Internet Economics (WINE), pages 169--186, 2022

    2022

  19. [27]

    On fair allocation of indivisible goods to submodular agents

    Gilad Ben Uziahu and Uriel Feige. On fair allocation of indivisible goods to submodular agents. CoRR, abs/2303.12444, 2023

    2023 arXiv

  20. [28]

    Kazachkov, Ariel D

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

    2018

  21. [29]

    Dynamic fair division with partial information

    Gerdus Benad \`e , Daniel Halpern, and Alexandros Psomas. Dynamic fair division with partial information. In Proceedings of the 36th International Conference on Neural Information Processing Systems (NeurIPS), pages 3703--3715, 2022

    2022

  22. [30]

    Kazachkov, Ariel D

    Gerdus Benad \`e , Aleksandr M. Kazachkov, Ariel D. Procaccia, Christos-Alexandros Psomas, and David Zeng. Fair and efficient online allocations. Operations Research, 72 0 (4): 0 1438--1452, 2023

    2023

  23. [31]

    Favrholdt, Christian Kudahl, Kim S

    Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen. Online algorithms with advice: A survey. ACM Computing Surveys (CSUR), 50 0 (2), 2017

    2017

  24. [32]

    Brams and Alan D

    Steven J. Brams and Alan D. Taylor. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, 1996

    1996

  25. [33]

    Online coalition formation under random arrival or coalition dissolution

    Martin Bullinger and René Romen. Online coalition formation under random arrival or coalition dissolution. In Proceedings of the 31st European Symposium on Algorithms (ESA), pages 27:1--27:18, 2023

    2023

  26. [34]

    Stability in online coalition formation

    Martin Bullinger and René Romen. Stability in online coalition formation. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9537--9545, 2024

    2024

  27. [35]

    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

  28. [36]

    New fairness concepts for allocating indivisible items

    Ioannis Caragiannis, Jugal Garg, Nidhi Rathi, Eklavya Sharma, and Giovanna Varricchio. New fairness concepts for allocating indivisible items. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pages 2554--2562, 2023

    2023

  29. [37]

    Weighted envy-freeness in indivisible item allocation

    Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, and Yair Zick. Weighted envy-freeness in indivisible item allocation. ACM Transactions on Economics and Computation, 9 0 (3): 0 18:1--18:39, 2021

    2021

  30. [38]

    Weighted fairness notions for indivisible items revisited

    Mithun Chakraborty, Erel Segal-Halevi, and Warut Suksompong. Weighted fairness notions for indivisible items revisited. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 4949--4956, 2022. Extended version available as arXiv:2112.04166v1

    2022 arXiv

  31. [39]

    Proportional aggregation of preferences for sequential decision making

    Nikhil Chandak, Shashwat Goel, and Dominik Peters. Proportional aggregation of preferences for sequential decision making. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9573--9581, 2024

    2024

  32. [40]

    EFX exists for three agents

    Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. EFX exists for three agents. Journal of the ACM, 71 0 (1), 2024

    2024

  33. [41]

    Edwin Cheng, Hans Kellerer, and Vladimir Kotov

    T.C. Edwin Cheng, Hans Kellerer, and Vladimir Kotov. Semi-on-line multiprocessor scheduling with given total processing time. Theoretical Computer Science, 337 0 (1): 0 134--146, 2005

    2005

  34. [42]

    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. arXiv preprint arXiv:2508.03253, 2025

    2025 arXiv

  35. [43]

    A general framework for learning-augmented online allocation

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

    2023

  36. [44]

    Plant-and-steal: Truthful fair allocations via predictions

    Ilan Reuven Cohen, Alon Eden, Talya Eden, and Arsen Vasilyan. Plant-and-steal: Truthful fair allocations via predictions. In Proceedings of the 37th International Conference in Neural Information Processing Systems (NeurIPS), pages 110057--110096, 2024

    2024

  37. [45]

    Fair public decision making

    Vincent Conitzer, Rupert Freeman, and Nisarg Shah. Fair public decision making. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), pages 629--646, 2017

    2017

  38. [46]

    Online approval committee elections

    Virginie Do, Matthieu Hervouin, Jérôme Lang, and Piotr Skowron. Online approval committee elections. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 251--257, 2022

    2022

  39. [47]

    Semi-online scheduling: A survey

    Debasis Dwibedy and Rakesh Mohanty. Semi-online scheduling: A survey. Computers & Operations Research, 139: 0 105646, 2022

    2022

  40. [48]

    Fairness in temporal slot assignment

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

    2022

  41. [49]

    Temporal elections: Welfare, strategyproofness, and proportionality

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

    2024

  42. [50]

    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 b

    2024

  43. [51]

    Temporal fair division of indivisible items

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

    2025

  44. [52]

    Not in my backyard! T emporal voting over public chores

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

    2025

  45. [53]

    Verifying proportionality in temporal voting

    Edith Elkind, Svetlana Obraztsova, Jannik Peters, and Nicholas Teh. Verifying proportionality in temporal voting. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 13805--13813, 2025 c

    2025

  46. [54]

    Esmaeili, Sharmila Duppala, Davidson Cheng, Vedant Nanda, Aravind Srinivasan, and John P

    Seyed A. Esmaeili, Sharmila Duppala, Davidson Cheng, Vedant Nanda, Aravind Srinivasan, and John P. Dickerson. Rawlsian fairness in online bipartite matching: Two-sided, group, and individual. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5...

    2023

  47. [55]

    Fair allocation of indivisible goods to asymmetric agents

    Alireza Farhadi, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Sebastien Lahaie, David Pennock, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods to asymmetric agents. Journal of Artificial Intelligence Research, 64: 0 1--20, 2019

    2019

  48. [56]

    Fair allocation of indivisible goods: B eyond additive valuations

    Mohammad Ghodsi, MohammadTaghi HajiAghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: B eyond additive valuations. Artificial Intelligence, 303: 0 103633, 2022

    2022

  49. [57]

    Fair and efficient online allocations with normalized valuations

    Vasilis Gkatzelis, Alexandros Psomas, and Xizhi Tan. Fair and efficient online allocations with normalized valuations. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 5440--5447, 2021

    2021

  50. [58]

    Online resource allocation with convex-set machine-learned advice

    Negin Golrezaei, Patrick Jaillet, and Zijie Zhou. Online resource allocation with convex-set machine-learned advice. arXiv preprint arXiv:2306.12282, 2023

    2023 arXiv

  51. [59]

    On fairness via picking sequences in allocation of indivisible goods

    Laurent Gourvès, Julien Lesca, and Anaëlle Wilczynski. On fairness via picking sequences in allocation of indivisible goods. In Proceedings of the 7th International Conference on Algorithmic Decision Theory (ADT), pages 258--272, 2021

    2021

  52. [60]

    Achieving a fairer future by changing the past

    Jiafan He, Ariel Procaccia, Alexandros Psomas, and David Zeng. Achieving a fairer future by changing the past. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pages 343--349, 2019

    2019

  53. [61]

    Semi on-line scheduling on two identical machines

    Yong He and Guochuan Zhang. Semi on-line scheduling on two identical machines. Computing, 62 0 (3): 0 179--187, 1999

    1999

  54. [62]

    Best of both worlds: Agents with entitlements

    Martin Hoefer, Marco Schmalhofer, and Giovanna Varricchio. Best of both worlds: Agents with entitlements. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 564--572, 2023

    2023

  55. [63]

    Necessarily optimal one-sided matchings

    Hadi Hosseini, Vijay Menon, Nisarg Shah, and Sujoy Sikdar. Necessarily optimal one-sided matchings. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 5481--5488, 2021

    2021

  56. [64]

    Class fairness in online matching

    Hadi Hosseini, Zhiyi Huang, Ayumi Igarashi, and Nisarg Shah. Class fairness in online matching. Artificial Intelligence, 335: 0 104177, 2024

    2024

  57. [65]

    Repeated fair allocation of indivisible items

    Ayumi Igarashi, Martin Lackner, Oliviero Nardi, and Arianna Novaro. Repeated fair allocation of indivisible items. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9781--9789, 2024

    2024

  58. [66]

    Online knapsack with frequency predictions

    Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit. Online knapsack with frequency predictions. In Proceedings of the 35th International Conference on Neural Information Processing Systems (NeurIPS), pages 2733--2743, 2021

    2021

  59. [67]

    The leximin approach for a sequence of collective decisions

    Ido Kahana and Noam Hazon. The leximin approach for a sequence of collective decisions. In Proceedings of the 26th European Conference on Artificial Intelligence (ECAI), pages 1198--1206, 2023

    2023

  60. [68]

    Semi on-line algorithms for the partition problem

    Hans Kellerer, Vladimir Kotov, Maria Grazia Speranza, and Zsolt Tuza. Semi on-line algorithms for the partition problem. Operations Research Letters, 21 0 (5): 0 235--242, 1997

    1997

  61. [69]

    An efficient algorithm for semi-online multiprocessor scheduling with given total processing time

    Hans Kellerer, Vladimir Kotov, and Micha \"e l Gabay. An efficient algorithm for semi-online multiprocessor scheduling with given total processing time. Journal of Scheduling, 18: 0 623--630, 2015

    2015

  62. [70]

    Perpetual voting: F airness in long-term decision making

    Martin Lackner. Perpetual voting: F airness in long-term decision making. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 2103--2110, 2020

    2020

  63. [71]

    Proportional decisions in perpetual voting

    Martin Lackner and Jan Maly. Proportional decisions in perpetual voting. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pages 5722--5729, 2023

    2023

  64. [72]

    Fairness in repeated matching: A maximin perspective

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

    2026

  65. [73]

    Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi

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

    2004

  66. [74]

    Adwords and generalized online matching

    Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online matching. Journal of the ACM, 54 0 (5): 0 579--603, 2007

    2007

  67. [75]

    Weighted envy-freeness for submodular valuations

    Luisa Montanari, Ulrike Schmidt-Kraepelin, Warut Suksompong, and Nicholas Teh. Weighted envy-freeness for submodular valuations. Social Choice and Welfare, 65 0 (4): 0 983--1016, 2025

    2025

  68. [76]

    Fair Division and Collective Welfare

    Herv\' e Moulin. Fair Division and Collective Welfare. MIT Press, 2003

    2003

  69. [77]

    Robust market equilibria with uncertain preferences

    Riley Murray, Christian Kroer, Alex Peysakhovich, and Parikshit Shah. Robust market equilibria with uncertain preferences. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 2192--2199, 2020

    2020

  70. [78]

    Resilient fair allocation of indivisible goods

    Dolev Mutzari, Yonatan Aumann, and Sarit Kraus. Resilient fair allocation of indivisible goods. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 2688--2690, 2023

    2023

  71. [79]

    Understanding efx allocations: Counting and variants

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

    2025

  72. [80]

    Online elicitation of necessarily optimal matchings

    Jannik Peters. Online elicitation of necessarily optimal matchings. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 5164--5172, 2022

    2022

  73. [81]

    Strengthening proportionality in temporal voting

    Bradley Phillips, Edith Elkind, Nicholas Teh, and Tomasz W a s. Strengthening proportionality in temporal voting. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2026

    2026

  74. [82]

    Almost envy-freeness with general valuations

    Benjamin Plaut and Tim Roughgarden. Almost envy-freeness with general valuations. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2584--2603, 2018

    2018

  75. [83]

    Technical perspective: A n answer to fair division's most enigmatic question

    Ariel Procaccia. Technical perspective: A n answer to fair division's most enigmatic question. Communications of the ACM, 63 0 (4): 0 118, 2020

    2020

  76. [84]

    Honor among bandits: No-regret learning for online fair division

    Ariel Procaccia, Ben Schiffer, and Shirley Zhang. Honor among bandits: No-regret learning for online fair division. In Proceedings of the 37th International Conference on Neural Information Processing Systems (NeurIPS), pages 13183--13227, 2024

    2024

  77. [85]

    For one and all: Individual and group fairness in the allocation of indivisible goods

    Jonathan Scarlett, Nicholas Teh, and Yair Zick. For one and all: Individual and group fairness in the allocation of indivisible goods. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 2466--2468, 2023

    2023

  78. [86]

    Improved regret bounds for online fair division with bandit learning

    Benjamin Schiffer and Shirley Zhang. Improved regret bounds for online fair division with bandit learning. In (Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 14079--14086, 2025

    2025

  79. [87]

    Democratic fair allocation of indivisible goods

    Erel Segal-Halevi and Warut Suksompong. Democratic fair allocation of indivisible goods. Artificial Intelligence, 277: 0 103167, 2019

    2019

  80. [88]

    Semi-online scheduling with decreasing job sizes

    Steve Seiden, Jiri Sgall, and Gerhard Woeginger. Semi-online scheduling with decreasing job sizes. Operations Research Letters, 27 0 (5): 0 215--221, 2000

    2000

  81. [89]

    Online ad allocation with predictions

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

    2023

  82. [90]

    The problem of fair division

    Hugo Steinhaus. The problem of fair division. Econometrica, 16 0 (1): 0 101--104, 1948

    1948

  83. [91]

    On maximum weighted N ash welfare for binary valuations

    Warut Suksompong and Nicholas Teh. On maximum weighted N ash welfare for binary valuations. Mathematical Social Sciences, 117: 0 101--108, 2022

    2022

  84. [92]

    Weighted fair division with matroid-rank valuations: M onotonicity and strategyproofness

    Warut Suksompong and Nicholas Teh. Weighted fair division with matroid-rank valuations: M onotonicity and strategyproofness. Mathematical Social Sciences, 126: 0 48--59, 2023

    2023

  85. [93]

    Optimal semi-online algorithms for machine covering

    Zhiyi Tan and Yong Wu. Optimal semi-online algorithms for machine covering. Theoretical Computer Science, 372 0 (1): 0 69--90, 2007

    2007

  86. [94]

    Online fair division with contextual bandits

    Arun Verma, Indrajit Saha, Makoto Yokoo, and Bryan Kian Hsiang Low. Online fair division with contextual bandits. arXiv preprint arXiv:2408.12845, 2024

    2024 arXiv

  87. [95]

    Online fair allocations with binary valuations and beyond

    Yuanyuan Wang and Tianze Wei. Online fair allocations with binary valuations and beyond. In Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI), 2026

    2026

  88. [96]

    Learning fair division from bandit feedback

    Hakuei Yamada, Junpei Komiyama, Kenshi Abe, and Atsushi Iwasaki. Learning fair division from bandit feedback. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3106--3114, 2024

    2024

  89. [97]

    Multiwinner temporal voting with aversion to change

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

    2024

  90. [98]

    Fairness-efficiency tradeoffs in dynamic fair division

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

    2020

  91. [99]

    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. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 42506--42516, 2023

    2023

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.