Pith. sign in

REVIEW 3 major objections 3 minor 48 references

Fair Allocation of Divisible Goods under Non-Linear Valuations

T0 review · 3 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read For n agents with arbitrary non-decreasing valuation functions over divisible goods, an algorithm always returns an allocation in which each agent receives at least 1/(2n−1) of her maximin share, and no algorithm can guarantee more than 1/n

desk verdict The paper gives the first asymptotically tight MMS bound for non-linear divisible goods and mostly proves it; the proof of Lemma 3.6 has a real but fixable error, and Algorithm 1 is undefined on leftover fractions. read the letter →

arxiv 2607.15613 v1 pith:BOSVIBAC submitted 2026-07-17 cs.GT

Haris Aziz , Zixu He , Xinhang Lu , Kaiyang Zhou This is my paper · ORCID
classification cs.GT MSC 91B3268Q17
keywords fairdivisiondivisiblegoodsnon-linearvaluationsmaximinshareenvy-freenessParetooptimalityone-breakpointpiecewise-constantresourceallocation
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 studies division of homogeneous divisible goods when an agent's value for a good is an arbitrary non-decreasing function of the amount received, not proportional to the amount. Its central positive result is an algorithm that, for any number n of agents, always yields an allocation giving every agent at least 1/(2n−1) of her maximin share—the value she could guarantee herself by splitting all goods into n bundles and taking the worst. The authors match this with an upper bound: even for the simplest threshold utilities (one-breakpoint piecewise-constant valuations), no allocation can guarantee more than 1/n of the maximin share, and for n=2 and n=3 the ratio 1/n is exactly tight. For envy-freeness combined with Pareto optimality, they show checking existence is NP-hard with three goods, but for a single divisible good they give a polynomial-time algorithm that returns the best envy-free allocation and decides whether an envy-free and Pareto-optimal allocation exists. If correct, the paper pins down the achievable fairness frontier for step-like and arbitrary monotone valuations.

What carries the argument

Algorithm 1 is the central mechanism: Phase I repeatedly selects a good g* that some remaining agent values at MMS_i/(2n−1) or more, and assigns to a set S of such agents the minimal fractions x_i summing to at most 1 that give each the required value; Phase II fills an empty bundle with whole goods until some remaining agent reaches value in [MMS_i/(2n−1), 2·MMS_i/(2n−1)], gives it to her, and repeats. The proof of the guarantee relies on Lemma 3.6(iii): after Phase I, each remaining agent's maximin share in the reduced instance is claimed to stay at least (2|N''|/(2n−1))·MMS_i. For the upper bound, the key object is an instance with n goods where agent 1 values any 1/n share of a good at 1

What would settle it

Run Algorithm 1 on small instances (say n=4, one-breakpoint piecewise-constant valuations) and compute, after Phase I, each remaining agent's maximin share in the reduced instance. Finding any instance where that MMS is strictly below (2|N''|/(2n−1))·MMS_i would falsify Lemma 3.6(iii) and with it the 1/(2n−1) guarantee. A simpler check: verify the paper's claim that, for each large good, at most |N_j| bundles of a remaining agent's MMS partition benefit from it; a single good whose threshold is low enough to benefit |N_j|+1 bundles makes the accounting fail.

Watch

Extended reading notes

Core claim

The paper's central claim is that, for n agents with arbitrary non-decreasing valuations over homogeneous divisible goods, the maximin-share approximation ratio lies between 1/(2n−1) and 1/n. Algorithm 1 attains 1/(2n−1)-MMS by first giving minimal fractions of 'large' goods to agents who value them enough, then bag-filling the remaining small goods. The matching upper bound uses one-breakpoint piecewise-constant valuations: one agent values a 1/n fraction of every good, all other agents value only whole goods, and the first agent can get at most 1/n of her share. For n=2,3 the ratio is tight at 1/n. Separately, checking existence of an envy-free and Pareto-optimal allocation is NP-hard with

Load-bearing premise

The 1/(2n−1)-MMS guarantee stands on Lemma 3.6(iii): after Phase I gives away a large good, each remaining agent's maximin share in the reduced instance remains at least (2|N''|/(2n−1))·MMS_i; if that loss bound is wrong, the guarantee can fall short.

Editorial extensions

