{"id":"468c561c-d3dc-4f31-9cc8-8c3c332dcf36","arxiv_id":"2502.03789","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For any fair division instance with monotone valuations, there exists an allocation with copies where each agent gets at least its maximin share, no good is copied more than O(log m) times, and total copies are at most m.","lead":"Exact maximin share fairness, known to be impossible for indivisible goods, becomes achievable if a limited amount of duplication or disposal is allowed. This paper proves tight bounds on how much copying or discarding is needed, even for fully general monotone preferences.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The lower-bound proof for goods replaces Binomial by Poisson without quantifying error, so the 'essentially tight' claim (Theorem 3.10) is not yet established.","rationale":"The main upper-bound results, especially Theorem 3.1, are supported by a correct probabilistic argument: sampling uniformly from each agent's MMS partition gives E[χ_g]=1, the Chernoff bound controls the ℓ∞ norm, Markov controls the ℓ1 norm, and the union bound yields the stated existence for m ≥ 2 (the m=1 edge case is a minor constant-patching issue). The identically ordered and chores arguments are also internally consistent. The load-bearing weakness is the tightness proof for monotone goods: the Poisson approximation in Theorem 3.10 is used as an exact equality without quantifying the error, and the regime needed for the Poisson limit and the regime needed for the union bound over n^n allocations pull in opposite directions. This directly affects the paper's advertised claim that the bounds are 'essentially tight.' A secondary dependency is Theorem 3.9's reliance on the external [HH22] result, whose precise hypotheses should be verified; however, the reader's identified weakest assumption—the Poisson approximation—is the same concern I find most load-bearing. The conditional verdict is appropriate: the constructive upper bounds are credible, but the tightness claim needs a repaired lower-bound proof before acceptance.","tokens_in":33748,"tokens_out":30739,"duration_ms":311591,"concrete_test":"Recompute the probability in equation (14) with the exact Binomial(n,1/n) CDF (or with a quantified Poisson approximation such as Le Cam's inequality d_TV ≤ 2/n), and substitute the resulting value into inequalities (15)-(16). Check whether there exists a choice of n = n(m), with m arbitrarily large, such that Pr{max_g χ_g ≤ ℓ} < n^{-2n} still holds for ℓ = log m / log log m. If such an n exists, the lower bound is repairable; if not, the tightness claim in Theorem 3.10 should be weakened or the proof substantially revised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 3.4, the random construction gives χ_g ~ Bin(n,1/n) exactly, but the proof of Theorem 3.10 writes equality (14) with the Poisson(1) CDF and then uses this value in the union bound (16) to conclude Pr{max_g χ_g ≤ ℓ} < n^{-2n}. No bound on the approximation error is supplied. This matters because the lower bound needs n large enough for the Poisson tail near ℓ = log m / log log m to be accurate, while the union bound over n^n allocations forces n to be small; the unquantified error could be comparable to the tail probability being estimated. A rigorous proof requires either a direct binomial tail estimate or a quantified approximation (e.g., Le Cam's inequality) with parameters satisfying both the tail and union-bound constraints. Until then, the 'essentially tight' claim for Theorem 3.1 is unsupported. The upper-bound theorem itself is sound; the gap is specifically in the matching lower bound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies exact maximin share (MMS) fairness when the supply of indivisible items can be adjusted after the fact: goods may be duplicated, or chores may be discarded. The proposed solution concept is an MMS multi-allocation in which each agent receives a subset of value at least its MMS, while the characteristic vector of the multi-allocation is bounded in ℓ1 and ℓ∞ for goods, and in the number of zero entries for chores. For monotone goods valuations, Theorem 3.1 gives an MMS multi-allocation with ℓ∞ ≤ 3 log m and ℓ1 ≤ m; for identically ordered valuations, Theorem 3.4 improves the multiplicity to O(√log m) at the cost of an additive m·Õ(1/√n) in ℓ1; and for additive valuations, Theorem 3.9 gives ℓ∞ ≤ 2 and ℓ1 ≤ 2m. On the chores side, Theorem 4.2 shows that at most m/e chores need be left unassigned under monotone costs, Theorem 4.4 gives an Õ(m/n^{1/4}) bound under identically ordered costs, and Theorem 4.9 gives a 2m/11 + n bound for additive costs. The paper also provides lower bounds claiming that the monotone-valuation goods bound and the monotone-cost chores bound are essentially tight, plus an entitlement generalization in Appendix A and an NP-hardness result in Appendix B.","tokens_in":33970,"tokens_out":8708,"duration_ms":90759,"significance":"If the results hold, the paper makes a clean conceptual contribution: the well-known impossibility of exact MMS under general monotone preferences can be bypassed by allowing limited duplication or disposal, and the quantitative bounds are quite strong. The upper-bound proofs are mostly self-contained and use standard probabilistic tools: random sampling from MMS-inducing partitions, Chernoff/Hoeffding bounds, and Chebyshev's inequality. There are no fitted parameters and no circularity: the existence arguments follow directly from the definition of MMS. The paper is honest about its external dependencies, notably the use of the cardinality-constrained MMS result of Hummel and Hetland in Theorem 3.9. The main caveat is the lower-bound proof for goods in Theorem 3.10, which currently uses an unquantified Poisson approximation; that gap is localized but load-bearing for the claimed tightness.","major_comments":[{"comment":"The proof of Theorem 3.10 replaces the exact distribution χ_g ∼ Bin(n,1/n) by χ_g ∼ Poi(1) and treats this as equality in Eq. (14), then uses the Poisson CDF in the union bound in Eq. (16). No bound on the approximation error is supplied. The total-variation error of the Poisson approximation is of order 1/n, which is not automatically negligible compared with the n^{-2n} target probability when n may be as small as 2 under the stated condition m ≥ 2 n log n e(ℓ+1)!. As written, the ``essentially tight'' claim for Theorem 3.1 is not established. Please either prove a direct binomial tail bound or quantify the approximation (e.g., via Le Cam's inequality), and state explicitly which ranges of n and m are used.","section":"§3.4, Eq. (14)–(16)"},{"comment":"The Chernoff step uses t = 3 log m and the bound Pr{χ_g ≥ t} ≤ 2^{-t}. With natural logarithms this gives only m^{-3 ln 2}, not m^{-3}, so the union-bound estimate Pr{G_1^c} ≤ 1/m^2 does not follow; with base-2 logarithms the constant 3 is correct, but the base is never stated. The same issue appears in Lemma A.4 for the entitlement result. Please state the logarithmic base explicitly, or adjust the constants and the admissible range of m if natural logarithms are intended.","section":"§3.1, Lemma 3.2"},{"comment":"The proof of Theorem 3.9 is essentially a reduction to the external result of Hummel and Hetland [HH22] on maximin shares under cardinality constraints, but the cited theorem is not stated in the paper. The reader cannot verify that the required guarantee (exact or 1/2-approximate) and the feasibility condition match exactly what is needed in the auxiliary instance ~I. Since the additive-goods result is one of the headline contributions, please state the invoked result precisely or give a proof of the needed consequence.","section":"§3.3, Theorem 3.9"}],"minor_comments":[{"comment":"Corollary 3.7 says ``every fair division instance with additive ordered valuations'' while the surrounding section is about identically ordered valuations; the proof and Lemmas 3.5–3.6 concern identically ordered valuations. Please correct the terminology and make clear whether the corollary is intended for all identically ordered valuations or only additive ordered ones.","section":"§3.2, Corollary 3.7"},{"comment":"The union-bound calculation in the proof of Theorem 3.1 writes Pr{G_1^c} + Pr{G_1^c} where the second term should be Pr{G_2^c}; the numerical conclusion is unaffected.","section":"§3.1, proof of Theorem 3.1"},{"comment":"The proof says the expected number of unassigned chores ``equals'' m/e, but the exact expectation is m(1−1/n)^n, which is strictly less than m/e. The inequality E[‖χ^R‖_z] ≤ m/e is what is needed and is enough for the stated bound.","section":"§4.1, Theorem 4.2"},{"comment":"There is a garbled cross-reference in the paragraph introducing the dyadic prefixes: ``the property laid out in /question_question'' appears to be a broken reference to the definition of identically ordered valuations. Please repair it.","section":"§3.2, Algorithm/Lemma 3.8"},{"comment":"The quantity ‖χ^A‖_z is written as a set in the text, e.g., ‖χ^A‖_z := {j ∈ [m] | χ^A_j = 0}, even though it is used as the cardinality of that set. This is a minor notational inconsistency worth fixing.","section":"§2 and §4, notation"}],"recommendation":"major_revision","confidential_remarks":"The Poisson-approximation gap in Theorem 3.10 is the main technical obstacle; it appears repairable with a direct binomial tail or a quantified Le Cam bound, so this is not a reject. The upper-bound results, especially Theorem 3.1 and Theorem 4.2, are elegant and likely correct. The paper fits the scope of cs.GT well. I saw no circularity or fitted-parameter concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me give you the short version: the main existence result is true and the proof is as clean as advertised; the lower bound that is supposed to make it tight is not yet proven. The paper deserves a serious referee, but the 'essentially tight' claim needs work.\n\nThe new model—exact MMS with limited duplication/disposal—is a good idea and the paper executes it well for the upper bounds. Theorem 3.1 is a genuinely neat observation: sample each agent's bundle uniformly from its MMS partition, then Chernoff plus Markov gives ℓ∞ ≤ 3 log m and ℓ1 ≤ m with positive probability. The identically ordered results (Theorems 3.4 and 4.4) are more involved—dyadic prefixes plus a copy-redistribution argument—and they appear sound to me. The chores upper bound m/e is a simple and correct application of the same sampling idea. The additive results depend on imported theorems ([HH22], [HL21]); that is fine, but the dependence should be flagged clearly.\n\nThe soft spot is Theorem 3.10. The proof replaces Bin(n,1/n) with Poisson(1) and then treats equation (14) as an exact identity inside a union bound over n^n allocations. That step is not justified as written. The approximation error is not quantified, and the parameters have to satisfy two competing constraints—the binomial tail needs n large, while the union bound needs n small relative to m^{o(1)}. The lower bound may well be true, and the argument is probably repairable with Le Cam's inequality or a direct binomial tail, but as it stands the matching lower bound is unproven. Relatedly, the statement should say something about the regime of n: for n < log m/log log m, a lower bound of log m/log log m on the max multiplicity is trivially impossible. Also, Theorem 3.1's constant 3 only works with base-2 logs in the Chernoff bound as written; with natural logs the constant needs to grow. These are minor fixes, but they are real.\n\nBottom line: the upper-bound half is a solid, citable contribution. The lower-bound half needs a rigorous repair before the 'essentially tight' claims can be trusted. I would send it to review, and I would expect the authors to fix the Poisson step. Worth a reading-group slot once the revised version is out.","headline":"The upper-bound half is real and clean; the lower-bound proof for goods has an unquantified Poisson approximation and needs repair before 'essentially tight' is justified.","tokens_in":34467,"tokens_out":12616,"would_cite":true,"duration_ms":121365,"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 proves that exact maximin share fairness is always achievable when goods may be duplicated or chores discarded, with only logarithmic per-item duplication under completely general monotone preferences.","keywords":["maximin share","fair division","multi-allocation","monotone valuations","chores","probabilistic method","capacity adjustment"],"falsifier":"Recompute the lower-bound argument of Section 3.4 with the exact Binomial(n,1/n) law for each good's copy count instead of Poisson(1), then redo the union bound over all $n^n$ candidate multi-allocations; if the resulting probability that every allocation has some good with at least $\\log m/\\log\\log m$ copies is not strictly positive for large $m$, the claimed asymptotic tightness of Theorem 3.1's duplication bound is not established. For the upper bound itself, a counterexample search over small monotone instances would settle Theorem 3.1 for those sizes.","tokens_in":33561,"feed_emoji":"⚖️","tokens_out":9095,"duration_ms":87557,"temperature":0.7,"pith_summary":"Maximin share (MMS) fairness asks that each agent receive a bundle worth at least the best guaranteed share it could secure by partitioning all goods into n bundles and taking the worst. For indivisible goods, exact MMS is known to be impossible even with additive preferences. This paper shows the obstruction disappears if the supply of items can be adjusted after the fact: there is always a multi-allocation giving every agent its MMS in which each good is copied at most $3\\log m$ times and the total number of assigned goods, copies included, is still at most $m$, even for completely monotone valuations. The analogous statement for chores is that at most $m/e$ chores ever need to be discarded. The consequences are concrete: exact fairness is a supply-adjustment problem, not merely an allocation problem.","feed_headline":"Exact MMS fairness is possible with 3 log m copies per good","feed_subtitle":"Arbitrary monotone preferences stop blocking fair division once goods may be copied and chores discarded.","key_machinery":"The central object is the characteristic vector $\\chi_A$ of a multi-allocation, whose $\\ell_1$ norm counts the total number of assigned copies, whose $\\ell_\\infty$ norm is the maximum number of copies of any single item, and whose zero-coordinate count $\\|\\chi_A\\|_z$ measures unassigned chores in the chores setting. The proof mechanism is the probabilistic method: independently, each agent samples one bundle uniformly from its MMS-inducing $n$-partition. Because each good lies in exactly one bundle of every such partition, it lands in any given agent's sampled bundle with probability $1/n$, so the expected copy count of every good is $1$ and the expected total is $m$; Chernoff, Hoeffding, and Chebyshev bounds then show the $\\ell_\\infty$ and $\\ell_1$ events co-occur with positive probability. For identically ordered instances, the sampled allocation is post-processed by a copy-redistribution algorithm that replaces higher-indexed, lower-marginal-value goods with lower-indexed, higher-marginal-value ones, preserving MMS while compressing multiplicities; for chores, the same sampling gives an expected unassigned count of $m(1-1/n)^n \\approx m/e$, and a covering-plus-redistribution step converts concentration on chore intervals into a bound on unassigned chores.","core_discovery":"Every fair division instance with goods and monotone valuations admits an MMS multi-allocation $A=(A_1,\\dots,A_n)$ whose characteristic vector $\\chi_A$ satisfies $\\|\\chi_A\\|_\\infty \\le 3\\log m$ and $\\|\\chi_A\\|_1 \\le m$: no individual good needs to be handed to more than logarithmically many agents, and the total number of goods handed out, counting copies, is at most the original number of goods. The same random-sampling idea shows that for $m$ chores with monotone costs an MMS multi-allocation can leave at most $m/e$ chores unassigned. Under identically ordered valuations or costs the bounds improve to $O(\\sqrt{\\log m})$ multiplicity and $m + O(m\\sqrt{\\log m}/\\sqrt{n})$ total assigned goods; under additive valuations, two copies of any good suffice. Matching lower bounds show that the monotone results are essentially tight, so these guarantees cannot be substantially improved in the most general model.","pith_inferences":["If the paper is right, fair division can be treated as capacity planning: duplicating a few scarce goods and leaving unwanted goods unassigned lets an algorithm meet an exact fairness target without changing preferences, so practical systems could adjust class sizes, inventory, or hospital capacities rather than rationing by approximation.","The same random-sampling template likely extends to other share notions and to envy-freeness up to any good (EFX) with duplication or charity, a direction the paper itself hints at; a testable next step is to run the sampling argument with EFX-inducing partitions and see what multiplicity bounds emerge.","The gap between the $3\\log m$ upper bound and the $\\log m/\\log\\log m$ lower bound for monotone goods suggests the true worst-case multiplicity may be $\\Theta(\\log m/\\log\\log m)$, but that is an editorial guess, not a claim of the paper.","For identically ordered valuations, the dyadic-prefix redistribution suggests a broader principle: whenever items can be sorted by marginal value, copy counts can be equalized across a prefix structure, which may carry over to online or dynamic allocation."],"forward_implications":["Exact MMS is feasible for every monotone valuation, which is impossible without duplication: the barrier is item supply, not preference structure.","In any instance with $m$ goods, one can find a fair multi-allocation that hands out no more than $m$ goods in total, so duplication never increases the overall volume of allocated resources.","For additive valuations, an MMS assignment exists in which no good is used more than twice and the total number of assigned goods is at most $2m$, a mild adjustment in realistic settings.","For chores, MMS fairness is always achievable by discarding at most $m/e$ chores; under additive costs the discarded count drops to $2m/11 + n$.","The lower bounds show the general guarantees are essentially optimal: some instances require $\\Omega(\\log m/\\log\\log m)$ copies of a good, and every MMS assignment leaves $(1-o(1))m/e$ chores unassigned."],"supporting_citations":[{"why":"Introduces the course-allocation setting with limited capacity duplication and the 1-out-of-(n+1) MMS guarantee that this work generalizes to exact MMS.","marker":"[Bud11]"},{"why":"Establishes that exact MMS allocations can fail even for additive valuations, the infeasibility that the duplication and disposal model is designed to circumvent.","marker":"[KPW18]"},{"why":"Gives the best-known constant approximation for additive MMS, the comparison point showing that exact MMS here is a qualitative improvement.","marker":"[GT20]"},{"why":"Proves that chores instances may fail to admit MMS allocations and initiates approximation algorithms for chores, motivating the disposal model.","marker":"[ARSW17]"},{"why":"Provides the 11/9-approximate MMS chore allocation from which the paper derives its $2m/11+n$ disposal bound.","marker":"[HL21]"},{"why":"Proves the cardinality-constrained additive-valuation result that the paper converts into a two-copies-per-good MMS multi-allocation.","marker":"[HH22]"},{"why":"Supplies the Chernoff, Hoeffding, and Chebyshev concentration inequalities used to show the sampled multi-allocation meets the norm bounds with positive probability.","marker":"[MU17]"}],"fun_headline_variants":["Exact fair shares with just 3 log m copies per good","Copies and discards: the secret to exact MMS fairness","Limited copying ensures exact maximin share fairness","Logarithmic copies per good: exact MMS achieved","No need for perfect preferences: copies fix fairness"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The tightness lower bound assumes the number of copies of each good in the random construction follows a Poisson(1) distribution, when it actually follows Binomial(n,1/n), and does not quantify how small the error from that approximation is before union-bounding over all allocations.","fun_headline_variants_meta":{"raw":{"variants":["Exact fair shares with just 3 log m copies per good","Copies and discards: the secret to exact MMS fairness","Limited copying ensures exact maximin share fairness","Logarithmic copies per good: exact MMS achieved","No need for perfect preferences: copies fix fairness"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000656,"raw_usage":{"total_tokens":3092,"prompt_tokens":1125,"completion_tokens":1967,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":741,"completion_tokens_details":{"reasoning_tokens":1901}},"tokens_in":741,"tokens_out":1967,"duration_ms":13584,"temperature":1.0,"reasoning_tokens":1901,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T00:45:06.200277+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the lower-bound argument of Section 3.4 with the exact Binomial(n,1/n) law for each good's copy count instead of Poisson(1), then redo the union bound over all $n^n$ candidate multi-allocations; if the resulting probability that every allocation has some good with at least $\\log m/\\log\\log m$ copies is not strictly positive for large $m$, the claimed asymptotic tightness of Theorem 3.1's duplication bound is not established. For the upper bound itself, a counterexample search over small monotone instances would settle Theorem 3.1 for those sizes.","supporting_citations":[],"review_version":1}