{"id":"6d6cbe4b-cd02-4f4e-867f-ab49121f89bf","arxiv_id":"2608.08966","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A lottery over two-agent allocations can be simultaneously ex-ante envy-free, ex-post EFX, and ex-post Pareto optimal, but this becomes impossible for three agents with four goods.","lead":"For two agents splitting indivisible items with additive values, this paper shows that a lottery can be fair in expectation (envy-free on average) while every outcome is both approximately fair (EFX) and efficient (Pareto optimal). For three agents with just four goods, it shows no such lottery exists, pinning down the exact boundary of this best-of-both-worlds guarantee.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader's weakest_assumption identifies additivity as a boundary. I agree that results are stated only for additive non-negative valuations and that the paper itself notes the extension fails for subadditive or submodular valuations. However, this is a scope condition, not a hidden assumption or an internal inconsistency: the central claim explicitly assumes additivity, and all proof steps use it only in the stated ways (the two-agent own-plus-other total value decomposition, the transfer inequalities in Lemma 2, and the lexicographic construction in Lemma 3). I could not locate a step in Theorem 4 where the proof requires more than the stated assumptions, or where a non-obvious feasibility or tie-breaking issue arises. The impossibility proof for three agents also appears correct. Since no load-bearing concern lands, the reader's ACCEPT verdict stands unchanged; the proposed brute-force verification is a low-cost independent check of the main construction.","tokens_in":17976,"tokens_out":12679,"duration_ms":115307,"concrete_test":"Implement a brute-force verifier for two agents with m ≤ 6 items and small integer additive valuations: enumerate all allocations, construct A1 and A2 exactly by the three lexicographic rules of Section 5, and test that both allocations are EFX and Pareto optimal and that the uniform lottery over them is ex-ante envy-free. Run it exhaustively for all valuation profiles in a small range (or over a large random sample); any violation would refute Theorem 4, while a clean run corroborates the structural claims.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. I checked the proof of the strongest claim (Theorem 4). Lemma 3 is sound: if agent j violated EFX at item g in agent i's bundle, both candidate bundles S1 = A^i_i \\ {g} and S2 = A^i_j ∪ {g} give agent i at least half of v_i(M) (so the chosen allocation keeps agent i envy-free), and each gives agent j strictly more than v_j(A^i_j), contradicting the second lexicographic step. The Pareto-optimality argument is also valid: any Pareto dominator is feasible for the lexicographic program, so it either improves agent j (contradicting step 2) or leaves j unchanged and raises total utility (contradicting step 3). The ex-ante envy-freeness case split in Theorem 4 is exhaustive, and inequalities (3) and (4) correctly show each agent's expected own-bundle value is at least half of her total value. The supporting Lemma 2 and the three-agent impossibility enumeration were also checked and are internally consistent. The only non-trivial hypotheses, additivity and non-negativity, are explicit assumptions rather than hidden ones; Section 7 acknowledges that additivity is essential.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the best-of-both-worlds (BoBW) question in fair division of indivisible goods: existence of a lottery that is envy-free ex ante while every realized allocation is, ex post, approximately envy-free and Pareto optimal. For two agents with non-negative additive valuations, it proves (Theorem 2) existence of an ex-ante envy-free lottery supported on allocations that are EF1 and Pareto optimal, and then a stronger result (Theorem 4) with ex-post EFX instead of EF1, with support size at most two. The strong result is obtained by a lexicographic construction of two extremal allocations, one making agent 1 envy-free then maximizing agent 2's utility and total utility, and the reverse for agent 2. For integral valuations, pseudo-polynomial algorithms are given (Propositions 1 and 2), and it is shown that the exact lexicographic allocation is weakly NP-hard in general. The paper also proves an impossibility (Theorem 5): for three agents with strictly positive additive valuations over four goods, no ex-ante envy-free lottery can be supported on allocations that are simultaneously EFX and Pareto optimal. Appendices provide an example where randomized Adjusted Winner fails and show that Lemma 2 does not extend to three agents.","tokens_in":18144,"tokens_out":24525,"duration_ms":216773,"significance":"The paper resolves the two-agent case of a question posed by Freeman et al. (2020) and strengthens the guarantee from EF1 to EFX, which is the strongest approximate envy-freeness notion currently known to be achievable with Pareto optimality in this setting. The proof of Theorem 4 is self-contained and introduces a clean lexicographic method that is likely to be reusable. The impossibility for three agents with only four goods is a valuable boundary result. The paper also gives pseudo-polynomial algorithms and an NP-hardness caveat, and it is transparent about the additivity assumption. I checked the proofs of Lemma 2, Lemma 3, Theorem 4, and Theorem 5 in detail and found them correct and complete; the computational claims are consistent with the stated DP recurrences. The external theorems (Bu et al., Aziz et al.) are cited appropriately.","major_comments":[],"minor_comments":[{"comment":"The introduction states 'The proof of Theorem 1 proceeds by a Pareto-completion argument' for Main Result 1, but Theorem 1 is later assigned to the cited Bu et al. result in Section 4; similarly, Corollary 1 says 'the lottery in Theorem 1' when the intended reference is the authors' Theorem 2. Please renumber or refer to 'Main Result 1' and 'Theorem 2' to remove the ambiguity.","section":"Section 1 / Corollary 1"},{"comment":"In the second sentence, 'envy-free up each one item (EFX)' should read 'envy-free up to any item' (or 'up to each item') to match Definition 4.","section":"Abstract"},{"comment":"The first sentence contains an extra period inside the phrase 'ex-ante EF+ex-post EF1+ex-post PO.'; the period should be placed outside the string so the sentence reads naturally.","section":"Section 7"},{"comment":"The spelling of 'Frosh' in the reference to Babaioff and Frosh [6] should be checked for consistency, and the same for any other author names that appear only once in the text.","section":"Related Work"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a strong contribution to computational social choice, well within the journal's scope. The technical content is sound; the issues are limited to presentation and theorem-numbering consistency. The AI-assisted declaration is transparent and does not raise concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this paper closes the two-agent case of a real open problem: for additive valuations, ex-ante envy-freeness is compatible with ex-post EF1 and ex-post PO, and in fact with the stronger ex-post EFX. Second, the proofs are cleaner than the theorem statements suggest. Lemma 2—every weak Pareto improvement of a two-agent EFX allocation is EF1—is a genuinely useful structural fact. The lexicographic construction for the stronger result is short and the case analysis in the impossibility is exhaustive. I checked the transfer inequalities and the envy-surplus linear program in the three-agent example; both are sound.\n\nThe paper is honest about its boundaries. The positive results stop at two agents. The impossibility is for the EFX version with three agents and four goods; whether the EF1 version is compatible for n>=3 remains open, and the paper says so. The algorithms are pseudo-polynomial, and the author points out that computing his specific lexicographic allocations is weakly NP-hard; he does not overclaim about the complexity of finding some lottery. There is a small typo in the abstract ('up each one item') but the body is fine. The AI disclosure is not a problem: the counterexample was found with help, but the proof is verified and self-contained.\n\nThe citation pattern is fair. The open problem is attributed to Freeman et al., the starting lottery to Bu et al., and the Pareto completion to Aziz et al. Self-citations are to relevant prior work, not padding. Related work is up to date, including the 2026 submodular impossibility.\n\nI'd send this to a serious referee. It resolves a question people in the BoBW literature actually care about, the main result is likely to be cited, and the proofs are complete enough that I found no red flags. For an editor: accept candidate, not a desk reject.","headline":"Clean resolution of the two-agent case of a BoBW open problem, with a sharp three-agent impossibility; the proofs hold up and the paper deserves peer review.","tokens_in":18688,"tokens_out":2680,"would_cite":true,"duration_ms":25863,"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 every two-agent fair-division instance with non-negative additive valuations, there is a lottery over two allocations that is ex-ante envy-free, ex-post EFX, and Pareto optimal.","keywords":["fair division","indivisible goods","best of both worlds fairness","ex-ante envy-freeness","ex-post EFX","Pareto optimality","additive valuations","randomized allocation"],"falsifier":"Compute the two lexicographic allocations $A^1$ and $A^2$ from Section 5 for any concrete two-agent instance and check whether each is EFX and Pareto optimal and whether each agent's expected own-bundle utility in the uniform lottery is at least $v_i(M)/2$; the theorem predicts all three checks pass for every non-negative additive instance. For the three-agent claim, enumerate all EFX allocations for the four-good valuations in Theorem 5; if any allocation beyond $X,Y,Z$ is simultaneously EFX and Pareto optimal, or if a lottery over $X,Y,Z$ satisfies the three envy-surplus inequalities, the impossibility would be refuted.","tokens_in":17743,"feed_emoji":"🎲","tokens_out":7889,"duration_ms":81323,"temperature":0.7,"pith_summary":"The paper targets an open 'best of both worlds' question in fair division: can a random allocation of indivisible items be exactly fair in expectation while every outcome it might produce is both approximately fair and efficient? For two agents with non-negative additive valuations, the answer is yes: there is always a lottery over at most two allocations that is ex-ante envy-free, ex-post envy-free up to any item (EFX), and ex-post Pareto optimal. The paper also gives a softer version with ex-post EF1, proves the lotteries can be computed in pseudo-polynomial time for integral valuations, and shows the two-agent guarantee is sharp by constructing a three-agent, four-good instance where no such lottery exists.","feed_headline":"Coin flip gives a fair, efficient two-person split every time","feed_subtitle":"A 50-50 lottery over two specially built allocations is fair in expectation and envy-free up to any item.","key_machinery":"The central objects are two extremal allocations, one favoring each agent, built by a three-step lexicographic construction: make agent $i$ envy-free, maximize the other agent's utility subject to that, then maximize total utility. The proof that each allocation is EFX—envy-free up to any positively valued item, meaning each agent prefers her own bundle after removing any positively valued item from the other's bundle—and Pareto optimal runs through a swap-and-transfer argument that relies on additivity. The uniform lottery over the two allocations is ex-ante envy-free because, with two agents, ex-ante envy-freeness is equivalent to ex-ante proportionality, and the extremality inequalities guarantee that each agent's expected own-bundle utility is at least half her value for all items. The weaker EF1 route uses a separate structural lemma: any weak Pareto improvement of a two-agent EFX allocation is EF1, so the support of a known ex-ante envy-free EFX lottery can be Pareto-completed without losing ex-ante envy-freeness.","core_discovery":"The central discovery is that two-agent fair division achieves the strongest natural combination of ex-ante and ex-post requirements. For every instance with two agents and non-negative additive valuations, there exists a probabilistic allocation that is ex-ante envy-free, ex-post EFX, and ex-post Pareto optimal, with support size at most two; when two allocations are required, each receives probability $1/2$. The proof constructs, for each agent, a lexicographically extremal allocation that first makes that agent envy-free, then maximizes the other agent's utility, then maximizes total utility, and shows that each resulting allocation is EFX and Pareto optimal. The paper also proves an impossibility for three agents: with strictly positive additive utilities over four goods, no ex-ante envy-free lottery can be supported on allocations that are simultaneously EFX and Pareto optimal.","pith_inferences":["A natural next step is to search small three- and four-agent additive instances to locate the exact boundary of the impossibility; the paper's four-good example shows the boundary is low, but the minimal number of goods required for the obstruction is not identified.","The lexicographic template could generalize to other two-agent objectives: replacing the 'maximize the other agent's utility' step with, say, maximizing Nash welfare or minimizing envy surplus might yield ex-ante fairness together with different ex-post efficiency or stability benchmarks.","If a positive result for three or more agents exists, the paper's appendix suggests it must coordinate fairness and efficiency globally rather than Pareto-improving each support allocation independently, since the two-agent transfer argument provably fails there."],"forward_implications":["Every two-agent instance admits a two-outcome lottery that is simultaneously fair in expectation, envy-free up to any item in every realized allocation, and Pareto optimal; a single coin flip implements it.","For integer-valued additive valuations, this lottery is constructible in pseudo-polynomial time, so the guarantee is algorithmic rather than purely existential.","The result is tight on the efficiency dimension: the paper notes that ex-post fractional Pareto optimality cannot be added, and that ex-ante Pareto optimality together with ex-post EF1 and ex-ante envy-freeness is likewise impossible even for two agents.","For three or more agents, the ex-ante envy-free, ex-post EF1, ex-post Pareto-optimal combination remains open, and the paper's appendix shows that the two-agent Pareto-completion argument cannot be transplanted because a Pareto improvement of a three-agent EFX allocation can fail EF1.","Additivity is essential: for monotone subadditive or submodular valuations, even a deterministic allocation that is both EF1 and Pareto optimal may fail to exist.","The three-agent impossibility uses strictly positive valuations and only four goods, so the obstruction is not an artifact of zero-valued items."],"supporting_citations":[{"why":"Supplies the base two-agent ex-ante envy-free lottery supported on EFX allocations that the EF1 route Pareto-completes.","marker":"[10]"},{"why":"Provides the pseudo-polynomial-time Pareto-domination subroutine used to compute the EF1-and-PO support for integral valuations.","marker":"[2]"},{"why":"Forms the open problem the paper answers: whether ex-ante envy-freeness, ex-post EF1, and ex-post Pareto optimality are compatible.","marker":"[17]"},{"why":"Establishes the impossibility of ex-ante proportionality with ex-post EF1 and ex-post fractional Pareto optimality, against which the new PO result is contrasted as tight.","marker":"[5]"},{"why":"Supplies the EF1 and Pareto-optimal maximum-Nash-welfare benchmark and the subadditive incompatibility used to show additivity is essential.","marker":"[12]"},{"why":"Guarantees EFX existence for three agents, the contrast case for the three-agent impossibility.","marker":"[15]"}],"fun_headline_variants":["Two agents always get a fair, EFX, Pareto lottery","Coin flips make two-agent division fair, EFX, and optimal","For two agents, a fair lottery exists that is EFX and Pareto","Two-agent fair division: lottery is envy-free, EFX, and Pareto"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the two agents' valuations are additive and non-negative, because the transfer inequalities, the proportionality equivalence, and the lexicographic EFX/PO arguments all use additivity, and the paper itself notes that without it (e.g., monotone subadditive or submodular valuations) even deterministic EF1 plus Pareto optimality can fail.","fun_headline_variants_meta":{"raw":{"variants":["Two agents always get a fair, EFX, Pareto lottery","Coin flips make two-agent division fair, EFX, and optimal","For two agents, a fair lottery exists that is EFX and Pareto","Two-agent fair division: lottery is envy-free, EFX, and Pareto"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001361,"raw_usage":{"total_tokens":5467,"prompt_tokens":838,"completion_tokens":4629,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":454,"completion_tokens_details":{"reasoning_tokens":4551}},"tokens_in":454,"tokens_out":4629,"duration_ms":34790,"temperature":1.0,"reasoning_tokens":4551,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:19:59.054703+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the two lexicographic allocations $A^1$ and $A^2$ from Section 5 for any concrete two-agent instance and check whether each is EFX and Pareto optimal and whether each agent's expected own-bundle utility in the uniform lottery is at least $v_i(M)/2$; the theorem predicts all three checks pass for every non-negative additive instance. For the three-agent claim, enumerate all EFX allocations for the four-good valuations in Theorem 5; if any allocation beyond $X,Y,Z$ is simultaneously EFX and Pareto optimal, or if a lottery over $X,Y,Z$ satisfies the three envy-surplus inequalities, the impossibility would be refuted.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the pseudo-polynomial-time Pareto-domination subroutine used to compute the EF1-and-PO support for integral valuations."},{"cited_title":"Bestofbothworlds:ex-anteandex-post fairness in resource allocation","cited_arxiv_id":null,"evidence_quote":"Forms the open problem the paper answers: whether ex-ante envy-freeness, ex-post EF1, and ex-post Pareto optimality are compatible."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the impossibility of ex-ante proportionality with ex-post EF1 and ex-post fractional Pareto optimality, against which the new PO result is contrasted as tight."},{"cited_title":"Caragiannis, D","cited_arxiv_id":null,"evidence_quote":"Supplies the EF1 and Pareto-optimal maximum-Nash-welfare benchmark and the subadditive incompatibility used to show additivity is essential."}],"review_version":1}