{"id":"05420cec-016a-4acf-ba7d-828deeeb517f","arxiv_id":"2505.05809","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Ex ante equitable, ex post EQ1 randomized allocations always exist for two agents, but may not exist for three or more agents and their existence decision is NP-complete.","lead":"This paper studies randomized fair division where the average allocation is exactly equal across agents, while every actual outcome is fair up to one item (EQ+EQ1). It shows such allocations always exist for two agents, but can fail or be computationally hard for three or more.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2 depends on an unverified external guarantee that an EQX allocation for two agents exists in linear time; if [GMT14] provides only EQ1 or a slower algorithm, the proof and the O(m) claim are unsupported.","rationale":"This is the most load-bearing issue because Theorem 2 is the main positive existence result of the paper, and Algorithm 1's proof cannot be repaired by substituting an EQ1 allocation: the inequality v2(g) >= delta for every g in A2 is essential to the case analysis. The concern is about missing external support rather than an internal contradiction; the rest of the proof, including Cases 1, 2.1, and 2.2, appears coherent, and I did not find a counterexample to the two-agent claim. The reader's weakest assumption identified the same dependency, so I agree. Since the gap is a missing verification rather than a demonstrated false theorem, the appropriate verdict remains CONDITIONAL rather than ACCEPT or REJECT; the paper should be revised to cite and state the correct EQX theorem and to confirm the linear-time bound.","tokens_in":20935,"tokens_out":52279,"duration_ms":532502,"concrete_test":"Inspect [GMT14] to confirm it states an O(m) algorithm for an EQX (not merely EQ1) allocation for two agents with unconstrained additive valuations. If it does not, replace the initialization in Algorithm 1 with the correct two-agent EQX construction, re-derive the invariant v2(g) >= delta for all g in A2, and run Algorithm 1 on random normalized two-agent instances to check that the output is always a 1-biased EQ1 allocation and that the total runtime is linear in m.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The two-agent existence proof (Theorem 2, Algorithm 1) begins by invoking [GMT14] for an EQX allocation computable in O(m). The proof then uses the EQX property to infer that for every g in A2, v2(g) >= delta, where delta = v2(A2) - v1(A1); this forces C ⊆ A1 and powers the transfer/swap argument. A mere EQ1 allocation would only guarantee this for at least one item in A2, so the argument would not go through. The manuscript neither restates the [GMT14] theorem nor verifies that it applies to unconstrained two-agent additive valuations with linear running time. If the cited theorem instead proves only EQ1 (or EQX under matroid constraints with a different complexity bound), the central two-agent existence result has a genuine gap, and the stated O(m) complexity may be wrong. The existence claim itself is likely repairable by citing the known two-agent EQX result, but the paper as written does not supply the needed support.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies randomized allocations that are equitable in expectation (ex ante EQ) and equitable up to one item in every realized outcome (ex post EQ1), with an analogous variant for EQX. It gives a geometric characterization (Theorem 1) of instances admitting such allocations via a linear-programming duality argument, and then derives a detailed landscape: for two agents with normalized additive valuations, an EQ+EQ1 allocation always exists and is claimed to be computable in O(m) time (Theorem 2); for binary valuations, an EQ+EQ1 allocation with optimal welfare over all fractional EQ allocations exists and is efficiently computable (Theorem 3); for three or more agents, such allocations may fail to exist (Theorem 5), and deciding existence is weakly NP-complete for three agents (Theorem 6) and strongly NP-complete in general (Theorem 7). The paper also gives a pseudopolynomial-time algorithm for a constant number of agents (Theorem 8) and studies i-biased EQ1 allocations, including their NP-hardness (Theorem 9).","tokens_in":21062,"tokens_out":46631,"duration_ms":464780,"significance":"The paper contributes a clean and useful characterization of best-of-both-worlds equitability, and the contrast with the always-positive results for envy-freeness is conceptually interesting. The characterization theorem is proved directly via LP duality and is likely to be reusable. The binary-valuation result is a strong positive result: it shows that, in that domain, the ex post EQ1 constraint causes no loss in social welfare relative to all fractional EQ allocations, and the proof via bihierarchical decomposition is well matched to the problem. The complexity results, if correct after repairs, provide a fairly complete picture. The paper is also careful about normalization and about stating the dependence on external results, though, as detailed below, one of those external dependencies needs verification and one reduction has a gap that currently leaves Theorem 9 unproved as stated.","major_comments":[{"comment":"The proof begins by invoking [GMT14] for an EQX allocation computable in O(m) time, and this is load-bearing: the EQX property is used to infer that v2(g) >= delta for every g in A2, which forces C subset of A1 and supports the transfer/swap argument in Cases 1 and 2. As used elsewhere in the paper, [GMT14] is cited for EQ1/EF1 allocations, not for EQX. The manuscript neither states the exact theorem from [GMT14] nor proves that an EQX allocation for two agents exists and is computable in O(m). If [GMT14] only guarantees EQ1, the proof of Theorem 2 is unsupported and the claimed O(m) time may be incorrect. The authors should either supply a correct citation, e.g., the two-agent EQX result of [FSVX19] if that is intended, or prove the needed EQX guarantee and re-derive the running time accordingly.","section":"Section 3, Theorem 2 and Algorithm 1"},{"comment":"The reverse direction of the NP-hardness reduction states that d cannot be assigned to agent 2 or agent 3 in any 1-biased EQ1 allocation. This is false without an additional assumption on m. For example, take m=2, b1=3, b2=1, T=2. The allocation A1={g1}, A2={d}, A3={g2} gives values (2,2,1) and is 1-biased and EQ1, but the 2-PARTITION instance has no solution. Thus, as written, the reduction does not prove NP-hardness. The argument can likely be repaired by assuming m>=5, with a padding argument, or by a modified case analysis, but this is a load-bearing gap in a claimed hardness result.","section":"Section 5, Theorem 9 proof"}],"minor_comments":[{"comment":"In the inductive step for g_t in A1, the second occurrence of 'condition (C1b)' should be 'condition (C1a)', and the variable 'v_i(g_t)' should be 'v_1(g_t)'. As written, the proof text is internally inconsistent.","section":"Section 8, Claim 3 proof"},{"comment":"In the reverse direction, the text says that two goods are 'of utility 2/3T each' but the table gives (2m/3)T per partition item; later 'the integers in S_i' should be 'the integers in S'. These are typos but they make the proof hard to follow.","section":"Section 5, Theorem 7 proof"},{"comment":"The values 1.4 and 2.2 in Figure 4 are not integers, while the formal model in Section 2 states v_i: M -> Z+. The example can be scaled by 5 to fit the model, and this should be stated.","section":"Section 5, Theorem 5 example"},{"comment":"When applying Theorem 4 to the polytope P2, the nonnegativity constraints (10) should be written with an explicit upper bound of 1 for each variable, which is implied by the assignment constraints, so that the lower and upper bound vectors in the theorem are integral. The current wording leaves this implicit.","section":"Section 4, proof of Theorem 3"}],"recommendation":"major_revision","confidential_remarks":"The main concern is the unverified EQX citation in Theorem 2: if the authors cannot confirm that [GMT14] proves the stronger EQX guarantee in linear time, the two-agent existence proof needs a replacement. The Theorem 9 reduction is not valid as stated, though the counterexample is small and the theorem may be salvageable with standard padding. I believe the central results are likely correct, but the required fixes are substantive rather than purely editorial."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is a solid paper that answers the main Best-of-Both-Worlds question for equitability — existence for two agents, non-existence for three, matching complexity results, and a clean characterization. I'd send it to peer review.\n\nWhat's genuinely new: the LP-duality characterization (Theorem 1) is elegant and does real work. It turns the search for a distribution over EQ1 allocations into a separating-hyperplane condition, and the two-agent corollary via i-biased EQ1 allocations is a nice reduction. The two-agent proof (Theorem 2) is intricate, and as far as I can trace it, correct — provided the cited EQX guarantee is real. The binary-valuation result uses the bihierarchical theorem from [BCKM13]; I checked the matrix structure and it really is bihierarchical, so that part holds. The NP-hardness reductions look standard, and the pseudo-poly DP is a useful tightness result. The example for non-existence with three agents and four items is tight in several respects and makes the landscape exact.\n\nThe main caveat is the reliance on [GMT14] for a linear-time EQX allocation. The proof's central step — that v2(g) >= delta for every g in A2 — uses the \"up to any good\" property, not just EQ1. The paper cites [GMT14] but doesn't restate the theorem. If that reference only gives EQ1, or if its complexity is not O(m), the proof needs repair and the O(m) claim is unsupported. I suspect the existence result itself is true and repairable, but the authors should spell out the external theorem so the dependency is verifiable.\n\nTwo smaller issues. Theorem 5's proof asserts that every agent must get at least one good in any EQ1 allocation for their 3x4 example. That's true for those valuations, but it's not automatic and they don't justify it. Minor, but worth a line. And Claim 3 has a typo: the second case in the proof should reference (C1a), not (C1b).\n\nWho this is for: anyone working on fair division or randomized allocation. The paper is clearly written, the literature coverage is reasonable, and the main results are novel. The citation pattern looks normal; the uses of [GMT14] and [BCKM13] are legitimate, just one of them under-specified.\n\nI'd engage with this paper. Send it out, ask the authors to verify and state the EQX theorem they are invoking, fix the small gaps, and it should be in good shape.","headline":"Settles the BoBW question for equitability with a clean characterization and matching complexity bounds; deserves a serious referee, but check the external EQX citation.","tokens_in":21648,"tokens_out":7422,"would_cite":true,"duration_ms":79498,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Fair lotteries always exist for two agents; at three they can fail, and deciding is NP-complete.","keywords":["fair division","equitability","best of both worlds","randomized allocation","EQ1","binary valuations","NP-completeness","ex ante fairness"],"falsifier":"Enumerate all integral allocations of the paper's three-agent, four-item example (Figure 4) and check whether every EQ1 allocation gives agent 1 less than the average of agents 2 and 3, confirming the claimed non-existence; or brute-force search small two-agent normalized instances for any counterexample to the claimed universal existence, which would refute Theorem 2.","tokens_in":20682,"feed_emoji":"⚖️","tokens_out":8028,"duration_ms":74600,"temperature":0.7,"pith_summary":"This paper asks when a randomized allocation can deliver equitable outcomes under two senses at once: equal expected utility across agents (ex ante equitability) and fairness after randomness resolves, when any inequity can be fixed by dropping one item (ex post EQ1). The answer depends sharply on the number of agents. For two agents with normalized additive valuations, such a best-of-both-worlds lottery always exists and can be found in linear time; for three or more it may not exist at all, and deciding whether it does is weakly NP-complete for three agents and strongly NP-complete in general. A geometric characterization—an instance admits such a lottery iff every zero-sum weighting of agents is certified by some EQ1 allocation—underlies the positive results, and a bihierarchical rounding theorem gives a welfare-optimal construction for binary valuations. The results contrast with envy-freeness, where best-of-both-worlds allocations always exist.","feed_headline":"Fair lotteries always exist for two agents, not for three","feed_subtitle":"A geometric test separates cases where fair lotteries exist; beyond two agents, deciding is NP-complete.","key_machinery":"The central object is the value-vector set of EQ1 allocations, $\\{\\vec{v}(A) : A \\text{ is EQ1}\\}$, together with the diagonal in $\\mathbb{R}^n$. A BoBW lottery exists exactly when the convex hull of these value vectors meets the diagonal; equivalently, no zero-sum linear functional separates the two. For two agents this condition reduces to the existence of $i$-biased EQ1 allocations for both agents, and the algorithm constructs one by starting from a linear-time EQX allocation and transferring 'compressing' goods one at a time. For binary valuations, the machinery is a rounding theorem for linear programs with bihierarchical constraint structures, a generalization of Birkhoff–von Neumann decomposition, which turns the optimal fractional EQ solution into a convex combination of integral EQ1 allocations.","core_discovery":"The paper establishes the full existence and complexity landscape for ex ante EQ / ex post EQ1 randomized allocations. Its central positive results are that such allocations always exist and are linearly computable for two agents, and that for binary valuations they exist for any number of agents while attaining the same social welfare as the best fractional EQ allocation. Its central negative results are that with three agents and four items such allocations can fail to exist, that deciding existence is weakly NP-complete for three agents and strongly NP-complete in general, and that a pseudo-polynomial algorithm handles any constant number of agents. The load-bearing characterization is geometric: an instance admits the allocation iff for every $\\lambda$ with $\\sum_i \\lambda_i = 0$ there is some EQ1 allocation $A$ with $\\sum_i \\lambda_i v_i(A_i) \\ge 0$, an equivalence proven by LP duality.","pith_inferences":["Inference: the two-agent compression argument may extend to approximate ex ante equitability ($\\alpha$-EQ with $\\alpha < 1$), which the paper raises as an open question; the transfer-and-swap structure suggests small slack can restore existence for small groups.","Inference: the bihierarchical rounding used for binary valuations is a candidate template for matroid-rank valuations, as the paper suggests; a direct check is whether the welfare LP's constraint matrix stays bihierarchical under matroid constraints.","Inference: the zero-sum separation condition is a general recipe: for any ex post fairness notion with a value-vector set, BoBW existence is equivalent to the convex hull touching the diagonal, which could classify other fairness notions.","Inference: the non-existence example may be useful as a stress test for heuristic or approximate BoBW algorithms, since it is minimal in agents, items, and valuation types."],"forward_implications":["Any two-agent fair division system can simultaneously promise ex ante equal utility and ex post EQ1, with an $O(m)$ algorithm suitable for large item sets.","For binary valuations, randomization costs nothing: the fair lottery can match the social welfare of the best fractional equitable allocation.","For three or more agents, efficient general algorithms are impossible unless P = NP, so practical systems must either restrict valuations or settle for approximate equitability.","The three-agent, four-item counterexample pinpoints the exact boundary of guaranteed existence: two agents always work, three agents with four items can fail.","The $i$-biased EQ1 notion gives a new lever: for two agents, checking both biased allocations certifies BoBW existence, while for three agents the check becomes NP-hard."],"supporting_citations":[{"why":"Supplies the linear-time EQX allocation that the two-agent algorithm starts from.","marker":"[GMT14]"},{"why":"Supplies the bihierarchical decomposition theorem used to round the binary-valuation LP into integral EQ1 allocations.","marker":"[BCKM13]"},{"why":"Defines the best-of-both-worlds paradigm and provides the EF+EF1 existence result that this paper contrasts with.","marker":"[AFSV23]"},{"why":"Introduces the EQ1 relaxation that the ex post guarantee in this paper builds on.","marker":"[FSVX19]"},{"why":"Source of the strong NP-hardness of 3-PARTITION used in the general complexity lower bound.","marker":"[GJ09]"}],"fun_headline_variants":["Fair lotteries: always for two, NP-complete for three","Binary valuations make fair lotteries always possible","Existence of fair lotteries splits at three agents","Geometric test decides when fair lotteries exist"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The paper relies on two cited theorems it does not reprove: that an EQX allocation can be computed in linear time for two agents, and that fractional solutions to linear programs with bihierarchical constraints decompose into whole solutions; if either theorem fails in the relevant setting, the matching existence proof collapses.","fun_headline_variants_meta":{"raw":{"variants":["Fair lotteries: always for two, NP-complete for three","Binary valuations make fair lotteries always possible","Existence of fair lotteries splits at three agents","Geometric test decides when fair lotteries exist"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000843,"raw_usage":{"total_tokens":3688,"prompt_tokens":976,"completion_tokens":2712,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":592,"completion_tokens_details":{"reasoning_tokens":2645}},"tokens_in":592,"tokens_out":2712,"duration_ms":20848,"temperature":1.0,"reasoning_tokens":2645,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:54:12.414720+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all integral allocations of the paper's three-agent, four-item example (Figure 4) and check whether every EQ1 allocation gives agent 1 less than the average of agents 2 and 3, confirming the claimed non-existence; or brute-force search small two-agent normalized instances for any counterexample to the claimed universal existence, which would refute Theorem 2.","supporting_citations":[],"review_version":1}