{"id":"59b623fe-31d5-47ed-85e8-06e36aea1261","arxiv_id":"2507.16209","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New best-of-both-worlds fair division results: ex-ante 9/10-EF with ex-post EFX+PO for lexicographic preferences, ex-ante 1/2-EF with ex-post EFX-with-charity for monotone valuations, and ex-ante 1/2-Prop with ex-post EFX-with-bounded-charity for subadditive valuations.","lead":"Fair division asks whether a lottery over allocations can be fair on average and fair in every draw. This paper proves new positive and negative results for such 'best-of-both-worlds' guarantees, attaining stronger ex-post fairness (EFX) alongside non-trivial ex-ante fairness for lexicographic, monotone, and subadditive valuations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4 rests on an unproved assertion in Lemma 12 that the CKMS21 little charity step never decreases agent utilities; without this, the ex-ante 1/2-Prop chain collapses.","rationale":"I read the paper's main claims in good faith. Theorem 2 is supported by a self-contained, detailed analysis; the dependent rounding proof was spot-checked and no competing gap emerged. Theorem 3's proof is sound because in Algorithm 3 only the selected agent changes, and it envies the new bundle, so utilities are monotone by construction; the stochastic dominance argument in Lemma 11 is valid. The central weakness is exactly the one the reader identified: Theorem 4 inherits a black-box monotonicity assertion about the CKMS21 little charity algorithm. The proof of Lemma 12 contains the sentence 'since the agent utilities are non-decreasing' with no proof and no pointer to a specific lemma in CKMS21. This is not merely a missing citation: if the bounded-charity step can reassign bundles, a fixed agent's utility may decrease, and then E[vi(Yi)] ≤ E[vi(Xi)] fails. Since that inequality is the final link in the proof of the ex-ante 1/2-Prop guarantee, Theorem 4 is not fully established as written. My read therefore agrees with the reader's conditional verdict; no verdict adjustment is needed, but the gap should be addressed before acceptance.","tokens_in":34788,"tokens_out":8539,"duration_ms":97909,"concrete_test":"Examine the CKMS21 little charity algorithm as used in Algorithm 4 and prove or disprove the invariant: for every agent i, vi(bundle at end) ≥ vi(bundle at start). If the algorithm only performs swaps in which the recipient envies the new bundle, the invariant follows by induction and should be stated as a lemma with a citation. If it performs envy-cycle rotations or other bundle transfers, search for a small counterexample (start with a 3-agent, 4-good subadditive instance output by Algorithm 3); if any agent's utility decreases, Lemma 12 is false and Theorem 4 needs a different argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is in Section 5.2, proof of Lemma 12: 'Also, since the agent utilities are non-decreasing, we have vi(Yi) ≤ vi(Xi).' Here Y is Algorithm 3's output and X is obtained by running the CKMS21 little charity algorithm on Y. The paper cites no lemma in [CKMS21] establishing this monotonicity, and it is not implied by the output being EFX-with-bounded-charity. An algorithm that transforms Y into a fairer allocation may reallocate goods rather than only add charity goods to bundles, in which case a fixed agent's utility could drop. The entire proof of Theorem 4 uses the chain vi(M) ≤ E[vi(P)] + E[vi(Yi)] + Σ_{j≠i}E[vi(Yj)] ≤ 2n·E[vi(Yi)] ≤ 2n·E[vi(Xi)], so the last inequality is necessary for the 1/2-Prop guarantee. The rest of the paper's main arguments, including Algorithm 3's stochastic dominance proof and the lexicographic analysis, appear internally consistent; this is a narrow but real gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies best-of-both-worlds (BoBW) guarantees in fair division of indivisible goods, aiming for ex-post EFX-type guarantees together with nontrivial ex-ante fairness. For lexicographic preferences it proves an impossibility result (Theorem 1): ex-ante sd-EF and ex-post EFX are incompatible. It then gives a polynomial-time algorithm (Theorem 2) achieving ex-ante 9/10-EF with ex-post EFX and Pareto optimality, using an early-terminated eating algorithm, Birkhoff-von Neumann decomposition, and, for the delicate k=2 case, dependent rounding. For monotone valuations it gives a pseudopolynomial-time algorithm (Theorem 3) achieving ex-ante 1/2-EF with ex-post EFX-with-charity, via a randomized version of the CKMS21 charity algorithm. For subadditive valuations it claims ex-ante 1/2-Prop with ex-post EFX-with-bounded-charity (Theorem 4), by post-processing the output of Algorithm 3 with the CKMS21 little charity algorithm.","tokens_in":35017,"tokens_out":17482,"duration_ms":181898,"significance":"If the theorems are correct, the paper makes a substantial contribution: it provides the first BoBW guarantees at the EFX level for lexicographic preferences, the first BoBW guarantee with EFX-with-charity for general monotone valuations, and the first with EFX-with-bounded-charity for subadditive valuations. The techniques are independently interesting: the randomized charity algorithm in Section 5.1 is simple and elegant, and its stochastic-dominance proof (Lemma 11) is sound and gives a genuine ex-ante 1/2-EF guarantee without any rounding. The lexicographic analysis is detailed, with a complete impossibility proof and a nontrivial dependent-rounding step for k=2. There are no fitted parameters or definitional shortcuts. The main caveat is that Theorem 4 relies on an unproved monotonicity assertion about the CKMS21 little charity algorithm, which is load-bearing for the ex-ante 1/2-Prop guarantee; this gap is localized and likely repairable, but it must be fixed before the result can be accepted.","major_comments":[{"comment":"The inequality E[vi(Yi)] ≤ E[vi(Xi)] is asserted with the justification \"since the agent utilities are non-decreasing\" when the little charity algorithm of [CKMS21] is applied to the output Y of Algorithm 3. This monotonicity is load-bearing: it supplies the last inequality in the chain vi(M) ≤ E[vi(P)] + E[vi(Yi)] + Σ_{j≠i} E[vi(Yj)] ≤ 2n·E[vi(Yi)] ≤ 2n·E[vi(Xi)], from which the ex-ante 1/2-Prop guarantee of Theorem 4 follows. No lemma in [CKMS21] is cited for this property, and it does not follow merely from the fact that X is EFX-with-bounded-charity, because the transformation from Y to X could in principle reallocate goods and lower the utility of a fixed agent. The authors should either prove that the little charity algorithm weakly increases every agent's utility, or cite the specific lemma in [CKMS21] that establishes this. Without such a proof or citation, the ex-ante guarantee of Theorem 4 is unsupported.","section":"5.2, Lemma 12 (proof of Theorem 4)"}],"minor_comments":[{"comment":"The statement of Lemma 10 contains a confusing condition: after restricting to g ∈ L ∪ U \\ {g_i}, it then says \"if g ≠ g_i\", which is redundant, and the second bound is for g = g_i. Please rephrase the statement to distinguish clearly between the two cases.","section":"4.4, Lemma 10"},{"comment":"Theorem 4 is stated as \"There exists an algorithm with pseudopolynomial running time algorithm that...\" with a duplicated word; this should be corrected to \"pseudopolynomial-time algorithm\".","section":"Abstract and Theorem 4"},{"comment":"References [FMNP24a] and [FMNP24b] appear to refer to the same EC 2024 paper by Feldman et al.; they should be merged into a single entry to avoid confusion.","section":"References"},{"comment":"In the proof of Lemma 11, the equality Pr[k_{r0} = i | E] = 1/2 is stated without justification. It is true because k_r is uniform over H_r and conditioning on k_r ∈ {i,j} makes i and j symmetric, but the authors should spell this out, since the conditioning on the first significant iteration could otherwise appear to affect the distribution.","section":"5.1, Lemma 11"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is strong and the lexicographic results appear sound. The only substantive obstacle I see is the unproved monotonicity of the CKMS21 little charity algorithm used in Lemma 12; this is a load-bearing step for Theorem 4 but is likely fixable by supplying a proof or a precise citation. If the authors resolve that point, I expect the paper to be suitable for publication in a serious theory venue. The paper's reliance on the authors' own prior work [CKMS21] is natural here, though the proof should make the exact interface with that paper explicit."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis is a strong fair-division theory paper that makes real progress on best-of-both-worlds guarantees at the EFX level. The lexicographic results are the meat: the sd-EF/EFX incompatibility (Theorem 1) and the 9/10-EF + EFX+PO algorithm (Theorem 2) are new, and the proofs are mostly self-contained and careful. The dependent-rounding section is dense, but the algebra holds up on spot-checking. The randomized charity-swap idea behind Algorithm 3 is genuinely simple and clever, and the ex-ante 1/2-EF + ex-post EFX-with-charity result for monotone valuations (Theorem 3) looks correct; the significant-iteration argument in Lemma 11 is sound.\n\nThe soft spot is Theorem 4. Lemma 12 asserts without proof that the CKMS21 little charity algorithm never decreases agent utilities. That monotonicity is load-bearing: the chain to ex-ante 1/2-Prop is vi(M) ≤ E[vi(P)] + Σ E[vi(Y_j)] ≤ 2n·E[vi(Y_i)] ≤ 2n·E[vi(X_i)], and the last inequality needs pointwise vi(Y_i) ≤ vi(X_i). The paper cites no lemma from [CKMS21] that gives this, and it is not implied by the output being EFX-with-bounded-charity. A charity step can in principle remove goods from an agent's bundle, dropping its utility. This is a genuine gap, though probably fixable—either by citing the right lemma if it exists in CKMS21, or by modifying the argument to handle utility decreases. Right now, Theorem 4 as stated is not proven.\n\nTwo minor notes: the analysis for Algorithm 1 is shown tight only in an example, which is fine. The paper leans heavily on the authors' earlier papers, but as black boxes rather than circular moves, so I do not see that as a problem.\n\nWho is this for? Anyone working in discrete fair division, especially on BoBW or EFX. It deserves a serious referee: the gap is narrow, the rest is solid, and the lexicographic contributions are worth having in the literature.\n\nRecommendation: send to peer review. I would not desk-reject; I would ask the authors to fix Theorem 4's proof before acceptance.","headline":"Strong new BoBW results at EFX level, but Theorem 4 has an unproved monotonicity step that must be fixed.","tokens_in":35613,"tokens_out":5932,"would_cite":true,"duration_ms":61003,"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":"Randomized allocations can be almost envy-free in expectation while every realized outcome is EFX or EFX-with-charity, with algorithms for lexicographic, monotone, and subadditive valuations.","keywords":["fair division","indivisible goods","best-of-both-worlds","ex-ante fairness","envy-freeness up to any good (EFX)","lexicographic preferences","monotone and subadditive valuations","dependent rounding"],"falsifier":"Enumerate small subadditive instances, run the randomized charity-swap routine followed by the bounded-charity step, and record whether any agent's value for its own bundle decreases; a single such decrease would break the inequality chain used to prove the ex-ante guarantee of the subadditive result.","tokens_in":34601,"feed_emoji":"🎲","tokens_out":18993,"duration_ms":178450,"temperature":0.7,"pith_summary":"Fair division of indivisible goods has two competing fairness standards: randomized allocations that are fair in expectation (ex-ante) and deterministic allocations that are only approximately fair (ex-post). This paper asks whether one can combine both when the ex-post standard is the stronger envy-freeness up to any good (EFX), in which removing any single good from another agent's bundle removes the envy. Its central results are algorithmic: for lexicographic preferences, a polynomial-time lottery that is ex-ante $9/10$-envy-free and whose every realization is EFX and Pareto-optimal; for monotone valuations, a pseudopolynomial-time lottery that is ex-ante $1/2$-envy-free with EFX-with-charity in every realization; and for subadditive valuations, a pseudopolynomial-time lottery that is ex-ante $1/2$-proportional with EFX-with-bounded-charity in every realization. The paper also proves that the stronger ex-ante notion used in prior work, stochastic-dominance envy-freeness, cannot coexist with ex-post EFX even in the lexicographic case.","feed_headline":"Fair allocation lottery is 90% envy-free on average, EFX in every draw","feed_subtitle":"Algorithms pair near-envy-free expectations with EFX outcomes in every draw, across three valuation classes.","key_machinery":"Two mechanisms carry the results. For lexicographic preferences, the paper runs the simultaneous eating procedure for exactly one time unit; the goods still being eaten at the cutoff form the set of 'last consumed' goods, whose total mass $k$ is an integer. Those goods are merged into a single super-good, the resulting fractional matching is rounded (via the Birkhoff–von Neumann decomposition, or via dependent rounding when $k=2$), and the leftover goods are given as a tail to a uniformly random unenvied agent who received a last-consumed good. The guarantee is $3k/(3k+1)$-EF in general, exact EF when $k=1$, and $9/10$-EF for $k=2$ thanks to dependent rounding's negative correlation. For monotone and subadditive valuations, the central object is a randomized charity-swap loop: repeatedly choose an inclusion-minimal envied set of unallocated goods, pick a uniformly random agent who envies it, and swap that set with the agent's bundle. The equal opportunity of receiving each envied bundle gives the ex-ante $1/2$ guarantees, and an appended bounded-charity routine converts the ex-post support to EFX-with-bounded-charity.","core_discovery":"The central claim is that EFX-level ex-post fairness does not force giving up non-vacuous ex-ante fairness, once the ex-ante benchmark is relaxed suitably. For lexicographic preferences the construction is a one-unit run of the simultaneous eating procedure followed by decomposition (Birkhoff–von Neumann or dependent rounding) and a random tail assignment; it achieves $9/10$-EF in expectation and EFX plus Pareto optimality (no reallocation could improve one agent without hurting another) in every realization. For general monotone valuations the paper randomizes a charity-swap routine, selecting a uniformly random agent among those who envy a minimal envied set of unallocated goods at each step, which yields ex-ante $1/2$-EF and ex-post EFX-with-charity. For subadditive valuations the same randomized routine is followed by a bounded-charity step, giving ex-ante $1/2$-proportionality and ex-post EFX-with-bounded-charity (at most $n-1$ goods left unallocated). Together with a counterexample to ex-ante sd-EF with ex-post EFX, these constitute the first best-of-both-worlds guarantees at the EFX level for the three domains.","pith_inferences":["The constant $9/10$ arises from the exceptional case $k=2$: the same construction gives $3k/(3k+1)$-EF, which exceeds $9/10$ for all $k \\ge 3$ and equals exact EF at $k=1$, so a different rounding scheme for the two-agent super-good case could plausibly raise the worst-case guarantee.","The randomized charity-swap loop is a template rather than a one-off algorithm: varying the distribution over envying agents, or the rule for choosing the minimal envied set, may yield better ex-ante factors or extend the construction beyond the monotone and subadditive classes considered here.","Composing the randomized charity-swap output with other deterministic fair-division routines, not only the bounded-charity one, would give a family of best-of-both-worlds guarantees with different trade-offs between the size of the unallocated pool and the ex-ante ratio.","The impossibility for sd-EF points toward a weaker ordinal benchmark, such as lexicographic sd-EF, as the right target for lexicographic preferences; if that notion is compatible with EFX, an exact ordinal best-of-both-worlds statement may exist."],"forward_implications":["For lexicographic preferences, instances now come with a polynomial-time lottery whose ex-ante fairness is $9/10$-EF while every realized allocation is EFX and Pareto-optimal, so the earlier EF1-level best-of-both-worlds guarantee is strengthened at the price of a small ex-ante loss.","Because ex-ante sd-EF is incompatible with ex-post EFX already in the lexicographic domain, any future theorem that targets EFX ex-post must either relax the ex-ante benchmark or replace sd-EF by a weaker ordinal notion.","For monotone valuations, the randomized charity-swap routine gives a best-of-both-worlds guarantee of ex-ante $1/2$-EF with ex-post EFX-with-charity, in a domain where purely EFX allocations are not known to exist.","For subadditive valuations, the same routine can be composed with a bounded-charity step to leave at most $n-1$ goods unallocated while retaining ex-ante $1/2$-proportionality; such allocations can then be completed to $1/2$-EFX and EF1 allocations."],"supporting_citations":[{"why":"Establishes the best-of-both-worlds framework and the eating-procedure decomposition into EF1 allocations that this paper seeks to strengthen.","marker":"[AFSV24]"},{"why":"Characterizes EFX and EFX+PO allocations under lexicographic preferences via picking sequences, supplying the ex-post correctness of the lexicographic algorithms.","marker":"[HSVX21]"},{"why":"Supplies dependent rounding with negative correlation, the tool that handles the $k=2$ case and yields the $9/10$-EF guarantee.","marker":"[GKPS06]"},{"why":"Supplies the deterministic EFX-with-charity and EFX-with-bounded-charity routines used as subroutines in the monotone and subadditive results.","marker":"[CKMS21]"},{"why":"Introduces EFX-with-charity, the relaxation whose charity pool underpins the monotone and subadditive guarantees.","marker":"[CGH19]"},{"why":"Provides the decomposition of rectangular fractional matchings used to convert the one-unit eating outcome into a distribution over partial allocations.","marker":"[KCP10]"}],"fun_headline_variants":["EFX ex-post, constant-factor ex-ante fairness: a balanced compromise","First best-of-both-worlds guarantees at EFX level","Best of both worlds: EFX ex-post, non-trivial ex-ante fairness","Randomized allocations achieve EFX ex-post with non-trivial ex-ante fairness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The subadditive result assumes that the final bounded-charity step never lowers any agent's value for its own bundle; if that monotonicity fails, the argument that the expected allocation is half-proportional collapses.","fun_headline_variants_meta":{"raw":{"variants":["EFX ex-post, constant-factor ex-ante fairness: a balanced compromise","First best-of-both-worlds guarantees at EFX level","Best of both worlds: EFX ex-post, non-trivial ex-ante fairness","Randomized allocations achieve EFX ex-post with non-trivial ex-ante fairness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001181,"raw_usage":{"total_tokens":5000,"prompt_tokens":1187,"completion_tokens":3813,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":803,"completion_tokens_details":{"reasoning_tokens":3730}},"tokens_in":803,"tokens_out":3813,"duration_ms":32306,"temperature":1.0,"reasoning_tokens":3730,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T15:18:06.031950+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate small subadditive instances, run the randomized charity-swap routine followed by the bounded-charity step, and record whether any agent's value for its own bundle decreases; a single such decrease would break the inequality chain used to prove the ex-ante guarantee of the subadditive result.","supporting_citations":[],"review_version":1}