If this is right

  • For any n, a 1/(2n−1)-MMS allocation always exists under arbitrary non-decreasing valuations; no regularity such as concavity or piecewise structure is needed for existence.
  • The worst-case guarantee can never exceed 1/n, so the asymptotic MMS approximation constant for this model is pinned between 1/(2n−1) and 1/n, and is exactly 1/n for two and three agents.
  • With at least three goods, deciding whether an envy-free and Pareto-optimal allocation exists is NP-hard even for threshold utilities, so no efficient general algorithm can be expected for that problem.
  • For a single divisible good, an EF-constrained Pareto-optimal allocation always exists and can be computed in polynomial time; the same procedure decides whether an EF and PO allocation exists.
  • Because indivisible-goods allocation is the special case where every threshold equals 1, the 1/(2n−1) guarantee extends a known family of MMS results to a strictly larger valuation class.

Reading between the lines

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

  • The paper's own conjecture that 1/n is achievable for one-breakpoint piecewise-constant valuations suggests a concrete next test: search n=4 instances exhaustively; if the conjecture holds there, the asymptotic constant is likely exactly 1/n for all n.
  • Phase I of Algorithm 1 may leave unallocated fractions of large goods; a computational implementation must decide what to do with these leftovers, since the paper's proof is an existence argument and does not specify a query-efficient protocol.
  • A natural extension of the Partition-based hardness construction is a two-good variant; if it works, it would resolve the paper's open question about m=2, given that the single-good case is polynomial and the three-good case is NP-hard.
  • The structure of the bounds—1/(2n−1) for arbitrary monotone valuations and 1/n for threshold utilities—suggests that intermediate valuation classes might admit intermediate MMS constants, with a unified ratio-symmetric proof possibly explaining the gap.
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

3 major / 3 minor

Summary. The paper studies fair allocation of homogeneous divisible goods among agents with additive, non-decreasing (but not necessarily linear) valuations that depend only on the amount of each good received. For the maximin share (MMS) guarantee, it proves an upper bound of 1/n even for one-breakpoint piecewise-constant valuations (Theorem 3.3), proposes Algorithm 1 and claims a 1/(2n−1)-MMS guarantee for arbitrary non-decreasing valuations (Theorem 3.4), and gives tight 1/n-MMS algorithms for n ≤ 3 agents with one-breakpoint piecewise-constant valuations (Theorems 3.13 and 3.14). For envy-freeness, it proves NP-hardness of checking the existence of an envy-free and Pareto-optimal allocation with at least three goods (Theorem 4.4) and gives a polynomial-time algorithm for the single-good case (Theorems 4.7 and 4.8).

Significance. If the MMS results are correct, they are substantial: the paper asymptotically pins the best possible MMS approximation between 1/(2n−1) and 1/n for a very general class of non-linear valuations, and exactly at 1/n for n ≤ 3 in the structured one-breakpoint case. The EF+PO results also clarify the computational boundary for a natural variant of cake cutting. The paper is self-contained, derives all claims from stated definitions, and contains detailed case analyses for the two- and three-agent results. No free parameters or fitted entities are used in the proofs. The earlier AAMAS version is properly acknowledged.

major comments (3)
  1. [§3.1, Lemma 3.6] The packing argument for property (iii) states that an excluded agent i needs at least a fraction 1/|N_j| of g*_j to reach value MMS_i/(2n−1). This statement is false as written. Maximality of S in line 10(iii) gives ∑_{k∈S} x_k + x_i > 1, and since x_i ≥ x_k for every k∈S, we obtain (|N_j|+1)x_i > 1, i.e. x_i > 1/(|N_j|+1). The conclusion that at most |N_j| bundles of an MMS partition can benefit from g*_j still follows, so Lemma 3.6(iii) is repairable; however, the stated 1/|N_j| bound is incorrect and should be replaced.
  2. [§3.1, Algorithm 1, lines 10–12] Phase I removes g* from M after allocating only ∑_{i∈S} x_i ≤ 1 to agents in S. If this sum is strictly less than 1, the leftover fraction of g* is never assigned to any agent, so the output violates the feasibility constraint ∑_i A_{i,g} = 1. The proof treats g* as wholly removed from the reduced instance, which is consistent with the MMS accounting but not with the allocation matrix. The pseudocode must specify where the leftover fraction goes (for instance, to an arbitrary agent in S); otherwise Algorithm 1 is not well-defined and Theorem 3.4 is not supported as stated.
  3. [§3.1, Algorithm 1, line 7] For arbitrary non-decreasing valuations, which need not be continuous, the set {p∈[0,1] : v_i(g*,p) ≥ MMS_i/(2n−1)} need not have a minimum. For example, if v_i(g*,p)=0 for p≤1/2 and v_i(g*,p)=1 for p>1/2, the set is (1/2,1], so the argmin is undefined. The algorithm should use an infimum together with an arbitrarily small perturbation, or the theorem should be restricted to valuations for which the relevant level sets are closed. As written, the 'arbitrary non-decreasing' claim in Theorem 3.4 is not fully justified.
