{"id":"52f85255-0c65-4240-bc81-800e504b0d44","arxiv_id":"2411.10434","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Novel cake-cutting and envy-free share notions for divisible goods are simultaneously achievable only up to a tight Θ(√n) approximation in the worst case.","lead":"This paper proposes new fair-share definitions for dividing divisible goods, where each agent's guaranteed share depends on what other agents value, not just its own utility. The authors prove that all agents can simultaneously get about 1/√n of these shares in the worst case, and that this is the best possible.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 12's ε-to-binary reduction is the load-bearing step: the claimed (1+O(ε·mn)) ratio preservation is unjustified when C/SW is small, leaving the O(√n) upper bound unproven as written.","rationale":"I checked the main proof chain beyond the reader's flagged point. Theorem 11 is a clean LP-duality conversion, and the dual solution in Theorem 13 satisfies the dual constraints and gives λ≤2√n+1; the projective-plane lower bound in Section 4 also yields ∑CCS_i/SW=Θ(√n) with a valid feasible solution. The remaining soft spot is exactly Theorem 12. The ceiling step as written claims a multiplicative (1+O(ε·mn)) error, but when min(C,SW)=C=1 and R=C/SW is small, the relative error is not bounded by that expression. The result is recoverable with an absolute-error argument and a case split, but that argument is not present. Thus the central upper bound depends on a formalization gap rather than on a known false step. This is the same weakest assumption the reader identified, so the CONDITIONAL verdict is appropriate and does not need to move. The lack of code and data for the empirical section is a separate reproducibility issue, but it is not load-bearing for the central Θ(√n) theorem.","tokens_in":17711,"tokens_out":28493,"duration_ms":279309,"concrete_test":"Formally re-derive Theorem 12 with explicit epsilons. For a fixed instance with n agents and m items, let R=C(I)/SW(I) and set δ>0. After normalizing min(C,SW)=1 and scaling by 1/ε, verify the chain: if R≤δ then C'(I')/SW'(I')≤δ+ε·mn; if R>δ, choose ε<δ/(mn) so that C'(I')/SW'(I')≤R+δ. Then prove the cloned binary instance I'' satisfies C'(I')/SW'(I')≤C''(I'')/SW''(I''). If this chain can be completed, Theorem 1 is restored; if the chain fails, the general-valuation upper bound is unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central Θ(√n) upper bound (Theorem 1) rests on Theorem 12's reduction from general to binary valuations. The proof scales to min(C,SW)=1, multiplies by 1/ε, and takes ceilings; the text claims the ratio increases by only (1+O(ε·mn)). This is not justified as stated in the case C<SW (so min(C,SW)=C=1). After scaling, the additive ceiling error in C is at most mn, while SW'≈SW/ε=1/(εR), where R=C/SW. The absolute error added to the ratio is ε·mn·R, but the relative error is ε·mn, and the claimed multiplicative form implicitly assumes the original ratio is bounded below. The conclusion is still recoverable by an absolute-error argument: if R≤δ, the desired bound is immediate; otherwise choose ε<δ/(mn) to make the additive error at most δ. However, this case split is absent from the paper. Since Theorem 12 is the only bridge from the binary dual-fitting LP to the general-valuation model, the O(√n) upper bound is not fully proven as written. The lower bound, Theorem 11, and the dual-fitting LP itself appear sound; the gap is in this limit step, not in the LP duality.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces new fair-share notions for divisible-item fair division: the cake-cutting share (CCS), the envy-free share (EFS), and an interpolating family EFS^Delta. For each notion it asks what fraction of the share can be guaranteed to all agents simultaneously in the worst case. The main results are a tight Theta(sqrt(n)) bound for CCS/EFS as a function of the number of agents, an O(m^{2/3}) upper bound with an Omega(sqrt(m)) lower bound for CCS as a function of the number of items, and a Theta(sqrt(Delta)) bound for EFS^Delta. The upper bounds are proved through an LP-duality reduction to social welfare, a reduction to binary valuations, and a dual-fitting LP; the m^{2/3} bound uses a greedy set-cover algorithm. A short empirical section reports approximation ratios on simulated and real valuation data.","tokens_in":17910,"tokens_out":15885,"duration_ms":155493,"significance":"The paper's central conceptual contribution is to define fair shares that are sensitive to other agents' utility functions, moving beyond proportionality even for divisible goods. If the proofs are correct, the tight Theta(sqrt(n)) worst-case approximation is a clean structural result, and the dual-fitting LP (Section 3) together with the projective-plane lower bound (Section 4) are elegant techniques likely to be reusable. The paper is also transparent that the shares and optimal allocations are efficiently computable via linear programming, and the empirical study gives a useful comparison of the notions. The main results are novel and appear to be of interest to the fair-division community, provided the two proof gaps identified below are repaired.","major_comments":[{"comment":"The proof of the binary-valuation reduction contains a claim that is not justified as stated. After normalizing min(C(I), SW(I)) = 1 and applying the ceiling operation, the text asserts that the ratio C/SW increases by a multiplicative factor of (1 + O(epsilon * m * n)). However, the ceiling error is additive: C'/SW' <= C/SW + epsilon * m * n / SW, and if the original ratio C/SW is very small, the additive term dominates. The theorem is recoverable by a direct additive-bound argument: either split on C/SW <= delta, or observe that as epsilon -> 0 the ratio converges to the original ratio; but this argument is absent. Because Theorem 1 relies on Theorem 12 as the only bridge from the binary dual-fitting LP to general valuations, the proof of the O(sqrt(n)) upper bound needs this repaired limit argument.","section":"Section 3, Theorem 12"},{"comment":"The constructed allocation in the lower-bound instance violates the defining constraint that agents in W_i receive the same bundle as agent i. For items S in the set T, the rule 'set x_jS = 1/ell if j in S' assigns positive amounts to agents j in Z_i = W_i union {i} whenever j lies in S, while agent i receives zero from these items. This contradicts A_j = A_i for j in W_i in F_i^{EFS^Delta}. The construction can be fixed locally by setting x_jS = 0 for j in Z_i and S in T (and only assigning to j in S \\ Z_i); the displayed inequality u_j(A_j) >= u_j(A_i) then still follows from the same counting. As printed, the Omega(sqrt(Delta)) lower bound is not established.","section":"Section 6.2, lower bound for EFS^Delta"}],"minor_comments":[{"comment":"The displayed inequalities bound CCS'_i by sum_{B_i} + (1/n)(1/(ab) + (a+b)m), while ALG_i = (1/3)(1/n + sum_{B_i}). Substituting a = b = m^{-1/3} gives a ratio of O(m^{2/3}) but not the stated constant factor 3m^{2/3}; for instance, when sum_{B_i} = 0 the ratio is bounded by 9m^{2/3}. The asymptotic O(m^{2/3}) claim remains correct, but the constant assertion should be corrected or softened.","section":"Section 5.1"},{"comment":"The sentence 'The factor of 3 can be improved to (1 + epsilon) for any constant epsilon > 0 by slightly modifying the algorithm, and we omit the details' states a result without proof. Since it is not used in any theorem, it should either be proved in an appendix or moved to a remark.","section":"Section 5.1"},{"comment":"The notations alpha(n, .) and alpha(., m) are used in the introduction but only defined in Section 2. Please define both variants explicitly at their first use.","section":"Section 1.5 and Section 2"}],"recommendation":"major_revision","confidential_remarks":"The paper is a good fit for a theory-oriented venue. The main results are novel and the techniques are interesting, but the two proof gaps identified in the report are load-bearing for Theorems 1 and 4. Both appear fixable without changing the main claims, so I recommend major revision rather than rejection. The authors should also clean up the constant-factor claim in Section 5.1."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: this is a genuine new idea in fair division, and the main Θ(√n) result is very likely correct, but the proof as written has a fixable gap in the reduction to binary valuations. I'd send it out, with a request to clean up that step.\n\nWhat's new: the paper defines cake-cutting and envy-free shares that depend on other agents' utilities, which is a real departure from proportionality and MMS-style shares for divisible goods. The share definitions are natural, the LP characterizations are clean, and the results are non-trivial: tight Θ(√n) worst-case approximation for CCS/EFS, an O(m^{2/3}) bound via a set-cover argument, and a smooth interpolation for EFS_Δ. The dual-fitting LP in Theorem 13 is a nice technique, and the projective-plane lower bound is elegant. None of this is derivable from the prior share literature.\n\nWhere it's soft: the reduction in Theorem 12 is the bridge that carries the O(√n) upper bound from binary to general valuations, and the proof's limit argument is too quick. After the min(C,SW)=1 normalization, the ceiling operation adds O(ε mn) to the ratio in absolute terms, not multiplicatively. When C/SW is tiny, the claimed (1+O(ε mn)) multiplicative factor is not justified. This is a real gap as written. The good news is that the gap is repairable: split on whether the ratio is large or small; if it is small the desired bound is immediate, and if it is bounded below the multiplicative form goes through. The authors should write that out.\n\nThe empirical section is also not reproducible—no code or data—but it is clearly secondary to the theory. Section 5 has a likely typo (calling the small-value items 'Si') and omits the promised (1+ε) improvement; both are minor.\n\nTheorems 11 and 13, the dual fitting itself, and the lower bound all look sound to me. The citation pattern is fine, with self-citations only as background.\n\nWho should read this: anyone working on fair shares, cake cutting, or approximation in fair division. It introduces a framework that will likely be built on, and it deserves serious refereeing. I would cite it.","headline":"Genuinely new share notions for divisible goods with tight Θ(√n) worst-case bounds; the main result is likely correct, but the binary-valuation reduction in Theorem 12 has a fixable gap that should be spelled out before publication.","tokens_in":18507,"tokens_out":4853,"would_cite":true,"duration_ms":44056,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B32","68Q25","90C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The worst-case approximation ratio for the cake-cutting and envy-free shares is $\\Theta(\\sqrt{n})$, so no allocation can guarantee every agent more than a $1/\\sqrt{n}$ fraction of its share in the worst case.","keywords":["fair division","cake-cutting share","envy-free share","approximation ratio","dual fitting","social welfare","linear programming","proportional share"],"falsifier":"Take an instance with non-binary valuations chosen just below integer multiples of $\\epsilon$ (for example, $v_{ik}=k/\\epsilon - \\delta_{ik}$ with tiny $\\delta_{ik}$), apply the paper's ceiling-and-cloning reduction, and compute $C(I')/SW(I')$ versus $C(I)/SW(I)$; if the binary ratio strictly exceeds the original ratio in the $\\epsilon\\to 0$ limit for any $\\epsilon$-family, Theorem 12 fails and the $O(\\sqrt{n})$ upper bound would apply only to binary utilities.","tokens_in":17459,"feed_emoji":"🎂","tokens_out":9754,"duration_ms":86448,"temperature":0.7,"pith_summary":"This paper introduces two fairness benchmarks for dividing divisible goods: the cake-cutting share and the envy-free share, both computed from an individual agent's viewpoint but constrained by other agents' valuations through envy-like inequalities. It asks what fraction of these shares can be guaranteed to every agent simultaneously in the worst case over all instances. The central answer is that this fraction is exactly $1/\\Theta(\\sqrt{n})$: an allocation always exists that gives each agent a $\\Omega(1/\\sqrt{n})$ fraction of its share, and there are instances where any allocation makes some agent lose a factor of $\\Theta(\\sqrt{n})$. This shows that these richer share notions admit no constant-factor approximation, unlike proportionality which is trivially achievable. The result extends to an interpolating family, EFS$_\\Delta$, whose worst-case approximation is $\\Theta(\\sqrt{\\Delta})$.","feed_headline":"Worst-case fair share guarantee is exactly √n","feed_subtitle":"New proof: no allocation can guarantee every agent more than a 1/√n fraction of its cake-cutting or envy-free share.","key_machinery":"The machinery is a dual-fitting argument around a linear program whose objective is the ratio of the sum of envy-free (or cake-cutting) shares to social welfare. The upper-bound proof has three load-bearing steps: a strong-duality theorem that turns a ratio bound of $\\theta_n$ on this LP into an allocation giving each agent a $\\theta_n$ fraction of its share; a rounding reduction showing it suffices to bound the ratio for binary valuations (each $v_{ik}\\in\\{0,1\\}$); and an explicit dual solution for binary instances that sets $\\eta_{ij}=1/\\sqrt{n}$, producing a dual value of $O(\\sqrt{n})$. The lower bound uses a finite projective plane of order $q$, with agents as lines and items as points, so that each agent values exactly $q+1$ items and each pair of agents shares one valued item; this makes the share-sum-to-welfare ratio $\\Theta(\\sqrt{n})$. The EFS$_\\Delta$ extension reruns the dual fitting with a parameter $Z=|W_i|+1$ and obtains $O(\\sqrt{n/Z})$, which is $O(\\sqrt{\\Delta})$.","core_discovery":"On the paper's own terms, the core discovery is that the worst-case approximation ratio $\\alpha(n,\\cdot)$ for the cake-cutting share (CCS) and the envy-free share (EFS) is $\\Theta(\\sqrt{n})$. For any instance with $n$ agents, the sum of the agents' envy-free shares is at most $O(\\sqrt{n})$ times the social welfare, and strong duality converts this ratio bound into an allocation where every agent receives at least a $\\Omega(1/\\sqrt{n})$ fraction of its share. A finite projective-plane construction shows the bound is tight: there are instances where the sum of cake-cutting shares is $\\Omega(\\sqrt{n})$ times the social welfare, forcing some agent to incur a $\\sqrt{n}$ loss. The paper also proves $\\alpha(\\cdot,m)=O(m^{2/3})$ for the cake-cutting share as a function of the number of items, with a nearly matching lower bound, and proves that the EFS$_\\Delta$ family has worst-case approximation $\\Theta(\\sqrt{\\Delta})$, interpolating between proportionality and the envy-free share.","pith_inferences":["If the $\\Theta(\\sqrt{n})$ barrier reflects the envy constraints themselves, analogous share notions for indivisible goods or non-additive utilities would likely face bounds no better than $\\Theta(\\sqrt{n})$, since rounding and item-duplication become less exact without linearity.","The dual-fitting LP is a reusable recipe: any share notion expressible by linear envy constraints immediately yields a ratio LP, and a good dual solution gives an approximation bound; this may be worth applying to other cumulative-share definitions.","The empirical EFS$_\\Delta$ results suggest a practical design heuristic the paper does not state explicitly: set the unknown-agent set to roughly a quarter to a third of the other agents (about $\\Delta=4$-$6$) to get shares that are both individually meaningful and nearly simultaneously achievable.","The worst-case instances are highly structured projective planes, so random or sparse valuation instances are likely far easier than the bound suggests; instance-specific LP-based approximation may typically beat $\\Theta(\\sqrt{n})$ by a wide margin."],"forward_implications":["Because $\\alpha(n,\\cdot)=\\Theta(\\sqrt{n})$ for the envy-free and cake-cutting shares, no allocation rule can guarantee every agent a constant fraction of these shares in the worst case; the best possible guarantee is a $1/\\sqrt{n}$ fraction.","The same $\\Theta(\\sqrt{n})$ bound automatically applies to every intermediate share notion whose envy polyhedron lies between the cake-cutting and envy-free polyhedra.","The EFS$_\\Delta$ family gives a smooth interpolation: with a random unknown set of about $(n-1)/\\Delta$ agents, the worst-case approximation is $\\Theta(\\sqrt{\\Delta})$, so small $\\Delta$ behaves like proportionality and $\\Delta\\ge n$ recovers the envy-free share.","As a function of the number of items, the cake-cutting share admits an $O(m^{2/3})$-approximation, with an $\\Omega(\\sqrt{m})$ lower bound; both are sublinear in $m$.","On simulated and real advertiser-bid instances, the cake-cutting share has an approximation ratio near 1, meaning it is essentially simultaneously achievable, whereas proportionality underestimates and the envy-free share overestimates agents' share values."],"supporting_citations":[{"why":"Introduces proportionality and the original fair-division problem that the new cake-cutting share generalizes.","marker":"Steinhaus [1948]"},{"why":"Makes explicit the cutting-and-choosing max-min interpretation of proportionality that defines the cake-cutting share.","marker":"Budish [2011]"},{"why":"Sets up the general notion of a share that the paper extends beyond agent-oblivious valuations.","marker":"Babaioff and Feige [2022]"},{"why":"Provides the finite projective-plane geometry used to build the lower-bound instance for $\\Theta(\\sqrt{n})$.","marker":"Dembowski [1968]"},{"why":"Supplies the random-valuation generation model used in the empirical comparison of proportionality, CCS, and EFS.","marker":"Caragiannis et al. [2019]"},{"why":"Supplies the real-world advertiser-bid dataset used to test whether the shares are achievable in practice.","marker":"Yahoo [2003]"}],"fun_headline_variants":["Fair share worst-case is exactly √n","Cake-cutting share: tight Θ(√n) bound","No allocation beats 1/√n of your fair share","Worst-case fair division: √n is the limit","New proof: cake-cutting share gap is Θ(√n)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The upper-bound proof assumes that rounding every agent's numerical valuations to nearby integer multiples of a small $\\epsilon$ and then cloning items so all valuations become 0 or 1 does not distort, in the limit as $\\epsilon\\to 0$, the ratio of the sum of envy-free shares to social welfare.","fun_headline_variants_meta":{"raw":{"variants":["Fair share worst-case is exactly √n","Cake-cutting share: tight Θ(√n) bound","No allocation beats 1/√n of your fair share","Worst-case fair division: √n is the limit","New proof: cake-cutting share gap is Θ(√n)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000482,"raw_usage":{"total_tokens":2389,"prompt_tokens":958,"completion_tokens":1431,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":1359}},"tokens_in":574,"tokens_out":1431,"duration_ms":12769,"temperature":1.0,"reasoning_tokens":1359,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T19:40:03.403948+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take an instance with non-binary valuations chosen just below integer multiples of $\\epsilon$ (for example, $v_{ik}=k/\\epsilon - \\delta_{ik}$ with tiny $\\delta_{ik}$), apply the paper's ceiling-and-cloning reduction, and compute $C(I')/SW(I')$ versus $C(I)/SW(I)$; if the binary ratio strictly exceeds the original ratio in the $\\epsilon\\to 0$ limit for any $\\epsilon$-family, Theorem 12 fails and the $O(\\sqrt{n})$ upper bound would apply only to binary utilities.","supporting_citations":[{"cited_title":"The problem of fair division","cited_arxiv_id":null,"evidence_quote":"Introduces proportionality and the original fair-division problem that the new cake-cutting share generalizes."},{"cited_title":"Finite Geometries","cited_arxiv_id":null,"evidence_quote":"Provides the finite projective-plane geometry used to build the lower-bound instance for $\\Theta(\\sqrt{n})$."},{"cited_title":"A1 dataset","cited_arxiv_id":null,"evidence_quote":"Supplies the real-world advertiser-bid dataset used to test whether the shares are achievable in practice."}],"review_version":1}