{"id":"790d4f74-273e-4e9c-83d3-82aa159dddea","arxiv_id":"2506.21727","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper introduces strong simultaneous envy-freeness up to c goods for multidimensional fair division, proves existence bounds independent of the item count, and shows NP-hardness for checking weak and strong sEF1.","lead":"This paper studies how to divide indivisible goods fairly when agents judge bundles on several criteria at once, introducing a new 'strong' version of envy-freeness-up-to-c-items. It proves that fair allocations with a bounded number of removals always exist, independent of how many goods are being divided, and that checking some versions is computationally hard.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 11's strong-sEFc decision algorithm is incomplete: its disjointness condition on witness sets excludes valid allocations and can return false negatives.","rationale":"I reviewed the central existence results and found no load-bearing flaw. In Theorem 9 the extreme-point counting is valid because a non-integral item contributes at least two positive coordinates, so at most n(n−1)ℓ items can be fractional; the subsequent compensation argument holds for any partition with |F_i| ≤ (n−1)ℓ since |F\\F_i| ≤ (n−1)^2ℓ follows from the same upper bound on the other parts. The reader's weakest assumption about the sparse extreme point therefore checks out. The genuinely load-bearing weakness is the strong-sEFc checking algorithm in Theorem 11: the imposed disjointness of witness sets is an extra condition absent from Definition 2, and it can reject valid allocations. My concrete counterexample (3 agents, 1 dimension, c=2) shows a strong sEF2 allocation where the two envious agents must both remove the same pair {a,b}, so the algorithm would return a false negative. This does not undermine the main existence theorems, but it invalidates a claimed algorithmic contribution. The verdict should remain CONDITIONAL: accept after correcting Theorem 11 and the textual errors (e.g., the 'strong' vs 'weak' slip in Theorem 10 and the S1/S2 typo in Theorem 13's converse direction).","tokens_in":18326,"tokens_out":31661,"duration_ms":297514,"concrete_test":"Run the Theorem 11 DP on the instance with n=3, ℓ=1, c=2: M={a,b,c,d,e,f,g,h} with v(a)=v(b)=10 and all other values 0, identical across agents. If the algorithm returns 'no' when the valid strong sEF2 allocation A1={c,g}, A2={d,h}, A3={a,b,e,f} exists, the incompleteness is confirmed. Alternatively, check analytically that any witness collection for this allocation must have X_{1,3}=X_{2,3}={a,b}, violating the algorithm's disjointness constraint.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing weakness is in the decision algorithm for strong sEFc (Theorem 11), not in the existence theorems. The proof enumerates witness collections (X_{ii'}) and imposes the condition that for distinct agents i and ι, (∪_{i'} X_{ii'}) ∩ (∪_{ι'} X_{ιι'}) = ∅. This disjointness is not part of Definition 2: removal sets for different ordered pairs may overlap, and the definition only requires existence of some set per pair. Moreover, the containment condition stated as A_i ⊇ ∪_{i'} X_{ii'} is inconsistent with the later verification V_{iik} ≥ V_{ii'k} − Σ_{j∈X_{i,i'}} v_{ijk}, which treats X_{i,i'} as a subset of A_{i'}. The disjointness condition is restrictive in exactly the wrong way: it can exclude valid allocations. For instance, with n=3, ℓ=1, c=2, and items a,b of value 10 and c,d,e,f,g,h of value 0, the allocation A1={c,g}, A2={d,h}, A3={a,b,e,f} is strong sEF2, but the only removal sets that eliminate envy from agents 1 and 2 toward agent 3 are both {a,b}, so the required disjointness fails. The algorithm can therefore return false negatives. This affects a claimed algorithmic contribution of the paper; the existence results (Theorems 7 and 9) remain sound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies multidimensional fair division of indivisible goods, introducing weak and strong simultaneous envy-freeness up to c goods (sEFc). It proves existence bounds on c that are independent of the number of items: a strong sEF(2ℓ-1) allocation for two agents (Theorem 7), a strong sEF(n²ℓ²) allocation for general n (Theorem 9), and matching-style lower bounds (Theorems 5 and 6). It also gives dynamic-programming decision algorithms for weak and strong sEFc (Theorems 10 and 11), and NP-completeness results for deciding the existence of weak sEF1 and strong sEF1 allocations (Theorems 12 and 13) and for verifying strong sEFc (Theorem 15). The related-work discussion connects the model to group fair division and discrepancy theory.","tokens_in":18515,"tokens_out":17006,"duration_ms":176458,"significance":"If the results hold, the paper makes a valuable contribution to multi-attribute fair allocation. The existence theorems are elegant: they combine LP rounding and discrepancy-based lower bounds to give guarantees on the relaxation parameter c that do not depend on the item count, and the proofs are self-contained. The NP-hardness reductions in Theorems 12, 13, and 15 are also well structured and appear sound. However, one of the central algorithmic claims—the polynomial-time decision procedure for strong sEFc in Theorem 11—has a genuine correctness gap, so the paper needs revision before its full set of claims can be accepted.","major_comments":[{"comment":"The decision algorithm for strong sEFc is not sound as written because it imposes a disjointness condition that is not part of Definition 2. The proof enumerates collections (X_{ii'}) and requires that for distinct agents i and ι, (∪_{i'} X_{ii'}) ∩ (∪_{ι'} X_{ιι'}) = ∅. Definition 2 only requires that for each ordered pair (i,i') there exists some set X_{ii'} ⊆ A_{i'} of size at most c; there is no requirement that the removal sets for different ordered pairs be disjoint. This condition can exclude valid allocations. For example, with n=3, ℓ=1, c=2, items a,b of value 10 and c,d,e,f,g,h of value 0, the allocation A1={c,g}, A2={d,h}, A3={a,b,e,f} is strong sEF2: the envy of agents 1 and 2 toward agent 3 is eliminated only by removing both a and b, so the only valid removal sets for the pairs (1,3) and (2,3) are both {a,b}. The algorithm's disjointness condition rejects this collection, producing a false negative.","section":"Theorem 11"},{"comment":"Independently of the disjointness issue, the containment condition stated in the proof is inconsistent with Definition 2. The proof imposes A_i ⊇ ∪_{i'} X_{ii'} for each agent i, but Definition 2 requires X_{ii'} ⊆ A_{i'}—the removal set must be a subset of the envied agent's bundle, not of the envious agent's bundle. This index swap is not merely cosmetic: the verification step V_{iik} ≥ V_{ii'k} − Σ_{g_j∈X_{i,i'}} v_{ijk} only makes sense if X_{i,i'} is contained in A_{i'}, but the dynamic program tracks only aggregate valuation profiles and cannot enforce such subset relations. Consequently, the claimed polynomial-time procedure for checking strong sEFc is not established by the proof.","section":"Theorem 11"}],"minor_comments":[{"comment":"The text says 'poynomial-time computability'; the intended word is 'polynomial-time'.","section":"Section 4, introduction"},{"comment":"The definition of A2 in the converse direction says A2 = {g_j : j∈S1} ∪ {g_{n+2}}; this should read {g_j : j∈S2} ∪ {g_{n+2}} for the stated valuations to hold.","section":"Theorem 13, converse direction"},{"comment":"The expression 'Σ_{j∈g_j∈X_{i,i'}} v_{ijk}' is malformed; it should be 'Σ_{g_j∈X_{i,i'}} v_{ijk}'.","section":"Theorem 11, verification line"},{"comment":"The sentence beginning 'We assume that N=[n], M={g1,...,g_m}, L=[ℓ], and that for each agent i∈N and item g∈M.' is incomplete and should be finished or removed.","section":"Theorem 10, proof"},{"comment":"Even if the disjointness condition were removed, the statement 'A_i ⊇ ⋃_{i'∈N} X_{ii'}' should be replaced by the correct subset relation 'A_{i'} ⊇ ⋃_{i∈N} X_{ii'}' (or an equivalent formulation) to match Definition 2.","section":"Theorem 11, containment statement"}],"recommendation":"major_revision","confidential_remarks":"The flaw in Theorem 11 is substantive because the abstract and introduction explicitly claim algorithms for checking strong sEFc. However, the existence theorems (5–9) and the hardness reductions (12, 13, 15) appear sound and are the main theoretical contributions. I therefore recommend major revision rather than rejection: the strong-sEFc decision algorithm needs to be corrected or the claim appropriately weakened, and the proof should be reworked to respect Definition 2."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid paper with a genuinely useful core and one load-bearing algorithmic claim that is not correct as written. The strong sEFc notion is new and well motivated, and the two LP-rounding existence results are the real contributions. The n-agent bound (n²ℓ²) and the two-agent bound (2ℓ−1) are item-count-independent, and the proofs go through by standard extreme-point counting. The hardness results (weak sEF1 via MNAE3SAT with identical binary valuations, strong sEF1 via Partition, strong sEFc verification via 3DM) are also nice and appear correct.\n\nThe soft spot is Theorem 11, the claimed polynomial-time decision algorithm for strong sEFc. The proof enumerates witness collections X_{ii'} and imposes a disjointness condition on the unions over i' for different agents i. That condition is not part of the definition of strong sEFc — removal sets for different ordered pairs can overlap. The proof also writes a containment condition A_i ⊇ ⋃_{i'} X_{ii'} that is inconsistent with the later verification step, which treats X_{i,i'} as a subset of A_{i'}. The stress-test counterexample is correct: with three agents, one dimension, c=2, items {a,b} of value 10 and six zero-value items, the allocation A1={c,g}, A2={d,h}, A3={a,b,e,f} is strong sEF2, but the only removal sets for agents 1 and 2 toward agent 3 are both {a,b}, so the required disjointness fails. The algorithm can return false negatives. This is a genuine completeness bug, though it does not affect the existence theorems or the hardness results.\n\nThere are also minor textual issues: the last sentence of Theorem 10 says 'strong sEFc' where it should say 'weak sEFc', and there are a few typos. These are cosmetic.\n\nWho should read this: anyone working on multidimensional or group fair division. The existence bounds are the takeaway. The bug in Theorem 11 is fixable — you need to allow overlapping witness sets and track enough information to verify each ordered pair independently — but as written that theorem is not reliable.\n\nOn balance, this deserves serious refereeing. The core results are new and mostly correct; the decision algorithm needs revision. I would accept it for review and let the authors repair Theorem 11 and the typos.","headline":"Solid existence and hardness results for multidimensional fair division, but Theorem 11's strong-sEFc decision algorithm has a genuine completeness bug that needs fixing.","tokens_in":19176,"tokens_out":5580,"would_cite":true,"duration_ms":54367,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","68Q17","90C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every multidimensional fair-division instance with $n$ agents and $\\ell$ criteria admits a simultaneously envy-free allocation up to $n^2\\ell^2$ goods, computable in polynomial time, and that with two agents the…","keywords":["fair allocation","indivisible goods","envy-freeness up to c goods","multidimensional valuations","simultaneous envy-freeness","linear programming","NP-completeness"],"falsifier":"Search exhaustively over small binary instances with, say, two agents and two dimensions, enumerating every allocation and checking whether any instance has no strong sEF(3) allocation; one such instance would falsify Theorem 7. For the general claim, a counterexample would be any small instance with three agents and two dimensions in which every allocation leaves some agent envying another by more than $n^2\\ell^2 = 36$ items after any allowed removal set.","tokens_in":18030,"feed_emoji":"⚖️","tokens_out":10340,"duration_ms":113674,"temperature":0.7,"pith_summary":"This paper asks how much envy survives when indivisible items are allocated to agents who evaluate each item along several independent criteria at once. It introduces two relaxations of envy-freeness: weak sEFc, which lets the agent remove a different set of up to c goods per criterion, and strong sEFc, which requires one set of at most c goods whose removal eliminates envy in every criterion. The main positive results are that a strong sEF($2\\ell-1$) allocation always exists with two agents, and a strong sEF($n^2\\ell^2$) allocation always exists with any number of agents; both are computable in polynomial time. Because the relaxation parameter depends only on the number of agents and the number of criteria, these guarantees hold no matter how many goods are being divided. The paper also gives lower bounds showing that some dependence on the number of criteria is unavoidable, and it proves that deciding whether weak or strong sEF1 allocations exist is NP-complete even in very restricted instances.","feed_headline":"Envy in multi-criteria allocations is fixed by removing n²ℓ² items","feed_subtitle":"For any number of agents and criteria the near-envy-free split exists and is found in polynomial time.","key_machinery":"The central object is the pair of relaxations weak sEFc and strong sEFc: for every agent pair and dimension, envy must vanish after deleting up to c goods, with weak sEFc allowing a different deletion set per dimension and strong sEFc requiring a single deletion set for all dimensions. The main workhorse is an envy-constrained or proportionality-constrained polytope whose extreme points are sparse. For two agents the feasible region is the set of fractional allocations satisfying $\\sum_j v_{1jk}(2x_j-1) \\ge 0$ and $\\sum_j v_{2jk}(1-2x_j) \\ge 0$ for every dimension $k$; every basic solution has at most $2\\ell-1$ fractional coordinates, so removing exactly those fractional items from the other agent's bundle eliminates all envy. For the general case the polytope $P$ is defined on the remaining items $R$ by the proportional constraints $\\sum_{g\\in R} v_i(g)_k(x_{ig}-x_{i'g}) \\ge 0$ together with partition constraints; an extreme point has at most $m'+n(n-1)\\ell$ nonzero coordinates, meaning at most $n(n-1)\\ell$ items are split between agents. A second mechanism is the discrepancy lower bound: the weak nonexistence result encodes an orthogonal $\\pm1$ matrix of order $r$ as valuations and uses the fact that every $\\pm1$ signing of its columns has discrepancy at least $\\sqrt{r}/2$, which exceeds $c$ unless $r = O(c^2)$.","core_discovery":"The core claim, on the paper's own terms, is that simultaneous envy-freeness is attainable once the relaxation parameter $c$ is allowed to grow with the number of agents $n$ and the number of dimensions $\\ell$, but not with the number of items. With two agents, rounding a basic optimal solution of a small linear program yields a strong sEF($2\\ell-1$) allocation. With $n$ agents, the paper first gives each agent the $(n-1)^2\\ell$ most valuable items in each dimension, then rounds an extreme point of a polytope describing proportional fractional allocations of the remaining items; the sparsity of that extreme point bounds the number of fractional items by $n(n-1)\\ell$, yielding a strong sEF($n^2\\ell^2$) allocation in polynomial time. Since strong sEFc implies weak sEFc, these are also weak existence results. The paper complements these with lower bounds: no weak sEFc guarantee is possible when $c = \\Omega(\\sqrt{\\ell})$, and no strong sEFc guarantee is possible when $c < \\lceil \\ell/2 \\rceil$; it also proves NP-completeness for checking the existence of weak sEF1 and strong sEF1 allocations.","pith_inferences":["The large gap between the lower bound $\\Omega(\\sqrt{\\ell})$ and the upper bound $n^2\\ell^2$ suggests the true worst-case $c$ is much closer to linear in $\\ell$ for a fixed number of agents, as the two-agent bound $2\\ell-1$ already shows.","The matrix-discrepancy lower bound is a discrepancy statement, and sharper discrepancy bounds for multicolor signings would immediately translate into stronger impossibility results for weak sEFc.","The pre-assignment plus extreme-point rounding scheme should transfer to the simultaneously proportional relaxations the paper defines in its conclusion, giving analogous sPROP-type guarantees.","Since verification of strong sEFc is hard only when $c$ is part of the input, the decision algorithm of Theorem 11 likely leaves room for fixed-parameter tractable algorithms parameterized by $c$ together with $n$ and $\\ell$."],"forward_implications":["With two agents, the polynomial-time strong sEF($2\\ell-1$) guarantee means fairness in every criterion can be certified by deleting a number of goods that depends only on the number of criteria.","With any number of agents, strong sEF($n^2\\ell^2$) allocations always exist and are efficiently computable, providing an item-count-independent existence guarantee for simultaneous envy-freeness.","Because strong sEFc implies weak sEFc, the same existence results supply weak sEF bounds, and the two-agent case upgrades a known existence-only weak bound to polynomial-time computability.","The dynamic programming checks show that for constant $c$, $n$, and $\\ell$ with unary valuations, deciding the existence of a weak sEFc allocation is polynomial-time solvable.","At $c=1$, both existence checks become intractable: weak sEF1 is strongly NP-complete even with two identical agents and binary values, and strong sEF1 is NP-complete with two agents and two dimensions."],"supporting_citations":[{"why":"Introduces the weak sEFc relaxation and supplies the three-dimension instance with no weak sEF1 allocation that motivates the paper.","marker":"[10]"},{"why":"Supplies the discrepancy fact for orthogonal $\\pm1$ matrices that the weak lower bound relies on.","marker":"[1]"},{"why":"Provides the group-fairness discrepancy construction that the weak sEF nonexistence result is essentially equivalent to.","marker":"[26]"},{"why":"Provides the standard linear-programming facts about basic feasible solutions and polynomial-time solvability used in Theorems 7 and 9.","marker":"[8]"},{"why":"Supplies the NP-completeness of monotone not-all-equal 3-SAT used in the weak sEF1 hardness reduction.","marker":"[30]"},{"why":"Supplies the NP-completeness of Partition and 3-Dimensional Matching used for the strong sEF1 and strong sEFc verification hardness results.","marker":"[16]"}],"fun_headline_variants":["n²ℓ² removals fix multidimensional envy in polynomial time","Multidimensional envy-free allocation exists with n²ℓ² item removals","Strong sEF(n²ℓ²) allocations are poly-time computable","Poly-time fair allocation across attributes: n²ℓ² removals handle envy","Envy-free up to n²ℓ² items: multidimensional fair division solvable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central bet is that an optimal fractional allocation can always be chosen with only a bounded number of partially assigned goods; if every optimal fractional solution had many split goods, the polynomial-time existence guarantee stated in the paper would not follow.","fun_headline_variants_meta":{"raw":{"variants":["n²ℓ² removals fix multidimensional envy in polynomial time","Multidimensional envy-free allocation exists with n²ℓ² item removals","Strong sEF(n²ℓ²) allocations are poly-time computable","Poly-time fair allocation across attributes: n²ℓ² removals handle envy","Envy-free up to n²ℓ² items: multidimensional fair division solvable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000491,"raw_usage":{"total_tokens":2478,"prompt_tokens":1073,"completion_tokens":1405,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":689,"completion_tokens_details":{"reasoning_tokens":1308}},"tokens_in":689,"tokens_out":1405,"duration_ms":15425,"temperature":1.0,"reasoning_tokens":1308,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:23:18.951187+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search exhaustively over small binary instances with, say, two agents and two dimensions, enumerating every allocation and checking whether any instance has no strong sEF(3) allocation; one such instance would falsify Theorem 7. For the general claim, a counterexample would be any small instance with three agents and two dimensions in which every allocation leaves some agent envying another by more than $n^2\\ell^2 = 36$ items after any allowed removal set.","supporting_citations":[{"cited_title":"Fair division with allocator's preference","cited_arxiv_id":null,"evidence_quote":"Introduces the weak sEFc relaxation and supplies the three-dimension instance with no weak sEF1 allocation that motivates the paper."},{"cited_title":"Almost envy-freeness for groups: Improved bounds via discrepancy theory","cited_arxiv_id":null,"evidence_quote":"Provides the group-fairness discrepancy construction that the weak sEF nonexistence result is essentially equivalent to."},{"cited_title":"Introduction to linear optimization , volume 6","cited_arxiv_id":null,"evidence_quote":"Provides the standard linear-programming facts about basic feasible solutions and polynomial-time solvability used in Theorems 7 and 9."}],"review_version":1}