REVIEW 3 major objections 2 minor 1 cited by
Efficient Fair Division with Minimal Sharing
T0 review · 3 major / 2 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read For a fixed number of agents, fair efficient divisions minimizing shared objects are polynomial for generic valuations, and NP-hard when valuation ratios align.
desk verdict The central cycle characterization is false for mixed valuations—the stress-test counterexample is correct—so the main positive algorithm is unproven, but the question is good and the NP-hardness half looks sound. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the weighted directed consumption graph $\overrightarrow{CG}_z$ of an allocation $z$: an edge from agent $i$ to object $o$ appears when $i$ consumes $o$ and values it non-negatively (weight $v_{i,o}$) or when $i$ does not fully consume $o$ and values it negatively (weight $|v_{i,o}|$); reverse edges are defined symmetrically. The load-bearing identity is Lemma 2.1: $z$ is fractionally Pareto-optimal if and only if it is non-malicious and no directed cycle $C$ has product of edge weights $\pi(C) < 1$. This reduces fPO-checking to negative-cycle detection (Lemma 2.2) and lets the algorithm enumerate all candidate fPO consumption graphs, first for two agents via ratio thresholds (Lemma 3.9) and then by adding agents one at a time (Lemma 3.10), before solving a constant-size linear program per graph for the fairness constraint. The degree of degeneracy $D_v$ controls how many graphs exist: the count is at most $3^{(1+D_v)n(n-1)/2} m^{n(n-1)/2}$.
What would settle it
Take a specific three-agent mixed goods-and-bads instance, compute an fPO allocation, and check whether the paper's weighted directed consumption graph contains a cycle with product less than 1; if such a cycle appears, Lemma 2.1 and the enumeration step that depends on it are refuted. Alternatively, run the algorithm on a small constructed instance and compare its output against brute-force search over all allocations for small $m$.
Extended reading notes
Core claim
The paper's central claim is a complexity dichotomy for sharing-minimization. For a fixed number of agents $n$ and a valuation matrix $v$ over $m$ objects, let $D_v$ be the degree of degeneracy, the largest number of excess objects on which any two agents share the same value ratio. Theorem 3.6(a) states that an allocation minimizing the number of sharings subject to fractional Pareto-optimality and proportionality or envy-freeness can be computed in $O(3^{n(n-1)D_v/2} m^{n(n-1)/2+2})$ operations, which is strongly polynomial whenever $D_v = O(\log m)$; for generic instances $D_v = 0$ with probability 1. Theorem 3.6(b) states that checking the existence of a fair fractionally Pareto-optimal allocation with zero sharings is NP-hard when $D_v \ge C m^\alpha$, so the hardness comes precisely from aligned valuations.
Load-bearing premise
Everything rests on the graph criterion that an allocation is fractionally Pareto-optimal exactly when its weighted trade graph has no cycle whose product of edge weights is less than 1; if that criterion fails for goods-and-bads instances, the enumeration can skip the true optimum.
Editorial extensions
If this is right
- For fixed $n$ and typical (non-degenerate) valuations, the minimal number of sharings can be computed exactly in polynomial time, so sharing minimization becomes a practical exact tool rather than a heuristic.
- When $D_v = O(\log m)$, the run time is strongly polynomial; since $D_v=0$ generically, almost all instances drawn from a continuous distribution are easy.
- The same enumeration can handle other fairness constraints that are linear in the allocation (weighted envy-freeness, weighted proportionality) and other sharing objectives, because the LP size depends only on $n$.
- Dropping fractional Pareto-optimality makes the problem NP-hard even for non-degenerate valuations (Remark 3.4), so efficiency is not an obstacle but the source of tractability.
Reading between the lines
- One can test how often real preference data fall in the strongly-polynomial regime by computing $D_v$ on collected valuation matrices; the paper's experiments suggest practical instances are often easy, but a systematic distributional study is left open.
- The graph-enumeration recipe is transferable: any fair-division problem whose Pareto frontier has a polynomially sized graph representation could be solved by the same 'enumerate graphs, then solve a small LP' pattern, for example rent division or consensus halving with sharing costs.
- The contrast with discrete Pareto-optimality suggests that fractional Pareto-optimality, not fairness, is the feature that buys algorithmic tractability; one could try replacing fairness notions like EF1 with fPO to see whether other sharing-minimization variants become polynomial.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a sharing-minimization approach to fair division of divisible objects that may be goods or bads. For a fixed number of agents, it develops an algorithm that, for valuations with low 'degree of degeneracy' (in particular, generic valuations), finds a proportional or envy-free fractionally Pareto-optimal allocation with the minimum number of sharings in polynomial time. For highly degenerate valuations, it claims NP-hardness. The algorithm enumerates all consumption graphs of fPO allocations and solves a small LP for each graph. The theoretical results are complemented by experiments on data from the Spliddit platform.
Significance. If the main theorem were correct, the paper would be a valuable contribution: a tractability result for an optimization problem in fair division, with a clean dichotomy based on a natural measure of degeneracy, plus an implemented algorithm with real-data experiments. The paper also contains useful building blocks, including a dynamic-programming enumeration of fPO graphs and a connection to Fisher markets and prior algorithms for pure goods or pure bads. However, the central characterization of fractional Pareto-optimality via directed consumption graphs is false for mixed-sign valuations, and this invalidates the correctness proof of the main positive result.
major comments (3)
- [Lemma 2.1 and Appendix A] The 'only if' direction of the cycle characterization in Lemma 2.1 is false for mixed-sign valuations. The proof in Appendix A assumes that for every edge i_k->o_k in a cycle, either agent i_k consumes o_k and both i_k and i_{k+1} value o_k positively, or agent i_{k+1} consumes o_k and both value o_k negatively. However, the definition of the directed consumption graph also creates an edge i_k->o_k when z_{i_k,o_k}<1 and v_{i_k,o_k}<0, and an edge o_k->i_{k+1} when z_{i_{k+1},o_k}<1 and v_{i_{k+1},o_k}>0. In this mixed-sign case, neither of the transfers described in the proof is feasible: i_k does not own o_k, and i_{k+1} values o_k positively. A concrete counterexample is n=m=3 with valuation columns x=(-1/2,1,1), y=(1,-1/2,1), z=(1,1,-1/2) and allocation z_A=(0,1/2,1/2), z_B=(1/2,0,1/2), z_C=(1/2,1/2,0). This allocation maximizes the unweighted sum of utilities and is therefore fPO, yet the directed graph contains the cycle A->x->B->y->C->z->A with product 1/8<1. Thus the cycle condition is not necessary for fPO. A variant with z_A=(0,1/2,1/2), z_B=(1,0,1/2), z_C=(0,1/2,0) is also fPO, has exactly n-1=2 sharings, and contains the mixed-sign cycle A->x->C->y->A with product 1/2<1, showing that the flaw directly affects allocations within the n-1 sharing bound.
- [Lemma 2.2 and Theorem 3.6(a)] Because Lemma 2.2 is derived from Lemma 2.1, the negative-cycle test can produce false negatives for fPO allocations with mixed-sign edges. The counterexample above would be classified as non-fPO by this test. Since Lemma 3.10 uses Lemma 2.2 to filter the enumerated graph set on the way to G_v, the enumeration in Proposition 3.8 can discard valid fPO consumption graphs, including the graph of an optimal fair allocation. Consequently, the correctness proof of Theorem 3.6(a) is unsupported: the algorithm may fail to find a fair fPO allocation with the minimum number of sharings. This is not a minor gap but a failure of the central characterization on which the main algorithmic claim rests.
- [Appendix B and Lemma 2.5] The proof of Lemma 2.5 asserts that the allocation z* obtained after eliminating all cycles with pi(C)<=1 is fractionally Pareto-optimal by Lemma 2.1. Since Lemma 2.1 is false for mixed valuations, this assertion is not justified. Although Lemma 2.5 might be true by other arguments (e.g., from known results for goods/bads and convexity of the utility possibility set), the proof as written is invalid. Lemma 2.5 is used in the main algorithm (step 1 of the second phase in Theorem 3.6) to justify restricting attention to graphs with at most n-1 sharings, so this compounds the effect of the first two comments.
minor comments (2)
- [Section 2.2] The definition of the weighted directed consumption graph is intricate, and the proof of Lemma 2.1 would be easier to verify if the authors explicitly enumerated the four cases that can give rise to an edge i->o and an edge o->j, rather than only the two cases where agents agree on the sign of the object.
- [Section 4] The experimental section implements the algorithm only for pure goods, so the mixed-valuation case, which is the source of the theoretical difficulty, is not validated computationally. This is a limitation, though a minor one relative to the correctness issue.
Circularity Check
No circularity found: the sharing-minimization result is derived from independently proved graph and LP characterizations, not from fitted inputs or self-citations that assume the conclusion.
full rationale
The paper's central derivation is self-contained and non-circular. The polynomial enumeration of Pareto-optimal consumption graphs rests on Lemma 2.1 (cycle characterization of fPO), Lemma 2.2 (polynomial fPO test), Lemma 2.3 (weighted-utilitarian characterization), and Lemmas 3.9-3.10 (graph enumeration). These lemmas are either proved in the paper (Appendix A and Section 3) or are cited as prior published building blocks with independent content. The main result, Theorem 3.6(a), minimizes the number of sharings over the enumerated fPO graphs by solving a constant-size LP per graph. No parameter is fitted to the number of sharings and then renamed as a prediction; the degree of degeneracy D_v is a property of the valuation matrix, defined independently of the target objective, and it controls only the worst-case number of graphs. Self-citations are present (e.g., Bogomolnaia et al. 2017 for existence of envy-free fPO divisions in mixed manna, Branzei and Sandomirskiy 2019 for algorithms in the bads-only case, and Segal-Halevi 2019b for hardness without fPO), but these are used as building blocks or as contrasts, not as the source of the main claim. In particular, the fPO characterization used for mixed valuations is proved in Appendix A rather than assumed from the cited goods-only or bads-only versions. The concern that Lemma 2.1 may be false for mixed-sign valuations, as raised in the reader's take, is a correctness issue about a specific proof step, not circularity: even if the lemma is wrong, the paper does not define fPO as 'no cycle with product below 1', nor does it fit the cycle condition to ensure the theorem's conclusion. Thus the circularity score is 0.
Assumptions & free parameters
assumptions (5)
- domain assumption Agents have additive utilities over divisible objects with possibly negative values.
- domain assumption Fairness is proportionality or envy-freeness, and efficiency is fractional Pareto optimality.
- domain assumption For mixed manna, envy-free competitive equilibrium with equal incomes exists and is fPO, from Bogomolnaia et al. 2017.
- ad hoc to paper The directed consumption graph cycle criterion in Lemma 2.1 characterizes fPO for mixed goods and bads.
- ad hoc to paper Every fPO utility profile has an fPO allocation with at most n-1 sharings, Lemma 2.5.
Cite this review
Pith. "Pith review of Efficient Fair Division with Minimal Sharing." pith.science (2026). https://pith.science/paper/SRHC2QXC
@misc{pith2026190801669,
author = {Pith},
title = {Pith review of: Efficient Fair Division with Minimal Sharing},
year = {2026},
howpublished = {\url{https://pith.science/paper/SRHC2QXC}},
note = {Machine review of arXiv:1908.01669}
}
read the original abstract
A collection of objects, some of which are good and some are bad, is to be divided fairly among agents with different tastes, modeled by additive utility functions. If the objects cannot be shared, so that each of them must be entirely allocated to a single agent, then a fair division may not exist. What is the smallest number of objects that must be shared between two or more agents in order to attain a fair and efficient division? In this paper, fairness is understood as proportionality or envy-freeness, and efficiency, as fractional Pareto-optimality. We show that, for a generic instance of the problem (all instances except a zero-measure set of degenerate problems), a fair fractionally Pareto-optimal division with the smallest possible number of shared objects can be found in polynomial time, assuming that the number of agents is fixed. The problem becomes computationally hard for degenerate instances, where agents' valuations are aligned for many objects.
Figures
Figures from the paper (1 more)
Forward citations
Cited by 1 Pith paper
-
A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
For mixed goods and chores, a weighted Pareto-optimal allocation that is proportional up to one item always exists and is computable in strongly polynomial time.
Reference graph
Works this paper leans on
-
[1]
Jealousy-freeness and other common properties in Fair Division of Mixed Manna
Abdulkadiroglu A, Sonmez T (1998) Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica 66(3):689. Aleksandrov M (2020) Jealousy-freeness and other common properties in fair division of mixed manna. arXiv preprint arXiv:2004.11469 . Aleksandrov M, Aziz H, Gaspers S, Walsh T (2015) Online Fair Division: a...
work page Pith review arXiv 1998
-
[2019]
Fair Allocation of Indivisible Goods: Improvement and Generalization
(Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik). Ghodsi M, HajiAghayi M, Seddighin M, Seddighin S, Yami H (2018) Fair allocation of indivisible goods: Improvements and generalizations. Proceedings of the 2018 ACM Conference on Economics and Computation , 539–556 (ACM), arXiv preprint 1704.00222. Goldberg PW, Hollender A, Igarashi A, Manurangsi P, Sukso...
work page Pith review arXiv 2018
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.