minor comments (3)
  1. [§3.1, Lemma 3.5] The sentence 'For all agents j∈N, we have v_j(B) ≤ 2·MMS_j/(2n−1), because v_j(g)<...' is not by itself a valid argument: a sum of many goods each valued below the threshold can exceed the bound. The desired bound does follow because the algorithm stops at the first time any agent reaches the threshold, so immediately before the last good was added all agents were below their thresholds. Please make this reasoning explicit.
  2. [§4.1, Algorithm 4] The algorithm and Lemmas 4.5–4.6 rely on an indeterminate ε. For the algorithm to be well-defined and polynomial-time, ε must be chosen small enough to avoid all breakpoints (e.g., a symbolic infinitesimal), or the proof should be phrased as a limiting argument. As written, ε is left unspecified.
  3. [§3.2, Example 3.2] The sentence 'agent 1 (resp., 2 and 3) regards goods g1, g2 (resp., g2, g3 and g3, g4)' appears garbled; it should presumably read that agent 1 regards g1,g2, agent 2 regards g2,g3, and agent 3 regards g3,g4 as having the first valuation type.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main results are derived from stated definitions and external benchmarks, with self-citations used only as disclosure.

full rationale

The paper's central claims are proven from the definitions in Section 2 rather than from the paper's own conclusions. The MMS upper bound (Theorem 3.3) is established by an explicit adversarial instance, and the algorithmic MMS guarantee (Theorem 3.4) is built from Lemmas 3.5-3.7, which reason directly about MMS partitions, reduced instances, and the algorithm's own allocation rules. The 2-agent and 3-agent MMS results similarly use lemmas proved from MMS definitions, threshold properties, and Lemma 3.8/3.9-type decompositions; they do not import a fitted parameter or a conclusion of the same theorem. The EF/PO hardness result reduces from the external Partition problem (Garey and Johnson 1979), and the single-good EF/PO results are proved from the definitions of EF and PO. The only self-citation is the AAMAS preliminary-version footnote, which is disclosure and is not load-bearing for any derivation. The concerns raised about Lemma 3.6's packing inequality and the handling of leftover fractions are potential correctness gaps in the proof, not circularity: they do not show that a stated output is equivalent to an input by construction. No fitted-input-called-prediction, self-citation-chain, uniqueness-import, ansatz-smuggling, or renaming pattern is present.

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

The paper's proofs are self-contained; the only inputs are the model assumptions (additivity, monotonicity, normalization, threshold structure), standard background (NP-completeness of Partition), and classical notions of MMS/EF/PO. No numbers are fitted and no new entities are introduced.

assumptions (5)
  • domain assumption Valuations are additive across goods.
    v_i(x)=Σ_j v_i(g_j,x_j); all MMS and EF arguments rely on additive separability to bound removed-bundle losses.
  • domain assumption Valuations are normalized and monotone non-decreasing.
    v_i(g,0)=0 and v_i(g,p)≤v_i(g,p′) for p≤p′; needed for free disposal and for the MMS lower-bound arguments.
  • domain assumption One-breakpoint piecewise-constant / piecewise-linear structure.
    Algorithms 2, 3, and 4 only work for these subclasses; Theorem 3.3 uses the one-breakpoint structure to build the upper-bound instance.
  • standard math Partition problem is NP-complete.
    Used in the Theorem 4.4 reduction; standard background result.
  • standard math Equal division always exists and is EF.
    Used in Section 4 to motivate EF+PO; trivial for divisible goods.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fair Allocation of Divisible Goods under Non-Linear Valuations." pith.science (2026). https://pith.science/paper/BOSVIBAC

