{"id":"d27ab2f4-e6fa-45b4-874f-9bdde9526135","arxiv_id":"1907.09279","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Introduces GEF1 and related fairness notions for mixed indivisible allocations, with poly-time algorithms for additive cases and coNP-completeness for verification.","lead":"The paper defines relaxed versions of group envy-freeness for indivisible goods and chores, centering on group envy-freeness up to one item (GEF1). It gives polynomial-time algorithms for computing GEF1 allocations under additive utilities and proves checking GEF1 is coNP-complete.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly flags the explicit scoping to additive classes; the abstract-only limitation is the source of the UNVERDICTED verdict, not an unstated flaw in the argument itself. With full text now referenced, the claims remain internally consistent as stated.","tokens_in":1648,"tokens_out":220,"duration_ms":11555,"concrete_test":"Extract the precise definitions of the two natural classes (likely in §3 or §4) and re-derive the running-time bound of the claimed algorithm for one class; confirm it remains polynomial when the class parameters are encoded in unary.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims are scoped explicitly to two natural classes of additive utilities for the poly-time GEF1 algorithms and to the GEF1 decision problem for the coNP-completeness result. The abstract states the restrictions directly; no hidden assumption or internal inconsistency appears in the strongest_claim or the reader's summary of the taxonomy/existence results.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The manuscript introduces stronger and relaxed variants of group envy-freeness suitable for indivisible goods and chores, with particular focus on group envy-freeness up to one item (GEF1). It develops a taxonomy of these fairness notions, analyzes existence guarantees under different preference domains, presents polynomial-time algorithms to compute GEF1 allocations for two natural classes of additive utilities, and proves that verifying whether a given allocation satisfies GEF1 is coNP-complete in the cases of only goods, only chores, or both.","tokens_in":1680,"tokens_out":323,"duration_ms":15878,"significance":"If the algorithmic and complexity results hold, the work makes a solid contribution to fair division by extending group-based fairness concepts to settings with mixed positive and negative utilities. The explicit taxonomy clarifies relationships among notions, the polynomial-time algorithms for the two additive classes provide constructive existence results, and the coNP-completeness result for verification is a useful hardness characterization. These elements are proportionate to the scoped claims and could inform mechanism design for resource allocation.","major_comments":[],"minor_comments":[{"comment":"Abstract: the two natural classes of additive utilities are referenced but not named; naming them (or giving a one-sentence characterization) in the abstract or early introduction would improve readability without altering the technical claims.","section":null},{"comment":"The taxonomy section would benefit from an explicit diagram or table summarizing the implication relationships among the fairness concepts, as the textual description alone can be dense.","section":null}],"recommendation":"minor_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their positive summary of the manuscript and for recommending minor revision. No specific major comments were raised in the report.","responses":[],"tokens_in":1160,"tokens_out":46,"duration_ms":6448,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The key thing here is that the paper defines GEF1 as a relaxed group envy-freeness notion suited to indivisible items that can be goods or chores, and it supplies polynomial-time algorithms for two natural classes of additive utilities plus a coNP-completeness result for verifying the property across goods-only, chores-only, and mixed cases. They also lay out a taxonomy of the fairness concepts and check existence under different preference domains. The algorithmic results are the clearest positive contribution because they directly address the mixed setting where an item can raise or lower an agent's utility. The hardness result gains strength from applying in all three settings rather than just one. The paper does well by keeping the claims scoped to additive utilities in those two classes, which avoids overclaiming. The taxonomy helps organize the space even if some of the notions are incremental extensions of prior group fairness ideas. A soft spot is the restriction of the efficient algorithms to those specific additive classes; outside them the methods may not carry over, though the abstract states the limit plainly so it is not a hidden flaw. The hardness result stands on its own and does not depend on the algorithmic part. This paper is for researchers in algorithmic fair division who already work with indivisible items and envy notions. A reader focused on mechanism design involving chores would pick up the complexity angle and the taxonomy. It deserves a serious referee because the results are concrete, scoped, and address a real extension of existing concepts.","headline":"The paper introduces GEF1 for mixed indivisible goods and chores, with poly-time algorithms under two additive classes and coNP-completeness for checking.","tokens_in":2149,"tokens_out":365,"would_cite":false,"duration_ms":18482,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"Fair-division algorithms for GEF1 allocations under additive utilities; no RS cost or forcing structure","alignment":"orthogonal","rationale":"The paper develops GEF1 relaxations, poly-time algorithms for identical and ternary-symmetric additive utilities, and coNP-completeness of GEF1 verification. Its central objects (group Pareto comparisons, network-flow constructions, Hall-matching arguments) are standard algorithmic game theory and bear no resemblance to J-cost, φ-ladder identities, 8-tick periodicity, or any theorem in the RS forcing chain. The domain (indivisible allocation with mixed goods/chores) lies outside the structural theorems catalogued in IndisputableMonolith/Economics or GameTheory.","tokens_in":61613,"confidence":"high","tokens_out":165,"duration_ms":5464,"cache_read_input_tokens":32896,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"For two classes of additive utilities, polynomial-time algorithms compute group envy-freeness up to one item allocations of indivisible goods and chores.","keywords":["group envy-freeness","GEF1","indivisible goods and chores","additive utilities","fair allocation","polynomial-time algorithms","coNP-complete"],"falsifier":"A concrete instance of agents and items whose additive utilities fall into one of the two classes, yet the algorithm returns an allocation that still leaves group envy after any single-item removal.","tokens_in":2533,"feed_emoji":"⚖️","tokens_out":709,"duration_ms":17498,"temperature":0.7,"pith_summary":"The paper develops notions of group envy-freeness tailored to indivisible items whose value to an agent can be positive or negative. It introduces GEF1 as a relaxed fairness standard and supplies a taxonomy that relates it to other group and individual fairness criteria. Under two natural classes of additive utilities the paper gives algorithms that find a GEF1 allocation in polynomial time. It further shows that deciding whether any given allocation meets the GEF1 standard is coNP-complete, whether the items are all goods, all chores, or a mixture of both.","feed_headline":"Poly-time algorithms compute GEF1 allocations of goods and chores","feed_subtitle":"For two additive utility classes, almost group-envy-free divisions can be found efficiently while verifying the property is hard.","key_machinery":"GEF1 (group envy-freeness up to one item), the requirement that for every pair of agent groups, one group's bundle does not create envy that persists after the removal of at most one item from either bundle.","core_discovery":"We consider a multi-agent resource allocation setting in which an agent's utility may decrease or increase when an item is allocated. We take the group envy-freeness concept that is well-established in the literature and present stronger and relaxed versions that are especially suitable for the allocation of indivisible items. Of particular interest is a concept called group envy-freeness up to one item (GEF1). We then present a clear taxonomy of the fairness concepts. We study which fairness concepts guarantee the existence of a fair allocation under which preference domain. For two natural classes of additive utilities, we design polynomial-time algorithms to compute a GEF1 allocation. We也","pith_inferences":["Practical fair-division software could incorporate the algorithms for routine allocation tasks that involve both desirable and undesirable items.","The verification hardness suggests investigating fixed-parameter tractable algorithms or approximation versions of GEF1 checking.","Results for additive cases may serve as a baseline when extending the same fairness standard to non-additive or combinatorial valuations."],"forward_implications":["A GEF1 allocation can be produced efficiently whenever utilities are additive in either of the two identified classes.","Existence of GEF1 allocations is guaranteed for those utility classes.","Deciding GEF1 satisfaction remains coNP-complete even when all items are goods or all items are chores.","The supplied taxonomy organises the relationships among group and individual fairness notions across mixed good-chore domains."],"fun_headline_variants":["Poly-time GEF1 for goods and chores","Algorithms achieve GEF1 for additive goods and chores","GEF1 verification coNP-complete for indivisible items","Almost group envy-free divisions via efficient algorithms","Taxonomy reveals GEF1 existence in additive domains"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"Agent utilities are additive and belong to one of the two natural classes identified in the paper.","fun_headline_variants_meta":{"raw":{"variants":["Poly-time GEF1 for goods and chores","Algorithms achieve GEF1 for additive goods and chores","GEF1 verification coNP-complete for indivisible items","Almost group envy-free divisions via efficient algorithms","Taxonomy reveals GEF1 existence in additive domains"]},"model":"grok-4.3","cost_usd":0.004657,"raw_usage":{"total_tokens":2289,"prompt_tokens":637,"num_sources_used":0,"completion_tokens":72,"cost_in_usd_ticks":46574500,"prompt_tokens_details":{"text_tokens":637,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1580,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":637,"tokens_out":72,"duration_ms":8655,"temperature":1.0,"reasoning_tokens":1580,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-24T20:14:57.649335+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A concrete instance of agents and items whose additive utilities fall into one of the two classes, yet the algorithm returns an allocation that still leaves group envy after any single-item removal.","supporting_citations":[],"review_version":1}