REVIEW 2 major objections 4 minor 15 references
A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read This paper proves that weighted PROP1 and fractional Pareto optimality are simultaneously achievable for all mixed-utility instances, via a strongly polynomial algorithm based on acyclic rounding.
desk verdict Genuinely new rounding algorithm resolves a real open problem, but the strong-polynomial claim rests on an unproved external lemma. 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 consumption graph of a fractional allocation: a bipartite graph whose edges connect an agent to an item when the agent receives a positive fraction of it. The algorithm first obtains an fPO proportional fractional allocation with an acyclic consumption graph, so the graph decomposes into trees. The rounding step performs a breadth-first exploration of these trees, giving each active agent all shared goods and passing shared chores to a neighbor; acyclicity ensures each agent is worsened by at most one shared item, and the known characterization of fPO as weighted-welfare maximization ensures the rounded allocation remains fPO.
What would settle it
Search for a mixed-utility instance in which every fPO proportional fractional allocation Pareto-dominating equal division has a cyclic consumption graph, or in which no integral allocation is simultaneously weighted PROP1 and fPO; either would refute Theorem 1. Alternatively, show that the LP subroutine in the self-contained version cannot be solved in strongly polynomial time, which would remove the time guarantee.
Extended reading notes
Core claim
The central discovery is that mixed-utility instances always admit an integral allocation that is simultaneously weighted PROP1 and fPO, a property stronger than ordinary Pareto optimality. The algorithm starts from the equal-division fractional allocation, computes an fPO fractional Pareto improvement whose consumption graph is acyclic, and then rounds this fractional allocation to an integral one by traversing the resulting forest of trees. Rounding preserves fPO because the final consumption graph remains a subgraph of a welfare-maximizing fractional allocation, and acyclicity guarantees that no agent loses two goods or gains two chores, which is exactly the weighted PROP1 guarantee.
Load-bearing premise
The argument leans on a previously proven lemma that, from any proportional fractional allocation, one can find in strongly polynomial time a fractional Pareto improvement with an acyclic consumption graph; if that lemma fails, the strong time guarantee, and possibly the existence claim for all mixed instances, would not follow from this paper alone.
Editorial extensions
If this is right
- Weighted PROP1 and fPO allocations exist for every mixed-utility instance, closing the existence question for this fairness/efficiency pair.
- The algorithm runs in strongly polynomial time in the number of agents and items, independent of the magnitudes of utilities.
- Recent results for goods-only instances, chores-only instances, and the two-agent mixed case follow as corollaries.
- The result is tight in several directions: strengthening PROP1 to EF1 or PROPX can break existence, and finding a utilitarian-optimal allocation among PROP1 allocations is NP-hard.
Reading between the lines
- The rounding scheme is modular: any method that produces an fPO proportional fractional allocation with an acyclic consumption graph would plug into the same PROP1-preserving rounding, so the hard part is isolated to a single subroutine.
- The flexibility noted in the paper suggests one could randomize or optimize the choice of root agents and tie-breaking to select among many different PROP1-plus-fPO allocations, which may be useful for secondary objectives.
- If the strongly polynomial subroutine for acyclic improvements were ever replaced by a weaker oracle, the existence result could still survive even while the strong time guarantee would not.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper considers fair allocation of indivisible items with additive utilities that may be positive, negative, or zero (mixed utilities). It claims that for any number of agents with positive weights, there always exists an integral allocation that is both fractionally Pareto optimal (fPO) and weighted proportional up to one item (weighted PROP1), and that such an allocation can be computed in strongly polynomial time. The proposed method first forms the equal-share fractional allocation, then uses an algorithm from Sandomirskiy and Segal-Halevi [14] to obtain an fPO Pareto-dominating fractional allocation with an acyclic consumption graph, and finally rounds this allocation through a queue-based tree exploration. The rounding is shown to preserve fPO and to guarantee weighted PROP1 because acyclicity implies each agent can have at most one predecessor, so each agent loses at most one good or gains at most one chore. The paper also provides a self-contained linear-programming-based Algorithm 2 that achieves the same existence result in weakly polynomial time, and it gives examples showing that strict strengthenings of PROP1 or PO do not hold.
Significance. If the main theorem is correct, it resolves an open problem in fair division for mixed utilities, unifying and extending previous results that were limited to goods, chores, or a fixed number of agents/items. The rounding argument is elegant and largely self-contained: the proof that acyclicity limits each agent to one predecessor is convincing, and the preservation of fPO via Varian's supporting-weights characterization is sound. The paper also provides a self-contained (though only weakly polynomial) algorithm, which would already establish the existence of fPO+weighted-PROP1 allocations. However, the strong-polynomial-time claim of Theorem 1 rests on an external lemma that is neither proved nor reproduced in this manuscript, and even the weakly polynomial Algorithm 2 depends on a supporting 'cyclic trade' argument cited from the same external source. These dependencies must be addressed before the central claim can be considered fully verified.
major comments (2)
- [Section 3, Algorithm 1 Step 2; Theorem 1] The strong-polynomial-time guarantee of Theorem 1 is not established within the paper. Step 2 of Algorithm 1 relies entirely on Lemma 2.5 of Sandomirskiy and Segal-Halevi [14], which asserts that, given the proportional fractional allocation, one can compute in strongly polynomial time an fPO fractional Pareto improvement with an acyclic consumption graph. This lemma is not proved in the present manuscript, and the paper does not reproduce its statement. In Section 4, the authors explicitly acknowledge that their self-contained Algorithm 2 is only weakly polynomial because it solves linear programs. Consequently, as written, the existence of a strongly polynomial algorithm does not follow from the arguments in this paper. The authors should either prove the needed lemma in an appendix, provide a peer-reviewed reference with a full proof, or clearly state Theorem 1 as conditional on [14] and state the strongest unconditional result separately.
- [Section 4, Algorithm 2] The correctness of Algorithm 2, offered as a self-contained alternative, also depends on an unproved external result. The algorithm argues that if the interim allocation has a cycle, there exists another allocation with the same utilities and a consumption graph that is a subgraph but omits some edge of the cycle; this is justified by a 'cyclic trade' argument 'as in the proof of Lemma 2.5 from [14]'. Since this cyclic-trade existence is not proved here, the acyclicity guarantee of Algorithm 2 is not fully supported. To make the paper self-contained, the authors should include a proof of this cyclic-trade claim, or, if it is considered standard, provide a complete citation to a published proof.
minor comments (4)
- [Algorithm 1 footnote (tie-breaking conventions)] The footnote claims that the outer while-cycle takes an agent who shares exactly one item and that such an agent exists by acyclicity whenever at least one item is shared. This is false: in the acyclic path with items A, B, C and agents 1, 2, with edges (1,A), (1,B), (2,B), (2,C), every agent shares at least two items. The main algorithm text correctly says 'an agent i sharing at least one item', so the footnote should be corrected or removed.
- [Introduction and Section 2 (definition of PROP1)] The informal description in the Introduction says PROP1 holds if an agent reaches her proportional guarantee after losing her biggest chore or obtaining the biggest good allocated to another agent, but the formal definition in Section 2 uses an existential 'some o' without requiring extremeness. Please align the two descriptions.
- [Appendix A, Examples 2 and 3] The examples are difficult to follow because the tables do not clearly mark which cells correspond to the allocation; the 'squares' mentioned in the text are not visible in the typeset version. Use explicit symbols (e.g., boldface or asterisks) to indicate the allocation.
- [Section 4, Algorithm 2 complexity] The paper states that Algorithm 2 is weakly polynomial but does not provide a bound on the number of iterations. Since each iteration removes at least one edge from a cycle, the number of iterations is at most O(nm), and each LP can be solved in weakly polynomial time; stating this would make the complexity claim more precise.
Circularity Check
No circularity: the rounding proof is self-contained and the cited Lemma 2.5 of [14], while load-bearing for the strong-polynomial bound, is an independent prior result rather than a restatement of the paper's inputs.
full rationale
The paper's main theorem is proved by first taking a proportional fractional allocation, applying an external algorithm (Lemma 2.5 of [14]) to obtain a fractional Pareto-optimal allocation with an acyclic consumption graph, and then rounding it. The rounding part is proved in Lemmas 1 and 2 using only acyclicity, the breadth-first exploration, and Varian's supporting-weights characterization; no fitted parameter is renamed as a prediction and no property is defined in terms of the claimed outcome. The only potentially load-bearing citation is [14], whose author overlaps with this paper, but that cited lemma concerns a different problem (computing an fPO fractional Pareto improvement with acyclic graph) and does not include the target integral PROP1 claims; the paper even supplies a self-contained but weakly polynomial Algorithm 2 for the same step, showing the existence part does not reduce to the citation. Thus there is no definitional or statistical circularity, only a strong-polynomial-time claim that relies on an external theorem, which is a verification/completeness concern rather than circularity.
Assumptions & free parameters
assumptions (4)
- domain assumption Additive utility model over mixed goods and chores, with item utilities allowed to be positive, negative, or zero.
- standard math Every fPO fractional allocation maximizes a weighted sum of utilities for some strictly positive weight vector (Varian 1976, with a mixed-item variant in Lemma 2.3 of [14]).
- ad hoc to paper There exists an fPO fractional allocation x that Pareto dominates the proportional allocation xprop and has an acyclic consumption graph, computable in strongly polynomial time (Lemma 2.5 of Sandomirskiy and Segal-Halevi [14]).
- ad hoc to paper If a cycle exists in the consumption graph of a fractional allocation, there is a 'cyclic trade' that preserves all agents' utilities while deleting at least one edge of the cycle.
Cite this review
Pith. "Pith review of A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation." pith.science (2026). https://pith.science/paper/YZQZPFFL
@misc{pith2026190900740,
author = {Pith},
title = {Pith review of: A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation},
year = {2026},
howpublished = {\url{https://pith.science/paper/YZQZPFFL}},
note = {Machine review of arXiv:1909.00740}
}
read the original abstract
We consider fair allocation of indivisible items under additive utilities. When the utilities can be negative, the existence and complexity of an allocation that satisfies Pareto optimality and proportionality up to one item (PROP1) is an open problem. We show that there exists a strongly polynomial-time algorithm that always computes an allocation satisfying Pareto optimality and proportionality up to one item even if the utilities are mixed and the agents have asymmetric weights. We point out that the result does not hold if either of Pareto optimality or PROP1 is replaced with slightly stronger concepts.
Figures
Reference graph
Works this paper leans on
-
[14]
Efficient Fair Division with Minimal Sharing
Sandomirskiy, F., Segal-Halevi, E., 2019. Fair division with minimal sh ar- ing. CoRR abs/1908.01669. URL http://arxiv.org/abs/1908.01669
work page Pith review arXiv 2019
-
[1]
Efficient re alloca- tion under additive and ordinal preferences
Aziz, H., Biro, P., Lang, J., Lesca, J., Monnot., J., 2019. Efficient re alloca- tion under additive and ordinal preferences. Theoretical Comput er Science
work page 2019
-
[2]
Fair allocatio n of combinations of indivisible goods and chores
Aziz, H., Caragiannis, I., Igarashi, A., Walsh, T., 2019. Fair allocatio n of combinations of indivisible goods and chores. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI)
work page 2019
-
[3]
Weighted maxmin fair share allocation of indivisible chores
Aziz, H., Chan, H., Li, B., 2019. Weighted maxmin fair share allocation of indivisible chores. In: Proceedings of the 28h International Joint C onference on Artificial Intelligence (IJCAI)
work page 2019
-
[4]
The con- strained round robin algorithm for fair and efficient allocation
Aziz, H., Huang, X., Mattei, N., Segal-Halevi, E., 2019. The con- strained round robin algorithm for fair and efficient allocation. CoRR abs/1908.00161
arXiv 2019
-
[5]
Competitive Equilibrium with Indivisible Goods and Generic Budgets
Babaioff, M., Nisan, N., Talgam-Cohen, I., 2017. Competitive equilibr ia with indivisible goods and generic budgets. CoRR abs/1703.08150. URL http://arxiv.org/abs/1703.08150
work page Pith review arXiv 2017
- [6]
-
[7]
Algorithms for competitive d ivision of chores
Brˆ anzei, S., Sandomirskiy, F., 2019. Algorithms for competitive d ivision of chores. CoRR abs/1907.01766
arXiv 2019
Show all 15 references
-
[8]
D., Shah, N ., Wang, J., 2016
Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N ., Wang, J., 2016. The unreasonable fairness of maximum nash welfare . In: Proceedings of the 17th ACM Conference on Electronic Commerce ( ACM- EC)
2016
-
[9]
Fair public decision makin g
Conitzer, V., Freeman, R., Shah, N., 2017. Fair public decision makin g. In: Proceedings of the 18th ACM Conference on Electronic Commerce ( ACM- EC). ACM Press, pp. 629–646
2017
-
[10]
On the co mplexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences
de Keijzer, B., Bouveret, S., Klos, T., Zhang, Y., 2009. On the co mplexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. In: Proceedings of the 1st ADT Conferenc e
2009
-
[11]
M., Seddighin, M., Seddighin, S., Yami, H., 2019
Farhadi, A., Hajiaghayi, M., Ghodsi, M., Lahaie, S., Pennock, D. M., Seddighin, M., Seddighin, S., Yami, H., 2019. Fair allocation of indivisi- ble goods to asymmetric agents. Journal of Artifical Intelligence R esearch (JAIR). 10
2019
-
[12]
Recent Advances in Fair Resource Allocation (ACM EC 2019 Tutorial)
Freeman, R., Shah, N., 2019. Recent Advances in Fair Resource Allocation (ACM EC 2019 Tutorial)
2019
-
[13]
Fair division in the age of internet
Moulin, H., 2019. Fair division in the age of internet. Annual Review of Economics 11, 407–441
2019
-
[15]
R., 1976
Varian, H. R., 1976. Two problems in the theory of fairness. Jou rnal of Public Economics 5 (3), 249 – 260. Appendix A. Examples Example 2 (Pareto improvement over a PROP1 allocation may not even satisfy PROP1 when there are goods. ) . Consider the following instance with 3 ag...
1976
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.