@misc{pith2026260715613,
  author       = {Pith},
  title        = {Pith review of: Fair Allocation of Divisible Goods under Non-Linear Valuations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BOSVIBAC}},
  note         = {Machine review of arXiv:2607.15613}
}
abstract

We study the problem of dividing homogeneous divisible goods among agents with non-linear valuations. Specifically, the value that an agent gains from a given good depends only on the amount of the good they receive, and is not necessarily linear with respect to the amount. For instance, under one-breakpoint piecewise-constant valuations, each agent specifies a threshold for each good such that this agent receives utility zero (resp., full utility of the good) when getting an amount below (resp., at least) the threshold. Given non-linear valuations that are additive across the goods, we focus on designing fair allocation algorithms and consider two well-known fairness properties: the maximin share (MMS) guarantee and envy-freeness (EF). For MMS, we devise an algorithm which always produces a $\frac{1}{2n-1}$-MMS allocation for $n$ agents with arbitrary non-decreasing valuations. It is worth noting that this algorithmic result is almost tight as we give an impossibility of guaranteeing more than $1/n$ approximation to MMS, even when agents have one-breakpoint piecewise-constant valuations. For $n \leq 3$ agents, we show the ratio $1/n$ is tight. Regarding envy-freeness, we show it is NP-hard to check the existence of an EF and Pareto optimal (PO) allocation for $n$ agents and at least three goods, even when agents have one-breakpoint piecewise-constant valuations. We complement the hardness result by considering the case with a single divisible good, and devising a polynomial-time algorithm to check whether an EF and PO allocation exists or not for agents with piecewise-linear valuations.

Figures

Figures reproduced from arXiv: 2607.15613 by the authors.

Figure 1
Figure 1. Examples of non-linear utility functions, where [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Valution functions vi(gj) for agents i ∈ [2] and goods j ∈ [5]. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 3 linked inside Pith

  1. [1]

    Randomized and deterministic maximin-share approximations for fractionally subadditive valuations

    Hannaneh Akrami, Kurt Mehlhorn, Masoud Seddighin, and Golnoosh Shahkarami. Randomized and deterministic maximin-share approximations for fractionally subadditive valuations. In Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS), pages 58821--58832, 2023

    2023

  2. [2]

    An improved envy-free cake cutting protocol for four agents

    Georgios Amanatidis, George Christodoulou, John Fearnley, Evangelos Markakis, Christos-Alexandros Psomas, and Eftychia Vakaliou. An improved envy-free cake cutting protocol for four agents. In Proceedings of 11th International Symposium on Algorithmic Game Theory (SAGT), pages 87--99, 2018

    2018

  3. [3]

    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 103965, 2023

    2023

  4. [4]

    A discrete and bounded envy-free cake cutting protocol for four agents

    Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for four agents. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 454--464, 2016 a

    2016

  5. [5]

    A discrete and bounded envy-free cake cutting protocol for any number of agents

    Haris Aziz and Simon Mackenzie. A discrete and bounded envy-free cake cutting protocol for any number of agents. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 416--427, 2016 b

    2016

  6. [6]

    Fair allocation of divisible goods under non-linear valuations

    Haris Aziz, Zixu He, Xinhang Lu, and Kaiyang Zhou. Fair allocation of divisible goods under non-linear valuations. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 170--178, 2025

    2025

  7. [7]

    Optimal proportional cake cutting with connected pieces

    Xiaohui Bei, Ning Chen, Xia Hua, Biaoshuai Tao, and Endong Yang. Optimal proportional cake cutting with connected pieces. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI), pages 1263--1269, 2012

    2012

  8. [8]

    Fair division of mixed divisible and indivisible goods

    Xiaohui Bei, Zihao Li, Jinyan Liu, Shengxin Liu, and Xinhang Lu. Fair division of mixed divisible and indivisible goods. Artificial Intelligence, 293: 0 103436, 2021 a

    2021

