REVIEW 1 major objections 3 minor 1 cited by
Fair Division Among Couples and Small Groups
T0 review · 1 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read For two couples, an EF1 allocation of indivisible goods always exists and is efficiently computable; for three or more couples it can fail. A general iterative-rounding algorithm guarantees PROPi allocations for groups of any size.
desk verdict A solid, honest group fair-division paper: the fPO+PROPi iterative-rounding theorem holds up, the EF1-for-two-couples result is concurrent but acknowledged, and the main soft spots are a repairable lemma gap and a non-reproducible empirical section. 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 objects are two linear-programming constructions. For the two-couple EF1 result, the LP pairs the goods as {1,2}, {3,4}, ... (after ordering by the first partner's valuations) and forces each couple to get exactly one good from each pair; a basic feasible solution has at most two fractional variables, and a case analysis on those two variables—distinguishing the 'natural rounding' and a swap of the integral parts—shows some rounding is EF1 for all four partners. For the general proportionality result, the machinery is iterative rounding over a polytope whose constraints require that each remaining agent's utility from the fractional allocation plus already-discretely-allocated goods reaches their proportional share. A counting lemma guarantees that every basic feasible solution either has some integral coordinate or some group whose total fractional load is at most the group's size; the algorithm deletes zero edges, fixes integral goods, and eliminates the last agent of any group satisfying the second condition. Starting from a fractionally Pareto optimal solution and never re-introducing deleted edges preserves fPO throughout.
What would settle it
A brute-force search over all additive two-couple instances with a small number of goods (say m ≤ 8) that seeks an instance with no balanced EF1 allocation would either confirm or refute the two-couple EF1 theorem; likewise, a small group-of-three instance with no PROPi allocation would refute the general proportionality theorem.
Extended reading notes
Core claim
The central discovery is a precise boundary between possible and impossible fair division among small groups. For two couples, an EF1 allocation always exists and is computable in weakly polynomial time; the proof rounds an optimal basic feasible solution of a linear program that maximizes the minimum envy gap while forcing each couple to take exactly one good from each consecutive pair of goods ordered by the first partner's valuations. For three or more couples, EF1 may fail, as demonstrated by a five-good instance in which any candidate EF1 allocation would have to give the single-good couple a good valued by both partners. For proportionality, the main theorem states that for groups of arbitrary sizes there is a fractionally Pareto optimal allocation in which the i-th member of each group is PROPi; the iterative-rounding algorithm repeatedly fixes integral coordinates, deletes zero-weight edges, and removes the last agent of a group once its fractional load is small enough, preserving the fairness guarantee for the remaining agents and efficiency throughout.
Load-bearing premise
The paper assumes that each agent's utility for a set of goods is additive (the sum of its goods' utilities) and that every member of a group fully enjoys every good the group receives; if preferences were not additive, the LP formulations and rounding arguments would not apply.
Editorial extensions
If this is right
- For any number of couples, a fractionally Pareto optimal allocation that is PROP1 for one partner and PROP2 for the other can be computed in weakly polynomial time.
- For any groups of size at most k, every agent is guaranteed PROPi for their own index i, so the relaxation of proportionality grows only with the agent's position in the group, not with the number of groups.
- The two-couple EF1 result completes the picture left open by prior work: the family of EF1 output sets is intersecting for two couples but is not intersecting for three or more.
- On real-world allocation instances, EF1 and PROP1 allocations were found for every couple-pairing studied (over 13,000 instance-pairing combinations), and the iterative-rounding algorithm delivered PROP1 in 99% of pairings on average.
Reading between the lines
- The paper's worst-case failures for PROP1 all involve groups of size three, not couples; a small brute-force search over additive couple instances would test the conjecture that PROP1 always exists for couples.
- The LP trick of maximizing the minimum envy gap to reduce the number of fractional basic-feasible variables may be reusable in other rounding problems where a basic feasible solution has too many fractional entries.
- If valuations are non-additive, the two-couple EF1 result may survive (the paper notes a concurrent line of work proving it for general monotone valuations), but the iterative-rounding proportionality algorithm is linearity-critical and would need a different mechanism.
- The near-universal existence of EF1 on real data suggests the three-couple counterexamples are knife-edge; a smoothed or random-valuation existence result for EF1 among couples is a natural next target.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies fair division of indivisible goods among groups whose members fully enjoy their group's bundle, assuming additive utilities. It proves that two couples always admit a balanced EF1 allocation (Theorem 3.1), shows that EF1 allocations need not exist for three or more couples (Theorem 3.3), and establishes the main iterative-rounding result (Theorem 4.2): for arbitrary group sizes there is a fractionally Pareto-optimal allocation in which the i-th member of each group receives a PROPi share, computable in weakly polynomial time. Section 4.2 gives special cases where PROP1 exists for all couples, and Theorem 4.4 gives a PROP1 impossibility and an NP-completeness result for groups of three. Section 5 reports experiments on Spliddit data.
Significance. If the proofs are correct, the main theorem is a strong algorithmic result: it converts the proportionality guarantee into an agent-indexed constant relaxation (PROP1, PROP2, ...) while preserving fractional Pareto optimality and polynomial-time computation, and it avoids the logarithmic loss of prior work. The EF1 result for two couples settles an open case without relying on the earlier graph conjecture. The iterative-rounding proof is carefully constructed; I checked the counting in Lemma 4.1, the feasibility argument for the updated polytope, and the support-based fPO induction and found them sound. The empirical section is reproducible and the code is linked. The main technical defect I found is a false inequality in the proof of Lemma D.1, which affects some of the special-case PROP1 theorems but is repairable.
major comments (1)
- [Appendix D, Lemma D.1] The displayed proof chain asserts u_{gi}(α_{m/n}) ≥ u_{gi}(m−n+1), but α_{m/n} is a good in the last segment {m−n+1, ..., m}, so its index is at least m−n+1 and the reverse inequality holds. This invalidates the proof as written; since Lemma D.1 is used in Lemma D.2 and hence in the second bullet of Theorem 4.3, this is a load-bearing gap. The lemma itself appears true, and the proof can be repaired: if the top good of the last segment, m−n+1, is absent from the bundle, add that good; otherwise add the smallest-index missing good k and use u_{gi}(α_1)+u_{gi}(k) ≥ u_{gi}(1)+u_{gi}(n+1) to bound the first two segments.
minor comments (3)
- [Theorem 4.3 statement] In the second bullet, 'm divides n' should read 'n divides m' (i.e., m is a multiple of n); the surrounding lemmas require m/n to be integer.
- [Section 2, Lemma 4.1, and Algorithm 1] The notation |g| is defined as the original number of agents in a group but is later used for the current number of remaining agents after eliminations from G′. This should be made explicit, since the counting in Lemma 4.1 and the elimination step depend on the dynamic meaning.
- [Proof of Theorem 4.3] The claim that opposite preference rankings reduce to Lemma D.2 is correct only because reversing a ranking reverses the order of the segment blocks, so the two segment partitions coincide as unordered sets; the proof should state this, because the lemma is stated as an equality of the order-labeled partitions.
Circularity Check
No significant circularity: the main existence theorems are derived from explicit LP and rounding arguments, with supporting lemmas proved in the appendices.
full rationale
The paper's central claims are derived from stated assumptions and standard tools, not from their own conclusions. Theorem 4.2 is proved by an iterative-rounding algorithm over an explicitly written polytope; Lemma 4.1 gives a self-contained counting argument, and the PROPi guarantee follows by bounding the fractional utility of an eliminated agent of index i by the value of the i most valuable remaining goods. The fPO preservation rests on Corollary C.2, whose Varian-type characterization is proved from scratch in Appendix C.1 via Proposition C.1 and Lemma C.1, so the citation to BFGP22 is not load-bearing. Similarly, the EF1-for-two-couples result is a genuine rounding argument: the paired-good LP structure is justified by Lemma A.1, which is proved in the appendix, and the subsequent case analysis exhausts the rounding options without importing the desired conclusion. The impossibility results are explicit counterexamples and reductions. No parameter is fitted to data, no prediction is computed from the same quantity it is supposed to predict, and the empirical section does not feed back into any theorem. Self-citations appear only as pointers to standard facts that are additionally reproved or used non-essentially, and therefore they do not create circularity.
Assumptions & free parameters
assumptions (6)
- domain assumption Additive utilities
- domain assumption Indivisible goods and group consumption
- standard math Linear programming background
- standard math Varian fPO characterization
- standard math Total unimodularity of bipartite incidence matrices
- standard math 3-Dimensional Matching is NP-complete
Cite this review
Pith. "Pith review of Fair Division Among Couples and Small Groups." pith.science (2026). https://pith.science/paper/SBPW3SS2
@misc{pith2026250813432,
author = {Pith},
title = {Pith review of: Fair Division Among Couples and Small Groups},
year = {2026},
howpublished = {\url{https://pith.science/paper/SBPW3SS2}},
note = {Machine review of arXiv:2508.13432}
}
abstract
We study the fair allocation of indivisible goods across groups of agents, where each agent fully enjoys all goods allocated to their group. We focus on groups of two (couples) and other groups of small size. For two couples, an EF1 allocation -- one in which all agents find their group's bundle no worse than the other group's, up to one good -- always exists and can be found efficiently. For three or more couples, EF1 allocations need not exist. Turning to proportionality, we show that, whenever groups have size at most $k$, a PROP$k$ allocation exists and can be found efficiently. In fact, our algorithm additionally guarantees (fractional) Pareto optimality, and PROP1 to the first agent in each group, PROP2 to the second, etc., for an arbitrary agent ordering. In special cases, we show that there are PROP1 allocations for any number of couples.
Figures
Forward citations
Cited by 1 Pith paper
-
Delegated Fair Division
A two-level fair division model with centers and affiliated agents is formalized, and efficient algorithms achieve EF1 (and in some cases EFX) at both levels under restricted valuations, alongside impossibility and NP...
Reference graph
Works this paper leans on
-
[1]
A Polynomial-Time Algorithm for Com- puting a Pareto Optimal and Almost Proportional Allocation
[AMS20] Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy. “A Polynomial-Time Algorithm for Com- puting a Pareto Optimal and Almost Proportional Allocation”. In:Operations Research Letters 48.5 (2020), pp. 573–578.doi:10.1016/j.orl.2020.07.005. [BB20] Siddharth Barman and Arpita Biswas.Fair Division Under Cardinality Constraints
-
[1997]
On Allocating Goods to Maxi- mize Fairness
[CCK09] Deeparnab Chakrabarty, Julia Chuzhoy, and Sanjeev Khanna. “On Allocating Goods to Maxi- mize Fairness”. In:2009 50th Annual IEEE Symposium on Foundations of Computer Science. 2009, pp. 107–116.doi:10.1109/FOCS.2009.51. [CGM20] Bhaskar Ray Chaudhury, Jugal Garg, and Kurt Mehlhorn. “EFX Exists for Three Agents”. In: Proceedings of the ACM Conference...
arXiv 2019
-
[2020]
Fair Allocations for Smoothed Utilities
arXiv: 1804.09521 [cs.GT].url:https://arxiv.org/abs/1804.09521. [BFGP22] Yushi Bai, Uriel Feige, Paul Gölz, and Ariel D. Procaccia. “Fair Allocations for Smoothed Utilities”. In:Proceedings of the ACM Conference on Economics and Computation (EC)
-
[2022]
Fair Division with Allocator’s Preference
doi:10.1145/3490486.3538285. [BLL+24] Xiaolin Bu, Zihao Li, Shengxin Liu, Jiaxin Song, and Biaoshuai Tao. “Fair Division with Allocator’s Preference”. In:Web and Internet Economics. Ed. by Jugal Garg, Max Klimm, and Yuqing Kong. Cham: Springer, 2024, pp. 77–94. [BLL+25] Xiaolin Bu, Zihao Li, Shengxin Liu, Jiaxin Song, and Biaoshuai Tao.Fair Division with ...
-
[2025]
Fair Division with Allocator's Preference
arXiv:2310.03475v2 [cs.GT].url: https://arxiv.org/abs/ 2310.03475v2. [BT97] Dimitris Bertsimas and John N. Tsitsiklis.Introduction to Linear Optimization. Athena Scientific Series in Optimization and Neural Computation. Belmont, Mass: Athena Scientific,
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.