{"id":"81c28d5a-197d-4542-aadf-09fa1b70d007","arxiv_id":"2502.02815","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper establishes a near-complete implication hierarchy among 22 fairness notions for additive and non-additive valuations over goods, chores, and mixed manna, with an automated inference engine.","lead":"This paper maps how 22 different fairness notions relate to each other in discrete fair division, showing which notions guarantee which others across goods, chores, and mixed manna. It provides a near-complete hierarchy with proofs and counterexamples, plus a web-based inference engine that can extend the map to new settings.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The near-complete hierarchy is built on nonstandard variants of PROP1, PROPx, PROPm, PROPavg, and EFX; the map may not transfer to the standard notions a reader expects.","rationale":"The reader's weakest-assumption analysis correctly identifies that the hierarchy is stated for the paper's own generalized and modified definitions of several standard notions, including strict PROP1, corrected PROPavg/PROPm, and the subset-based EFX. This is the most load-bearing issue because the paper's headline promise is a near-complete map of relations among fairness notions; if the map is only for nonstandard variants, its value to the community is substantially reduced. The paper is transparent about many of these choices and explains motivations in Appendix B, but transparency does not make the map applicable to standard definitions. Example 116 is an explicit place where the paper concedes that its strict PROP1 changes the truth of a non-implication, confirming that the DAGs are definition-dependent. This is not an internal inconsistency: the proofs may be correct for the definitions as stated. The problem is external applicability and the interpretation of the central claim. Since the reader already registered this as the basis for a conditional verdict, my stress-test does not move the verdict; it reinforces the conditional. I do not elevate to reject because the paper's contribution could be reframed as a hierarchy of its generalized notions, and the main additive-goods results for EFX and PROP1 are standard in that flagship setting.","tokens_in":63402,"tokens_out":18969,"duration_ms":179735,"concrete_test":"For the flagship setting of additive goods with equal entitlements, instantiate the standard definitions from the literature for PROP1, PROPx, PROPm, PROPavg, and EFX (e.g., non-strict PROP1 from Aziz et al., original PROPm from Baklanov et al., original PROPavg from Kobayashi-Mahara, and EFX from Caragiannis et al.). Then exhaustively enumerate all allocations for all additive instances with n=3 and m<=5 and re-check every implication edge in Fig. 1a incident to these five notions. If even one edge that holds under the paper's definitions fails under the standard definitions (or vice versa), the near-complete hierarchy does not transfer to the standard notions.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the paper gives a near-complete picture of implications among 22 fairness notions. But several of those notions are deliberately redefined: PROP1 uses strict inequalities (Definition 5, following [39] rather than [34]); PROPx, PROPm, and PROPavg are modified to handle mixed manna and to fix perceived errors in [14,44] (Definitions 16,17); and EFX is a new subset-based generalization (Definition 3) that is only equivalent to the original EFX in special cases such as additive goods. The paper itself notes that Example 116, which shows GAPS+EF1 does not imply PROP1, relies crucially on the strict-inequality variant of PROP1. Thus the DAGs in Fig. 1 and Appendix H are maps of the authors' variants, not of the literature's standard notions in general. A reader who uses the standard non-strict PROP1, the original PROPavg, or the usual EFX for additive goods may find that some displayed edges flip, making the 'near-complete picture' inapplicable to the notions they care about. This is load-bearing because the paper's contribution is precisely to organize the relations among fairness notions as understood by the fair-division community.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies implications among 22 fairness notions in discrete fair division, across goods, chores, and mixed manna, with additive and several non-additive valuation classes. It manually proves a set of implications and counterexamples, then uses a custom inference engine to compute transitive closures and derive a near-complete implication DAG for many settings. The main deliverables are the implication diagrams in Fig. 1 and Appendix H, plus the web-based inference engine.","tokens_in":63684,"tokens_out":24366,"duration_ms":238509,"significance":"If correct, this would be a very useful reference map for fair-division researchers: the scale of the comparison (110 pairs per setting, many settings), the explicit counterexamples, and the reproducible inference engine are real strengths. Several proofs in Appendix C are self-contained, and the authors are careful to state feasibility/open-problem status for the notions. However, the hierarchy is built on deliberately modified definitions of PROP1, PROPx, PROPm, PROPavg, and EFX, and I found concrete chores counterexamples that fail as written. The core additive-goods part may be salvageable, but the chores and subadditive parts need correction and re-verification before the near-complete-picture claim can be accepted.","major_comments":[{"comment":"The chores versions of these counterexamples are invalid. In Example 81 with t=-1, v1(A1)=-4 while w1 v1([m])=-11/2, so A satisfies the first disjunct of PROP (Definition 4) and hence of PROPx (Definition 16); moreover A itself is EFX for agent 1 because agent 1 does not envy agent 2, so A is also MXS-fair to agent 1. Thus the row 'EF1 implies neither MXS nor PROPx' is not witnessed for chores. Similarly, in Example 83 with t=-1, v1(A1)=-5 >= -13/2, so A is PROPx, contradicting the claim that 'MXS does not imply PROPx' for negative bivalued marginals. Since Table 3 explicitly marks these rows as holding for both positive and negative bivalued marginals, the chores DAG (Fig. 1b) currently rests on unsupported non-implications. Please supply valid chores counterexamples or remove the negative-sign claims.","section":"Appendix D.3 (Examples 81 and 83; Table 3)"},{"comment":"This counterexample is false as written. With v(S)=ceil(|S|/4) and A=(2,5), we have v1(A1)=ceil(2/4)=1 and v1([7])/2=ceil(7/4)/2=1, so agent 1 is PROP-fair and therefore PROP1-fair by the first disjunct of Definition 5, even under the strict version. The note that the strict inequality is 'crucial' is therefore incorrect. Consequently the claimed non-implication GAPS+EF1 does not imply PROP1 for subadditive valuations is unproved, and any DAG edge derived from this counterexample in Fig. 13 needs re-examination.","section":"Appendix E.4 (Example 116; Table 3)"},{"comment":"The relation map is stated for modified versions of several literature notions, and this limits transfer to the notions a reader may expect. PROP1 uses strict inequalities (Definition 5), PROPx/PROPm/PROPavg are altered for mixed manna, and PROPavg in Definition 17 averages over |T| instead of n-1 specifically to force PROPx implies PROPavg. The paper itself explains in Appendix B.6.2 that the original PROPavg of [44] does not satisfy that implication. Hence Fig. 1's edges involving PROPavg and PROP1 are not claims about the original published notions in general. The abstract and Section 1.1 should state this caveat prominently, or the paper should include a dictionary of which edges survive for the standard definitions; otherwise the 'near-complete picture' can be misread as applying to the literature's notions.","section":"Appendix B.4 and B.6 (Definitions 5, 16, 17; Fig. 1)"}],"minor_comments":[{"comment":"The shorthand 'bival *' and the asterisk explanations are hard to parse; please expand the affected settings explicitly in each row or provide a clearer legend.","section":"Table 3 and footnotes"},{"comment":"In the t=-1 case, the sentence 'agent 1 doesn't have an M1S-certificate for A' appears to concern agent 2; as written it is confusing and should be rephrased.","section":"Lemma 82 proof"},{"comment":"The example should either be corrected to a genuine non-implication or deleted; the current text is internally inconsistent with Definition 5, and the claimed role of strict inequalities needs to be re-established.","section":"Example 116"},{"comment":"After fixing the counterexamples above, the inference engine inputs and all affected DAGs (especially Fig. 1b and Fig. 13) should be regenerated, since the engine propagates any incorrect non-implication through transitive closure.","section":"Appendix H / inference inputs"}],"recommendation":"major_revision","confidential_remarks":"The pattern of failures in the t=-1/chores variants suggests that a systematic audit of all counterexamples marked as holding for negative or bivalued marginals is needed before the chores hierarchy can be trusted. I did not check every t=-1 instance exhaustively, but the ones I checked are not isolated typos: they invalidate several rows of Table 3."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is a large, systematic map of implications among 22 fairness notions, with many new counterexamples and a working inference engine. It is worth having on your shelf, but the map is for the authors' variants of several standard notions, not the originals.\n\nThe genuinely new part is the scope. Previous work covered at most a handful of notions; this paper covers 22 across goods, chores, mixed manna, and multiple valuation classes. Most counterexamples are new, and the inference engine (with released code) is a real tool that automates transitive closure and counterexample propagation. Most implication proofs in Appendix C are self-contained.\n\nThe soft spot is definitional, and it matters. The near-complete DAGs are built from modified definitions: PROP1 uses strict inequalities; PROPx, PROPm, PROPavg are adapted and 'corrected'; EFX is a new subset-based generalization. The paper is transparent about this and explains the choices, but the consequence is that the central claim—a near-complete picture for fair division—is only true for these variants. For instance, the counterexample that GAPS+EF1 does not imply PROP1 (Example 116) relies on the strict PROP1; with the standard non-strict definition, that edge may flip. Likewise, their EFX only coincides with the original EFX under submodular or strictly signed marginals. Readers using standard definitions will need to re-check the affected edges. That is a real limitation, though not a fatal one.\n\nA second, smaller issue: one load-bearing implication (Lemma 33, MXS => PROP1) is cited from the authors' own prior work without proof, and some other results are proof sketches. For a reference work, I would have liked that lemma proved or clearly marked as imported.\n\nOverall, the paper is honest, detailed, and useful as a map for the authors' definitions. It is not the final word on the relations among the standard notions. The right audience is researchers who already know which variant of PROP1 or EFX they care about and want a comprehensive graph for that variant. I would send it to a serious referee; the referee should ask the authors to state explicitly which edges depend on the modified definitions, and to prove or clearly flag the imported Lemma 33.","headline":"A useful, systematic implication map for 22 fairness notions, but the near-complete picture is for the authors' redefined variants, not the standard definitions.","tokens_in":64173,"tokens_out":2962,"would_cite":true,"duration_ms":28810,"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":"This paper delivers a near-complete map of which of the 22 fairness notions in discrete fair division imply which, proved or refuted pair by pair across goods, chores, and mixed manna.","keywords":["fair division","indivisible items","fairness notion implications","EFX","proportionality","maximin share","anyprice share","inference engine"],"falsifier":"Walk through all pairs of the 22 notions in the additive-goods, equal-entitlements setting and compare each with the goods diagram: any pair that is neither connected by a path in the diagram nor matched by a counterexample from the paper's tables — other than the single acknowledged open question of whether MXS implies EEF1 for more than two agents — refutes the near-completeness claim. A second check is to rebuild one engine-derived edge by hand: the non-implication EEFX $\\not\\Rightarrow$ PROPavg rests on Example 89, so verifying that instance really is APS-fair (hence EEFX-fair) and not PROPm-fair under the paper's own definitions tests whether the inference engine propagates soundly.","tokens_in":63199,"feed_emoji":"⚖️","tokens_out":14987,"duration_ms":131262,"temperature":0.7,"pith_summary":"Fair division of indivisible items among agents has produced many competing fairness notions — envy-based relaxations such as EF1 and EFX (envy-free up to one, or up to any, item), proportionality relaxations such as PROP1 and PROPx, and share-based benchmarks such as the maximin share and the anyprice share — and it has been unclear how they relate. This paper tries to settle the relation problem: for 22 notions, it treats an implication as the claim that every allocation satisfying one notion also satisfies another, and then, for almost every ordered pair, either proves the implication or constructs an allocation that is fair under the first notion but not the second. The result is a near-complete hierarchy, summarized in implication diagrams for goods, chores, and mixed manna under additive valuations, with additional diagrams for submodular, subadditive, and general valuations. A reader should care because the map tells practitioners and theorists when a guarantee for a weaker notion automatically transfers to a stronger one and where the notions genuinely diverge; the paper also supplies an inference engine that derives many of the relations automatically and can be reused outside fair division.","feed_headline":"22 fairness notions ranked in one near-complete map","feed_subtitle":"For goods, chores, and mixed manna, almost every implication is proved or disproved.","key_machinery":"The load-bearing object is the implication relation itself: a notion $F_1$ implies $F_2$ when every $F_1$-fair allocation is also $F_2$-fair, so the whole contribution is a directed graph whose vertices are fairness notions and whose edges are proved implications, with counterexamples marking the missing edges. To get the graph at scale, the paper first proves a batch of implications and non-implications by hand, then feeds them to an inference engine that computes the transitive closure of implications and propagates counterexamples upward along implication chains, producing the final directed acyclic graphs. Two definitional moves carry much of the weight: the paper extends every notion — including EFX, PROPx, PROPm, and PROPavg — to the general mixed-manna, unequal-entitlements setting, and it adopts a slightly strengthened PROP1 with strict inequalities plus corrected versions of PROPm and PROPavg, so that the map's edges (for instance EFX implies PROPavg and PROPx implies PROPavg) are statements about these generalized definitions rather than about the originals.","core_discovery":"The paper's central claim is that the fairness-notion landscape for discrete fair division is almost fully understood: with a few explicitly listed exceptions, every pair of the 22 notions it considers is either known to be related by an implication or known not to be, via a counterexample. For the main setting — additive valuations with equal entitlements — the implication graph for goods is closed except for one open edge (whether MXS implies EEF1 for more than two agents), the chore graph has no open edges, and the mixed-manna graph has none; the unequal-entitlements settings each carry at most three open pairs, and several binary-marginal settings are fully resolved. The same near-completeness is claimed for submodular goods (one open edge), subadditive goods (one open edge), and general goods (complete). The paper also attaches a feasibility label to each notion — feasible, infeasible, or open — and its diagrams show that for additive goods and chores with equal entitlements the only feasibilities in doubt are EFX and PMMS, two of the field's most studied open problems.","pith_inferences":["My inference: because the map's edges are drawn for the paper's generalized definitions, exporting its conclusions to the standard definitions from the literature requires re-checking the affected lemmas; the paper flags where strictness matters, but the printed diagrams themselves are statements about its own variants.","My inference: the conditional-predicate machinery is not tied to fair division — any domain whose predicates, implications, and counterexamples can be conditioned on a partially ordered family of settings admits the same transitive-closure engine, a direction the paper suggests but does not develop.","My inference: the map makes a research-program prediction — since EFX and PMMS are the only open feasibility vertices for additive goods, an infeasibility proof for either would cascade downward into infeasibility for every notion above it in the diagram, giving a clean way to refute whole families at once."],"forward_implications":["A researcher proving an existence or algorithmic result for a weaker notion can immediately extend it to every stronger notion on the map, and a proven infeasibility for a strong notion rules out feasibility for everything above it.","For additive goods and chores with equal entitlements, the only fairness notions whose feasibility remains open are EFX and PMMS, so the map isolates where the field's hardest existence questions concentrate.","The strict-inequality definitions of PROP1, PROPx, PROPm, and PROPavg mean the map's edges involving proportional notions are statements about these strict variants; the paper notes that nearly all of its results hold for both strict and non-strict versions and flags where they do not, as in Example 116, which relies on strictness.","The inference engine needs only a few hand-proved base relations when a new notion is added — adding PROPavg required five results, and the engine inferred the rest — so the map can be extended incrementally as new fairness notions appear.","The engine itself is a general tool for conditional predicate implications: given a partially ordered family of settings, it outputs all implications and counterexamples that follow by transitive closure, a capability the paper demonstrates on fair division but describes as applicable more broadly."],"supporting_citations":[{"why":"Supplies the original EFX definition and the PMMS-not-MMS counterexample used in Example 88; the paper's Definition 3 generalizes this notion to mixed manna.","marker":"[29]"},{"why":"Introduces the anyprice share and the results relating it to MMS and PROP (Lemmas 45, 49, 51), plus the instance where APS strictly exceeds MMS behind Examples 86–87.","marker":"[13]"},{"why":"Introduces the epistemic and minimum-share notions and supplies MMS implies EEFX and MXS implies PROP1, which several derived edges of the diagrams build on.","marker":"[28]"},{"why":"Source of the strict-inequality PROP1 definition (Definition 5) that the paper adopts, which changes which counterexamples go through.","marker":"[39]"},{"why":"Introduces PROPm; the paper corrects its minimax-item condition and extends it to mixed manna in Definition 17.","marker":"[14]"},{"why":"Introduces PROPavg; the paper fixes the original averaging error so that PROPx implies PROPavg holds as claimed.","marker":"[44]"},{"why":"Supplies the EEFX implies PROPx lemma for chores (Lemma 37), a load-bearing edge of the chores diagram.","marker":"[47]"},{"why":"Provides the MEFS implies PROP and EF implies GPROP bridges (Lemmas 28–29) between the envy and proportionality families.","marker":"[24]"},{"why":"Provides the MXS-not-PROPx counterexample (Example 83) that separates the minimum-share family from the proportional family.","marker":"[27]"},{"why":"Supplies the EF1 and maximin-share definitions whose partition characterization is used throughout Appendix C and anchors the envy and share families.","marker":"[26]"}],"fun_headline_variants":["22 fairness notions: near-complete map of implications","Almost every fairness relation proved or disproved","Fair division: nearly all implication pairs settled","One open edge: fairness implications nearly fully mapped"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hierarchy is drawn for the paper's own generalized definitions of the fairness notions — EFX as in Definition 3, PROP1 with strict inequalities, and corrected PROPx, PROPm, and PROPavg — so a reader using the original definitions from the cited literature cannot take every edge of the map at face value; some edges were proved only for these variants, and at least one counterexample (Example 116) depends on the strict-inequality convention.","fun_headline_variants_meta":{"raw":{"variants":["22 fairness notions: near-complete map of implications","Almost every fairness relation proved or disproved","Fair division: nearly all implication pairs settled","One open edge: fairness implications nearly fully mapped"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000244,"raw_usage":{"total_tokens":1551,"prompt_tokens":984,"completion_tokens":567,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":600,"completion_tokens_details":{"reasoning_tokens":509}},"tokens_in":600,"tokens_out":567,"duration_ms":5766,"temperature":1.0,"reasoning_tokens":509,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T11:00:33.130079+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Walk through all pairs of the 22 notions in the additive-goods, equal-entitlements setting and compare each with the goods diagram: any pair that is neither connected by a path in the diagram nor matched by a counterexample from the paper's tables — other than the single acknowledged open question of whether MXS implies EEF1 for more than two agents — refutes the near-completeness claim. A second check is to rebuild one engine-derived edge by hand: the non-implication EEFX $\\not\\Rightarrow$ PROPavg rests on Example 89, so verifying that instance really is APS-fair (hence EEFX-fair) and not PROPm-fair under the paper's own definitions tests whether the inference engine propagates soundly.","supporting_citations":[{"cited_title":"Fair-share allocations for agents with arbitrary entitlements","cited_arxiv_id":null,"evidence_quote":"Introduces the anyprice share and the results relating it to MMS and PROP (Lemmas 45, 49, 51), plus the instance where APS strictly exceeds MMS behind Examples 86–87."},{"cited_title":"New fairness concepts for allocating indivisible items","cited_arxiv_id":null,"evidence_quote":"Introduces the epistemic and minimum-share notions and supplies MMS implies EEFX and MXS implies PROP1, which several derived edges of the diagrams build on."},{"cited_title":"Low communication protocols for fair allocation of indivisible goods","cited_arxiv_id":null,"evidence_quote":"Source of the strict-inequality PROP1 definition (Definition 5) that the paper adopts, which changes which counterexamples go through."},{"cited_title":"Achieving pro- portionality up to the maximin item with indivisible goods","cited_arxiv_id":null,"evidence_quote":"Introduces PROPm; the paper corrects its minimax-item condition and extends it to mixed manna in Definition 17."},{"cited_title":"Proportional allocation of indivisible goods up to the least valued good on average","cited_arxiv_id":null,"evidence_quote":"Introduces PROPavg; the paper fixes the original averaging error so that PROPx implies PROPavg holds as claimed."},{"cited_title":"Almost (weighted) proportional allocations for indivisible chores","cited_arxiv_id":null,"evidence_quote":"Supplies the EEFX implies PROPx lemma for chores (Lemma 37), a load-bearing edge of the chores diagram."},{"cited_title":"Characterizing conflicts in fair division of indivisible goods using a scale of criteria","cited_arxiv_id":null,"evidence_quote":"Provides the MEFS implies PROP and EF implies GPROP bridges (Lemmas 28–29) between the envy and proportionality families."},{"cited_title":"New Fairness Concepts for Allocating Indivisible Items","cited_arxiv_id":"2206.01710","evidence_quote":"Provides the MXS-not-PROPx counterexample (Example 83) that separates the minimum-share family from the proportional family."},{"cited_title":"The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes","cited_arxiv_id":null,"evidence_quote":"Supplies the EF1 and maximin-share definitions whose partition characterization is used throughout Appendix C and anchors the envy and share families."}],"review_version":1}