Show all 48 references
  1. [9]

    Maximin fairness with mixed divisible and indivisible goods

    Xiaohui Bei, Shengxin Liu, Xinhang Lu, and Hongao Wang. Maximin fairness with mixed divisible and indivisible goods. Autonomous Agents and Multi-Agent Systems, 35 0 (2): 0 34:1--34:21, 2021 b

    2021

  2. [10]

    Fair division with subjective divisibility

    Xiaohui Bei, Shengxin Liu, and Xinhang Lu. Fair division with subjective divisibility. Games and Economic Behavior, 151: 0 127--147, 2025

    2025

  3. [11]

    Approximate maximin share with subjective divisibility: Beating the 1/2 barrier

    Xiaohui Bei, Ke Ding, Bo Li, and Fangxiao Wang. Approximate maximin share with subjective divisibility: Beating the 1/2 barrier. CoRR, abs/2606.13057, 2026

    2026 arXiv

  4. [12]

    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

  5. [13]

    Almost full EFX exists for four agents

    Ben Berger, Avi Cohen, Michal Feldman, and Amos Fiat. Almost full EFX exists for four agents. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), pages 4826--4833, 2022

    2022

  6. [14]

    Brams and Peter C

    Steven J. Brams and Peter C. Fishburn. Fair division of indivisible items between two people with identical preferences: Envy-freeness, P areto-optimality, and equity. Social Choice and Welfare, 17 0 (2): 0 247--267, 2000

    2000

  7. [15]

    Brams and Alan D

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

    1996

  8. [16]

    Brams, Michal Feldman, John K

    Steven J. Brams, Michal Feldman, John K. Lai, Jamie Morgenstern, and Ariel D. Procaccia. On maxsum fair cake divisions. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI), pages 1285--1291, 2012

    2012

  9. [17]

    Brams, Marc Kilgour, and Christian Klamler

    Steven J. Brams, Marc Kilgour, and Christian Klamler. Two-person fair division of indivisible items: An efficient, envy-free algorithm. Notices of the AMS, 61 0 (2): 0 130--141, 2014

    2014

  10. [18]

    The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes

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

    2011

  11. [19]

    Gerding, and Baharak Rastegari

    Jan Buermann, Enrico H. Gerding, and Baharak Rastegari. Fair allocation of resources with uncertain availability. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 204--212, 2020

    2020

  12. [20]

    Procaccia, Nisarg Shah, and Junxing Wang

    Ioannis Caragiannis, David Kurokawa, Herv\' e Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum N ash welfare. ACM Transactions on Economics and Computation, 7 0 (3): 0 12:1--12:32, 2019

    2019

  13. [21]

    Beyond cake cutting: Allocating homogeneous divisible goods

    Ioannis Caragiannis, Vasilis Gkatzelis, Alexandros Psomas, and Daniel Schoepflin. Beyond cake cutting: Allocating homogeneous divisible goods. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 208--216, 2022

    2022

  14. [22]

    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): 0 4:1--4:27, 2024

    2024

  15. [23]

    1/2 -approximate MMS allocation for separable piecewise linear concave valuations

    Chandra Chekuri, Pooja Kulkarni, Rucha Kulkarni, and Ruta Mehta. 1/2 -approximate MMS allocation for separable piecewise linear concave valuations. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI), pages 9590--9597, 2024

    2024

  16. [24]

    Cohler, John K

    Yuga J. Cohler, John K. Lai, David C. Parkes, and Ariel D. Procaccia. Optimal envy-free cake cutting. In Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAAI), pages 626--631, 2011

    2011

  17. [25]

    On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences

    Bart de Keijzer, Sylvain Bouveret, Tomas Klos, and Yingqian Zhang. On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. In Proceedings of the 1st International Conference on Algorithmic Decision Theory (ADT), pages ...

    2009

  18. [26]

    Concentration and maximin fair allocations for subadditive valuations

    Uriel Feige and Shengyu Huang. Concentration and maximin fair allocations for subadditive valuations. CoRR, abs/2502.13541, 2025

    2025 arXiv

  19. [27]

    On fair division of a homogeneous good

    Uriel Feige and Moshe Tennenholtz. On fair division of a homogeneous good. Games and Economic Behavior, 87: 0 305--321, 2014

    2014

  20. [28]

    A tight negative example for MMS fair allocations

    Uriel Feige, Ariel Sapir, and Laliv Tauber. A tight negative example for MMS fair allocations. In Proceedings of the 17th Conference on Web and Internet Economics (WINE), pages 355--372, 2021

    2021

  21. [29]

    Resource allocation and the public sector

    Duncan Karl Foley. Resource allocation and the public sector. Yale Economics Essays, 7 0 (1): 0 45--98, 1967

    1967

  22. [30]

    Garey and David S

    Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979

    1979

  23. [31]

    Dominant resource fairness: Fair allocation of multiple resource types

    Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker, and Ion Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation (NSDI), pages 323--336, 2011

    2011

  24. [32]

    Fair allocation of indivisible goods: Beyond additive valuations

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

    2022

  25. [33]

    Envy-free cake-cutting for four agents

    Alexandros Hollender and Aviad Rubinstein. Envy-free cake-cutting for four agents. Journal of the ACM, 72 0 (5): 0 34:1--34:54, 2025

    2025

  26. [34]

    An FPTAS for 7/9 to maximin share allocations

    Xin Huang and Shengwei Zhou. An FPTAS for 7/9 to maximin share allocations. CoRR, abs/2511.13056, 2025

    2025

  27. [35]

    Marc Kilgour and Rudolf Vetschera

    D. Marc Kilgour and Rudolf Vetschera. Two-player fair division of indivisible items: Comparison of algorithms. European Journal of Operational Research, 271 0 (2): 0 620--631, 2018

    2018

  28. [36]

    Procaccia, and Junxing Wang

    David Kurokawa, Ariel D. Procaccia, and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM, 65 0 (2): 0 8:1--8:27, 2018

    2018

  29. [37]

    o rg Rothe. Cake-cutting: Fair division of divisible goods. In J\

    Claudia Lindner and J\" o rg Rothe. Cake-cutting: Fair division of divisible goods. In J\" o rg Rothe, editor, Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, chapter 8, pages 507--603. Springer Cham, 2nd e...

    2024

  30. [38]

    Mixed fair division: A survey

    Shengxin Liu, Xinhang Lu, Mashbat Suzuki, and Toby Walsh. Mixed fair division: A survey. Journal of Artificial Intelligence Research, 80: 0 1373--1406, 2024

    2024

  31. [39]

    Complexity results and exact algorithms for fair division of indivisible items: A survey

    Trung Thanh Nguyen and J\" o rg Rothe. Complexity results and exact algorithms for fair division of indivisible items: A survey. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pages 6732--6740, 2023

    2023

  32. [40]

    Envy-freeness and maximum N ash welfare for mixed divisible and indivisible goods

    Koichi Nishimura and Hanna Sumita. Envy-freeness and maximum N ash welfare for mixed divisible and indivisible goods. Mathematical Social Sciences, 138: 0 102449, 2025

    2025

  33. [41]

    Parkes, Ariel D

    David C. Parkes, Ariel D. Procaccia, and Nisarg Shah. Beyond dominant resource fairness: Extensions, limitations, and indivisibilities. ACM Transactions on Economics and Computation, 3 0 (1): 0 3:1--3:22, 2015

    2015

  34. [42]

    Procaccia

    Ariel D. Procaccia. Cake cutting algorithms. In Felix Brandt, Vincent Conitzer, Ulle Endriss, J\' e r\^ o me Lang, and Ariel D. Procaccia, editors, Handbook of Computational Social Choice, chapter 13, pages 311--329. Cambridge University Press, 2016

    2016

  35. [43]

    Reijnierse and Jos A

    Johannes H. Reijnierse and Jos A. M. Potters. On finding an envy-free P areto-optimal division. Mathematical Programming, 83 0 (1): 0 291--311, 1998

    1998

  36. [44]

    Cake-Cutting Algorithm: Be Fair If You Can

    Jack Robertson and William Webb. Cake-Cutting Algorithm: Be Fair If You Can. A K Peters/CRC Press, 1998

    1998

  37. [45]

    Sur la division pragmatique

    Hugo Steinhaus. Sur la division pragmatique. Econometrica, 17: 0 315--319, 1949

    1949

  38. [46]

    Rental harmony: S perner's lemma in fair division

    Francis Edward Su. Rental harmony: S perner's lemma in fair division. The American Mathematical Monthly, 106 0 (10): 0 930--942, 1999

    1999

  39. [47]

    Constraints in fair division

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

    2021

  40. [48]

    Weighted fair division of indivisible items: A review

    Warut Suksompong. Weighted fair division of indivisible items: A review. Information Processing Letters, 187: 0 106519, 2025

    2025

Pith tools

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