{"id":"6b41a649-357f-447b-b175-2725d95505f5","arxiv_id":"2411.19881","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"EF1 allocations always exist for identical trilean valuations and for three-agent separable single-peaked valuations, while EFX allocations do not.","lead":"This paper proves that fair allocations (envy-free up to one item) always exist for two new families of valuation functions: identical trilean valuations (where every bundle has one of three integer values) and separable single-peaked valuations for three agents. It also shows that the stronger EFX fairness notion fails for these families.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Positive-trilean EF1 theorem depends on Lemma 19, whose proof is skipped; without a verified classification of EF1 violations, Theorem 13 is unsupported as written.","rationale":"The central claim is that EF1 allocations always exist for identical trilean valuations (Theorems 4 and 13) and for three-agent SSP valuations (Theorem 15). The trilean claim is proved by reduction (Proposition 1) to negative and positive trilean cases, each handled by an algorithm whose correctness rests on a classification of possible EF1 violations (Lemma 5 for negative, Lemma 19 for positive). I read the negative case carefully: Lemma 5 is proved in the appendix with a case analysis that appears complete, and Claims 8–12 connect it to the algorithm. The positive case, however, explicitly skips the proof of Lemma 19. I attempted to find a concrete missing pair—e.g., Zero vs Bad—but this pair is covered by case 1 (Bad, Zero) when the Bad agent is named first, so no immediate counterexample surfaced. Nevertheless, a lemma whose proof is omitted and that is used to certify EF1 of the final allocation is a real gap: a referee cannot verify Theorem 13 without it. The undefined \"M' is trilean\" condition is also a formal defect, but it is likely resolvable by a clarifying definition. The reader's CONDITIONAL verdict correctly captures that the results are plausible and likely correct but not fully supported as written; my stress-test does not move that verdict.","tokens_in":25490,"tokens_out":13751,"duration_ms":114563,"concrete_test":"Write out the full proof of Lemma 19, or verify it computationally: for |M| ≤ 5 enumerate all set functions v : 2^M → {0,1,2} and all ordered pairs of bundles (Ai, Aj) realizing each combination of types from {Fav, Zero, Flex, Res, Res*, Bad}; check that every non-EF1 pair satisfies exactly one of the two conditions in Lemma 19. If any realization of an unlisted type pair is not mutually EF1, the lemma is false and Theorem 13 fails. Also run Algorithm TrileanPosEF1 on these instances to confirm the returned allocation is EF1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix A.3 states Lemma 19, the positive-trilean analogue of Lemma 5, classifying all EF1 violations among the bundle types Fav, Zero, Flex, Res, Res*, and Bad. Its proof is omitted: \"This lemma can be easily proved following the proof of Lemma 5... we will skip the proof.\" Lemma 19 is load-bearing for Theorem 13: Claim 21 uses it to conclude EF1 at termination Lines 9, 11, and 15, and the final step of Theorem 13 invokes it to certify the allocation after FixEF1ViolationsPos (all agents in Fav, Res, Bad). If the two listed violation cases are incomplete, the algorithm can return a non-EF1 allocation. Lemma 5 is fully proved, but the positive case is not, so the paper's existence claim for identical positive trilean valuations is not yet established. A secondary formal gap is the undefined loop condition \"M' is trilean\" in Algorithms 2 and 5 (lines 4 and 4 respectively); on Boolean remaining sets the flexible-set loop's behavior is ambiguous. The primary load-bearing concern is the missing proof of Lemma 19.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies existence of EF1 allocations for two classes of nonmonotone valuations. For identical trilean valuations, where every bundle has value in {0,a,b}, it claims EF1 existence for every number of agents by reducing to negative trilean ({0,-1,1}) and positive trilean ({0,1,2}) cases. The negative case is handled by Algorithm TrileanNegEF1, which allocates favorable, flexible, and resolved sets and then repairs EF1 violations by transferring items from a single bad bundle. The positive case is handled analogously in Appendix A.3 by Algorithm TrileanPosEF1 and FixEF1ViolationsPos. The paper also introduces separable single-peaked (SSP) valuations, with values additive across item types and single-peaked in each type, and proves EF1 existence for three agents (Theorem 15) and for common thresholds (Theorem 14). Finally, it gives a two-agent, three-item example showing that EFX+ allocations need not exist for either class.","tokens_in":25594,"tokens_out":25899,"duration_ms":229087,"significance":"If completed, the trilean results extend the known EF1 existence frontier beyond Boolean and doubly monotone valuations toward arbitrary nonmonotone identical valuations, and the SSP results introduce a new structured class with positive EF1 guarantees. The negative-trilean algorithm and the SSP three-agent proof are substantive and largely convincing. The reduction in Proposition 1 and the EFX non-existence example are useful contributions. The paper is also honest about the exponential query complexity of its trilean algorithms and about the open questions that remain. The main obstruction to accepting the positive-trilean theorem is the omitted proof of Lemma 19, which is load-bearing for Theorem 13.","major_comments":[{"comment":"The proof of Lemma 19 is omitted, with the sentence 'This lemma can be easily proved following the proof of Lemma 5, and its statement is also conclusive from Figure 2. Therefore, we will skip the proof.' This lemma is load-bearing for Theorem 13: Claim 21 invokes it to certify EF1 at termination at Lines 9, 11, and 15; Claim 22 invokes it to restrict all possible EF1 violations to a Flex agent versus a Bad agent; and the final step of Theorem 13 invokes it after FixEF1ViolationsPos. Figure 2 is a summary of the claimed classification, not a proof, and the positive case contains a bundle type, Res* = {1 => {1,2}}, that has no counterpart in Lemma 5. The analogy with Lemma 5 is therefore not automatic. Please supply a complete case analysis for all pairs among Fav, Zero, Flex, Res, Res*, and Bad.","section":"Appendix A.3, Lemma 19"},{"comment":"The loop guard 'M' is trilean' is not defined. Under the paper's own definition, every subset M' of a trilean instance is trilean, so the guard would be trivially true and the flexible-set loop would also run on Boolean-valued remaining item sets, contrary to the surrounding text and the case split at Lines 18--23 of Algorithm 2 and Lines 14--15 of Algorithm 5. If the intended meaning is that the restriction of v to subsets of M' attains all three values (equivalently, M' is not Boolean-valued), that condition needs a formal definition and should be used consistently. As written, the algorithms are not fully specified, and the termination cases on which Theorems 4 and 13 rely cannot be checked.","section":"Algorithms 2 and 5, line 4"}],"minor_comments":[{"comment":"The instruction 'Pick any x /∈ S' should be 'Pick any x ∈ M' \\ S'; otherwise x is not guaranteed to be an unallocated item and the assignment Ai = S ∪ {x} may leave M'.","section":"Algorithms 2 and 5, lines 6 and 5"},{"comment":"The sentence 'If M' is trilean, such a set S must exist' is informal. Once 'trilean' is defined as suggested in the major comments, the existence of the maximal flexible set S, including the case S = ∅, should be stated as a small lemma.","section":"Section 4.2, paragraph before Algorithm 2"},{"comment":"In the both-negative case, the sentence 'since allocation A is EF1 for valuations V′' should explicitly say that the displayed inequality is obtained by applying the EF1 condition to agent j's envy in the transformed instance, where v'(Aj) < v'(Ai). As written, the direction of the inequality can confuse the reader.","section":"Appendix A.1, Proposition 1 proof"},{"comment":"The comment on line 6 of Algorithm 5 says 'v(Ai) = 1→0', but this relies on the absence of favourable sets to rule out v(Ai) = 2→0; it is worth spelling out this one-line justification in the text.","section":"Section 4.3, Algorithm 5"},{"comment":"The captions say the edges 'depict possible EF1 violations'. Since Lemmas 5 and 19 state only necessary conditions, the captions could be clarified to say that the graphs summarize possible violations under the classification, not that every drawn edge is realized for every allocation.","section":"Figures 1 and 2"}],"recommendation":"major_revision","confidential_remarks":"The negative-trilean and SSP contributions appear sound in structure, and the missing proof of Lemma 19 seems repairable, so I do not see grounds for rejection. However, the positive-trilean theorem is currently unsupported as written because its key classification lemma is skipped, and the undefined 'M' is trilean' guard affects both trilean algorithms. I would advise the editor to require a full proof of Lemma 19 and a precise definition of the loop guard before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is a genuine extension of EF1 existence to two new nonmonotone valuation classes. Trilean valuations and separable single-peaked valuations are natural, and the results are new: EF1 for identical trilean for any number of agents, for SSP with three agents, and for SSP with common thresholds. The negative-trilean section is the strongest part. Lemma 5 gives a complete case analysis of EF1 violations, and the FixEF1ViolationsNeg algorithm is detailed and convincing. The SSP section also holds up; the example with identical thresholds does a good job of showing why the old doubly-monotone analysis fails, and the two-phase proof for three agents is a real adaptation. The EFX non-existence example is simple and correct.\n\nThe soft spots are real but likely repairable. The main one is Lemma 19 in the appendix. It classifies EF1 violations for positive trilean and the proof is skipped with the note that it follows Lemma 5. That lemma is load-bearing for Theorem 13; without a written proof, the positive-trilean existence result is unsupported as written. A referee should demand the full proof. The loop condition \"M' is trilean\" in Algorithms 2 and 5 is also not defined for the remaining item set, and on Boolean instances the algorithms could misbehave. And the parenthetical in Section 4 about non-identical trilean valuations is at best ambiguous; read literally it contradicts the open problem stated in Section 7. None of these are deep, but they need to be fixed.\n\nThe citation pattern is fine. The paper builds on prior work by Bérczi et al. and Bhaskar et al., and it is honest about the open problem for arbitrary identical valuations. There are also typos and a comment that the algorithm may need exponentially many queries, which is a limitation but not a correctness issue.\n\nThis paper is for the fair-division community. It deserves serious refereeing, but not acceptance in its current form. If the authors supply the proof of Lemma 19, clarify the loop condition, and correct the parenthetical, the central results are likely to stand. I would send it to peer review and hope the referees push for those fixes.","headline":"New valuation classes and real progress beyond doubly monotone EF1, but the positive-trilean theorem is not yet proven because its central classification lemma is skipped.","tokens_in":26206,"tokens_out":6039,"would_cite":true,"duration_ms":49798,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that envy-free-up-to-one-item (EF1) allocations always exist for identical trilean valuations with any number of agents, and for separable single-peaked valuations with three agents.","keywords":["fair division","EF1","trilean valuations","separable single-peaked valuations","envy-freeness up to one item","EFX nonexistence","indivisible goods","algorithmic fair division"],"falsifier":"The central claim would be refuted by exhibiting an identical negative trilean instance where, in the allocation produced by TrileanNegEF1 before FixEF1ViolationsNeg, there is an EF1 violation that is neither Type 1 nor Type 2; equivalently, a pair of bundles whose types are not connected by an edge in the Lemma 5 graph but for which no single-item removal eliminates envy. For the single-peaked claim, a concrete refutation would be a three-agent, two-type instance where the algorithm's output has an envy that no item from the earlier type can cure.","tokens_in":25207,"feed_emoji":"⚖️","tokens_out":6248,"duration_ms":55345,"temperature":0.7,"pith_summary":"The paper establishes existence of EF1 allocations for two valuation classes that are not covered by doubly monotone utilities. The first class, identical trilean valuations, assigns each bundle one of three values $0$, $a$, or $b$ for any integers $a,b$; the paper proves EF1 allocations exist for any number of agents by reducing to the signed cases $\\{0,-1,1\\}$ and $\\{0,1,2\\}$. The second class, separable single-peaked valuations, partitions items into types, gives each type a single-peaked value in the number of items of that type, and sums across types; the paper proves EF1 allocations exist for three agents, and for any number of agents when all agents share the same threshold per type. It also shows that the stricter EFX notion does not exist for either class, even with two identical agents and three items.","feed_headline":"EF1 fairness proved for trilean and single-peaked tastes","feed_subtitle":"Existence results extend envy-free-up-to-one-item allocations beyond Boolean and doubly monotone valuations.","key_machinery":"For trilean valuations, the machinery is the bundle-type taxonomy built from the child-removal notation $v(S)=a\\to b$ (some child of $S$ has value $b$) and $v(S)=a\\Rightarrow b$ (every child of $S$ has value $b$). Lemma 5 asserts that for negative trilean valuations, an EF1 violation can occur only between a Bad$+$ agent and a Zero, Flex$^-$, Res$^-$, or Bad$^-$ agent, between a Bad$^-$ agent and a Zero, Flex$^+$, Res$^+$, or Bad$^+$ agent, or between a Res$^+$ and a Res$^-$ agent; the positive case (Lemma 19) has an analogous classification. Algorithm FixEF1ViolationsNeg transfers arbitrary items from a bad bundle to a flexible agent until at least one of them reaches a resolved state, and the termination bound is the initial size of the bad bundle. For separable single-peaked valuations, the machinery is the envy graph and top-trading envy graph together with a two-phase allocation per item type; the decisive observation is additivity across types, which makes an earlier-type envy-curing item continue to cure envy after later-type items are added to either bundle.","core_discovery":"The central claim is that EF1 allocations always exist for identical trilean valuations for any number of agents (Theorems 4 and 13), and for separable single-peaked valuations for three agents (Theorem 15), plus for any number of agents when thresholds are common per type (Theorem 14). The trilean proof works by classifying every bundle into Zero, Favourable, Flexible, Resolved, or Bad types, proving a complete characterization of possible EF1 violations, and resolving the remaining violations by moving items from a bad bundle to a flexible agent until one of them becomes resolved. The single-peaked proof uses a two-phase envy-graph algorithm in which valuations are additive across item types; the key step is that an envy-resolving item from an earlier type remains valid after later-type items are assigned, as long as that item is not of the currently assigned type. The paper also gives a two-agent, three-item valuation (empty set value $0$, singleton value $1$, any set of size two or more value $-1$) that is both negative trilean and separable single-peaked and has no $EFX^+_-$ allocation.","pith_inferences":["This is an inference: the bundle-type taxonomy for three values may generalize to valuations with $k$ distinct values, where an algorithm for $(k-1)$-valued instances acts as the subroutine; the paper hints at this recursive direction but does not prove it.","This is an inference: the three-agent bound for separable single-peaked valuations may not be inherent, and a natural testable extension is whether the same two-phase algorithm, or a modest variant, preserves EF1 for four agents when the type-wise analysis does not need the full case split unique to three agents.","This is an inference: because the EFX impossibility example is tiny, practical fair-division tools for such preferences should target EF1; an empirical check of whether the trilean algorithm's potentially exponential query count becomes polynomial for additive trilean or other structured subclasses would be a useful next step."],"forward_implications":["EF1 allocations exist for identical agents whenever every bundle's value lies in a three-element integer set, generalizing the Boolean $\\{0,1\\}$ and $\\{0,-1\\}$ results.","For separable single-peaked valuations, EF1 allocations exist for three agents with different thresholds, and for any number of agents when thresholds are identical within each type.","The same two-agent, three-item valuation rules out $EFX^+_-$ allocations in both trilean and separable single-peaked settings, so EF1 is the strongest envy-based guarantee these classes can promise in general.","The trilean algorithm uses the known Boolean EF1 algorithms as subroutines, providing a concrete template for treating wider discrete valuation ranges."],"supporting_citations":[{"why":"Supplies the Boolean $\\{0,1\\}$ (BooleanEF1) and identical $\\{0,-1\\}$ (NegBooleanEF1) algorithms that the trilean algorithms use as subroutines, and the EFX existence results being extended.","marker":"[14]"},{"why":"Gives the two-phase algorithm for doubly monotone valuations that the common-threshold separable single-peaked result reuses, and whose analysis needs substantial modification for different thresholds.","marker":"[12]"},{"why":"Introduces EF1 and the envy-cycle elimination technique used in the separable single-peaked algorithms.","marker":"[25]"}],"fun_headline_variants":["EF1 exists for trilean and separable single-peaked valuations","New EF1 existence proofs for trilean and single-peaked","Fair division: EF1 proven for trilean and single-peaked tastes","Trilean and single-peaked valuations admit EF1 allocations","EF1 guaranteed for identical trilean and separable single-peaked"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The trilean proof depends on Lemma 5's claim that the listed bundle types cover every possible EF1 violation, and the single-peaked proof depends on the claim that an envy-curing item from an earlier type remains effective after later-type items are added.","fun_headline_variants_meta":{"raw":{"variants":["EF1 exists for trilean and separable single-peaked valuations","New EF1 existence proofs for trilean and single-peaked","Fair division: EF1 proven for trilean and single-peaked tastes","Trilean and single-peaked valuations admit EF1 allocations","EF1 guaranteed for identical trilean and separable single-peaked"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000534,"raw_usage":{"total_tokens":2614,"prompt_tokens":1036,"completion_tokens":1578,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":652,"completion_tokens_details":{"reasoning_tokens":1491}},"tokens_in":652,"tokens_out":1578,"duration_ms":12281,"temperature":1.0,"reasoning_tokens":1491,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:46:08.057577+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The central claim would be refuted by exhibiting an identical negative trilean instance where, in the allocation produced by TrileanNegEF1 before FixEF1ViolationsNeg, there is an EF1 violation that is neither Type 1 nor Type 2; equivalently, a pair of bundles whose types are not connected by an edge in the Lemma 5 graph but for which no single-item removal eliminates envy. For the single-peaked claim, a concrete refutation would be a three-agent, two-type instance where the algorithm's output has an envy that no item from the earlier type can cure.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Boolean $\\{0,1\\}$ (BooleanEF1) and identical $\\{0,-1\\}$ (NegBooleanEF1) algorithms that the trilean algorithms use as subroutines, and the EFX existence results being extended."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the two-phase algorithm for doubly monotone valuations that the common-threshold separable single-peaked result reuses, and whose analysis needs substantial modification for different thresholds."}],"review_version":1}