{"id":"f684e4e1-115e-45d8-be96-6983734464a1","arxiv_id":"2508.13432","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For two couples a balanced EF1 allocation always exists and is efficiently computable, while three or more couples may have no EF1 allocation; for groups of size at most k, an fPO and PROPk allocation can always be found efficiently.","lead":"Two couples splitting indivisible goods always have a fair-enough division, called EF1, and it can be found in polynomial time; with three or more couples this guarantee can fail. The paper also gives an efficient algorithm producing a fractionally efficient allocation in which the i-th member of every group is guaranteed PROPi.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the iterative-rounding proof of Theorem 4.2 holds up under scrutiny.","rationale":"The reader's conditional verdict is driven by minor issues (Lemma D.1's inequality, the binary n=3 PROP1 proof, and experimental reproducibility), but the central claim—Theorem 4.2—appears correct after a careful line-by-line check. I specifically stress-tested the iterative-rounding algorithm: the counting lemma's use of BFS non-integrality is valid; the feasibility argument for the updated polytope works even when a group's last agent is removed, because the group is not deleted from G' and its edges remain; the proportionality bound for eliminated agents correctly uses the rearrangement inequality; and the fPO argument via support inclusion is sound. The reader's weakest_assumption (additivity) is a scope condition of the model, not a hidden flaw in the theorem. Since no load-bearing concern about the central claim was found, the appropriate verdict is unchanged from the reader's CONDITIONAL, which already reflects the minor, non-central issues.","tokens_in":24418,"tokens_out":35216,"duration_ms":349015,"concrete_test":"Run Algorithm 1 on the minimal instance with two groups of size two (or two singleton groups) and a single good valued 1 by every agent; confirm that the algorithm terminates with an fPO allocation and does not encounter an infeasible LP, and trace that groups whose last agent is removed remain in G' with zero agents so the good constraints stay intact.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I examined Theorem 4.2 and its proof in Appendix C. Lemma 4.1's counting argument is sound: at a BFS with no integral edge, every good must be incident to at least two edges, giving sum of group sizes plus number of remaining goods at least |E| and hence at least 2|M'|, so some nonempty group has total incident weight at most its current size. After step 3, the group remains in G' even if it has zero agents (the pseudocode removes agents, not groups), so the restricted fractional solution keeps good constraints satisfied and remains feasible for the updated polytope. The PROPi guarantee for an eliminated agent is correct because, when the total fractional weight incident to the group is at most i and each x is at most 1, the agent's fractional utility is at most the sum of the i most valuable remaining goods. The fPO preservation follows from the support-inclusion corollary, and the initial BFS is fPO since any Pareto improvement would also satisfy the PROP constraints and would increase total utilitarian welfare. I could not identify a gap in the central construction.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":24580,"tokens_out":31503,"duration_ms":330477,"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":[{"comment":"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.","section":"Appendix D, Lemma D.1"}],"minor_comments":[{"comment":"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":"Theorem 4.3 statement"},{"comment":"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.","section":"Section 2, Lemma 4.1, and Algorithm 1"},{"comment":"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.","section":"Proof of Theorem 4.3"}],"recommendation":"major_revision","confidential_remarks":"The two-couple EF1 result overlaps with the concurrently revised work [BLL+25], but the authors acknowledge this and the proportionality contributions are independent. The substantive gap is confined to the appendix lemma on segment partitions and is clearly repairable; I do not regard it as grounds for rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper is worth engaging with. The headline results are real. EF1 for two couples is now also settled by Bu et al., and the paper says so plainly. What is genuinely new is the impossibility of EF1 for three or more couples (Theorem 3.3) and the iterative-rounding theorem (Theorem 4.2) that gives an fPO allocation which is PROPi for the i-th agent of every group. That constant-factor improvement over the prior PROP-O(log n) is the meat of the paper, and it is in good shape. I checked the central construction, and the stress-test is right: Lemma 4.1 counts correctly, the restricted x* stays feasible after edge and agent removal, and the fPO preservation via support inclusion is sound. I could not find a load-bearing gap in Theorem 4.2.\n\nThe soft spots are where the reader says they are. Lemma D.1's proof contains a false inequality: u(alpha_t) >= u(m-n+1) fails for the least-valued good in the last segment. The lemma itself is plausible and probably repairable, but as written it is broken. The n=3 binary PROP1 proof (Lemma D.5) is also under-argued; the segment construction is asserted rather than proven, and that part reads like a sketch. The experimental section is the weakest: the data is private Spliddit data, and the EF1-existence check is unspecified. Did they solve an exact LP or MILP? Without that, the claim that EF1 exists for every instance-pairing is not independently reproducible, and the empirical results should be treated as suggestive, not as a quantitative finding.\n\nNone of this undermines the central theorems. The paper is honest with the concurrent work, the citations look normal, and the fPO preservation argument cites BFGP22 for exactly the kind of support-inclusion claim it is standard for. The main results deserve referee time, and the small-group PROP1 section plus the experiment section need a careful revision. I would support sending it to peer review, not desk-rejecting it.","headline":"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.","tokens_in":25166,"tokens_out":1447,"would_cite":true,"duration_ms":17431,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["fair division","group fair division","envy-freeness up to one good (EF1)","proportionality up to one good (PROP1)","iterative rounding","fractional Pareto optimality","indivisible goods","couples"],"falsifier":"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.","tokens_in":24176,"feed_emoji":"⚖️","tokens_out":9310,"duration_ms":91405,"temperature":0.7,"pith_summary":"The paper asks how to split indivisible goods fairly when the recipients are couples or other small groups, and every member of a group fully enjoys everything the group receives. It proves that two couples always have an envy-free-up-to-one-good (EF1) allocation—each partner finds their own bundle no worse than the other couple's after removing one good—and that such an allocation can be found in polynomial time; this closes an open problem. It also proves that EF1 cannot be guaranteed for three or more couples, giving an explicit five-good counterexample. On the proportionality side, it shows that when all groups have size at most k, an efficiently computable allocation exists in which the i-th member of each group is PROPi (can reach their proportional share by adding at most i goods), and the allocation is fractionally Pareto optimal; for couples this means PROP1 for one partner and PROP2 for the other. Special cases with binary or opposite preferences upgrade couples to full PROP1, while groups of three agents can defeat PROP1 entirely.","feed_headline":"Two couples always get a fair-enough split; three need not","feed_subtitle":"The same LP-based methods deliver near-proportional, efficient allocations for groups of any size.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the group fair division model and leaves the two-couple EF1 question open that this paper resolves; supplies the pair-structure observation.","marker":"[KSV20]"},{"why":"Gives the basic feasible solution theorem used to find the LP solutions in polynomial time.","marker":"[BT97]"},{"why":"Provides the iterative-rounding paradigm for the Generalized Assignment Problem that the proportionality algorithm adapts.","marker":"[ST93]"},{"why":"Establishes that fractional Pareto optimality is equivalent to maximizing a positive weighted sum of utilities, used to preserve fPO.","marker":"[Var74]"},{"why":"Shows that restricting a fractional allocation's support preserves fractional Pareto optimality, used in the rounding argument.","marker":"[AMS20]"},{"why":"Introduces iterative rounding as a general technique that the main algorithm employs.","marker":"[Jai01]"},{"why":"Concurrent work proves EF1 for two couples and PROP-O(log n) for couples, the proportionality gap the paper improves to PROP2.","marker":"[BLL+25]"}],"fun_headline_variants":["Two couples: fair enough always; three not","Fair split for two couples, not three","EF1 exists for two couples, fails for three","Group fairness: two okay, three not","Proportional and efficient splits for all group sizes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Two couples: fair enough always; three not","Fair split for two couples, not three","EF1 exists for two couples, fails for three","Group fairness: two okay, three not","Proportional and efficient splits for all group sizes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001134,"raw_usage":{"total_tokens":4680,"prompt_tokens":884,"completion_tokens":3796,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":500,"completion_tokens_details":{"reasoning_tokens":3726}},"tokens_in":500,"tokens_out":3796,"duration_ms":31066,"temperature":1.0,"reasoning_tokens":3726,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:17:54.246858+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":2}