{"id":"32f751ad-de3f-49ca-8ac8-6d7e636c4164","arxiv_id":"2506.02193","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An FPTAS is given for leximin-optimal electricity allocation when the distribution network is a tree.","lead":"This paper studies how to fairly ration electricity when demand exceeds supply, requiring that connected households form a connected network. It proves the problem is NP-hard in general and offers an approximation scheme for tree-shaped networks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1's key inequality can fail when the highest-valued item exceeds capacity, breaking the (1−ε) guarantee; a concrete counterexample shows the FPTAS as written does not achieve the claimed approximation.","rationale":"The reader's conditional verdict is appropriate. The Lemma 1 gap is load-bearing because the FPTAS guarantee and the leximin reduction both rely on the (1−ε) approximation of Geographic Knapsack. The counterexample is small and directly falsifies the lemma as stated. The issue is an internal correctness gap, not a disagreement with consensus. It is likely fixable by excluding infeasible items from v_max, so conditional rather than reject. The DP zero-value/base-case issue noted by the reader is secondary; the Lemma 1 counterexample is sufficient to require revision. No machine-checked proof or reproducible code is supplied, so the proof text is the only evidence for the main theorem.","tokens_in":13129,"tokens_out":8193,"duration_ms":75454,"concrete_test":"Run Algorithm 1 exactly as stated on the two-item star instance (n=2, S=1, d=(2,1), v=(100,1), ε=0.2). Record the output. If it is empty (or the final loop fails to return while OPT=1), the counterexample is confirmed. For an analytical check, verify the line 'v_max ≤ sum_{i∈C*} v_i' in Lemma 1 with this instance: 100 ≤ 1 is false. Also verify that deleting the oversized item before rounding restores the (1−ε) guarantee, which would show the FPTAS is fixable by a preprocessing step.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central approximation guarantee rests on Lemma 1 (Section 4.1), specifically on the step 'as v_max ≤ sum_{i∈C*} v_i'. This inequality is not implied by the definitions. In Geographic Knapsack, C* is an optimal legal packing, and any item with size d_i > S is excluded from every legal packing, yet it still contributes to v_max. Concrete counterexample: n=2, S=1, d_1=2, v_1=100, d_2=1, v_2=1, with a star graph. The only legal packings are ∅ and {2}, so OPT=1, but v_max=100. For ε=0.2, θ=10, rounded values are r_1=10, r_2=0. Algorithm 1 then has no legal packing with positive rounded value; its final loop j=v_N...1 returns nothing (or would have to return the empty packing of value 0), so the output value is 0 < (1−ε)·OPT = 0.8. Thus Lemma 1's conclusion is false. A fix is to delete items with d_i>S (or re-define v_max over items that can appear in a legal packing) before rounding; the paper does not state such a preprocessing step. Because Theorem 5 and hence the leximin FPTAS depend on Lemma 1, the main claim is not established as written, though the gap appears repairable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the fair division of scarce electricity over a time interval [0,1], where each household has a fixed demand and a set of simultaneously served households must have total demand at most S and induce a connected subgraph containing the power station. Agents have uniform additive utilities equal to their total connection time. The main results are (i) NP-hardness of maximizing the smallest utility (egalitarian welfare) even on a star network, and (ii) an FPTAS for the stronger leximin objective when the underlying network is a tree. The algorithmic part reduces leximin, via a black-box theorem of Hartman et al. [10], to weighted utilitarian allocation, which is formulated as a 'Geographic Knapsack' problem; the paper then adapts the standard value-rounding FPTAS to Geographic Knapsack on trees, presenting an exact dynamic program (Algorithm 1) for integer values.","tokens_in":13483,"tokens_out":21857,"duration_ms":224980,"significance":"If the identified gaps are repaired, this would be a solid contribution. The NP-hardness proof is elementary and correct, and an FPTAS for leximin allocation under tree connectivity is a nontrivial positive result that goes beyond prior egalitarian bin-packing results. The reduction to Geographic Knapsack is clean, Algorithm 1 is explicit, the rounding framework is standard, and the runtime bound is polynomial in n and 1/ε. The paper also correctly identifies its dependence on the external reduction theorem [10]; given that theorem, the reduction step is valid. However, the approximation guarantee of the FPTAS currently rests on an unjustified inequality in Lemma 1, and Algorithm 1 as written mishandles zero-valued rounded items; both are repairable, but the main theorem is not established as written.","major_comments":[{"comment":"The inequality 'v_max ≤ Σ_{i∈C*} v_i' used in the last step of the proof of Lemma 1 is not implied by the definitions. v_max is the maximum value over all items, whereas C* is a legal packing; any item with d_i > S is absent from every legal packing. For a concrete failure, take a star graph with n=2, S=1, d=(2,1), v=(100,1). The only legal packings are ∅ and {2}, so OPT=1, but v_max=100. With ε=0.2, θ=10, the rounded values are (10,0); the empty packing has rounded value 0, which is maximum among legal packings (item 1 is illegal and item 2 rounds to 0), yet its original value is 0 < (1−ε)·OPT = 0.8. Thus Lemma 1's conclusion is false. This invalidates the proof of Theorem 5. A repair is to remove all items with d_i > S (or redefine v_max over items that can belong to a legal packing) before rounding, and to handle the case OPT=0 separately; the paper should state this preprocessing explicitly.","section":"Section 4.1, Lemma 1 (proof of Theorem 5)"},{"comment":"The rounded values r_i = ⌊v_i/θ⌋ are nonnegative integers, and zero values occur whenever v_i < θ. The base case (lines 6–8) sets F(i,v_i)={i} for a leaf that is a first child; when v_i=0, this overwrites F(i,0), which was initialized to the empty packing, even though the empty packing has smaller size and satisfies condition (1). This can propagate incorrect cells. Concretely, let G be a star with two leaves, d=(1,1), integer values v=(0,1), and S=1. Under the valid numbering in which the zero-valued leaf is node 1 and the positive-valued leaf is node 2, Algorithm 1 computes F(2,1)={1,2} with size 2; the final loop then finds no packing with d≤S and returns nothing, although {2} is a legal packing of value 1. Hence Theorem 4 is false as stated for nonnegative integer values. Fix: assign F(i,v_i)={i} only if v_i>0, and make the final loop consider j=0 so that the empty packing is returned when the optimal rounded value is 0.","section":"Section 4.1, Algorithm 1 and Theorem 4"}],"minor_comments":[{"comment":"The text uses 'FTPAS' instead of 'FPTAS' in at least two places; this should be corrected.","section":"Abstract and Section 1"},{"comment":"There is a typo in 'an agenF's demand'; it should read 'an agent's demand'.","section":"Section 1.1"},{"comment":"The symbol C is used both for a single configuration and for the set of all feasible configurations; this makes the definition of X confusing and should be renotated.","section":"Section 2, definition of X"},{"comment":"The step 'Σ_{i∈C*} θ = n ε v_max / n' is an equality only if |C*|=n; the correct statement is Σ_{i∈C*} θ ≤ n ε v_max / n, and the chain should use an inequality rather than an equality.","section":"Section 4.1, proof of Lemma 1"},{"comment":"The line 'v_N = n·r_max' should be 'v_N ≤ n·r_max', since v_N is the sum of n rounded values. Also, θ is undefined when v_max=0; the all-zero-value case (where every packing is optimal) should be handled separately.","section":"Section 4.1, Theorem 5 runtime proof"}],"recommendation":"major_revision","confidential_remarks":"The paper relies heavily on [10], a prior work by overlapping authors, as a black box for the leximin-to-utilitarian reduction. The editor may wish to verify that [10] is published or otherwise available, since the reduction is not proved here. The technical gaps identified in the major comments are repairable within the manuscript's scope, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Eden et al. give an FPTAS for leximin-optimal electricity allocation when the network is a tree, plus an NP-hardness proof for egalitarian welfare even on a star. The NP-hardness is a clean Partition reduction. The main algorithmic idea—reduce leximin to weighted-utilitarian via Hartman et al. [10], then solve the resulting Geographic Knapsack on trees with a DP after value rounding—is sensible, and the DP looks correct in spirit.\n\nThe soft spot is Lemma 1. The proof uses v_max <= sum_{i in C*} v_i, which is not guaranteed if the largest-value item has size d_i > S and therefore appears in no legal packing. Concrete example: S=1, d_1=2, v_1=100, d_2=1, v_2=1. The only legal packing is {2}, OPT=1, but v_max=100; for eps=0.2, the rounded instance has r_1=10, r_2=0, and the best legal packing has rounded value 0, giving output value 0 < 0.8. So Lemma 1 is false as stated and the (1-eps) guarantee does not follow. The fix is easy: delete items with d_i > S (or redefine v_max over packable items) before rounding. The paper doesn't state that preprocessing.\n\nThere is also a small bug in the DP base case: for a leaf first-child, line 7 sets F(i, v_i)={i} even when v_i=0, overwriting the empty packing that has smaller size. Zero values do arise after rounding, so the DP needs to handle that case.\n\nThese are both fixable. The reduction from [10] is used as a black box; that's fine, it's a published result, and the self-citation is not circular since the FPTAS is independently derived. The runtime argument checks out: rounded values are bounded, so the table is polynomial.\n\nBottom line: a genuinely useful contribution in an underexplored area, but the paper as written doesn't prove its main theorem. The errors are repairable and don't look deep. Send it to peer review; a good referee will catch these quickly and the authors should be able to patch them. If the fixes land, I'd cite it.","headline":"A useful, repairable FPTAS for leximin electricity allocation on trees, but Lemma 1's proof breaks on oversized items and the DP mishandles zero values.","tokens_in":13941,"tokens_out":2633,"would_cite":true,"duration_ms":22386,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Fair division of scarce electricity is NP-hard, but tree networks admit a fully polynomial-time approximation scheme for leximin.","keywords":["leximin approximation","egalitarian allocation","NP-hard","electricity distribution","fair division","approximation algorithms","geographic knapsack","tree networks"],"falsifier":"Build a tree instance with a single item of value $1$ and demand larger than the supply $S$, while all feasible items together have value $1/2$. For $\\varepsilon < 1/2$, the inequality $v_{\\max} \\le \\sum_{i\\in C^*} v_i$ used in Lemma 1 is false; if Algorithm 1 on such an instance returns a packing with value below $(1-\\varepsilon)\\cdot 1/2$, the central guarantee fails, and if it does not, the theorem needs a repaired proof.","tokens_in":12971,"feed_emoji":"⚡","tokens_out":9546,"duration_ms":93304,"temperature":0.7,"pith_summary":"This paper asks how to allocate scarce electricity fairly when not all households can be served at once and any group receiving power must form a connected subgraph with the power station. It proves that maximizing the smallest utility is NP-hard even in the simplest network, and that the stronger leximin rule is NP-hard as well. The main positive result is an FPTAS for leximin when the network is a tree: for any $\\varepsilon \\in (0,1)$, it returns an allocation whose sorted utility vector is within factor $1-\\varepsilon$ of every other allocation, in time polynomial in the instance size and in $1/\\varepsilon$. The route runs through a reduction from leximin to weighted utilitarian allocation, which becomes a knapsack problem with a geographic connectivity constraint.","feed_headline":"Fair electricity rationing is NP-hard; tree grids are tractable","feed_subtitle":"A (1−ε)-optimal leximin schedule for tree networks is computable in polynomial time, despite NP-hardness in general.","key_machinery":"The load-bearing object is the reduction theorem of [10]: an $\\alpha$-approximate solver for weighted-utilitarian allocation yields an $\\alpha$-leximin approximation, with the resulting lottery over configurations interpreted as connection times on the interval $[0,1]$. The utilitarian problem becomes Geographic Knapsack — choose a subset of items with total demand at most the supply $S$ whose induced subgraph together with the source $s$ is connected, maximizing total value. For trees, Algorithm 1 is an exact dynamic program on a bottom-up node ordering (nodes farther from the root get smaller indices, siblings are consecutive), storing for each prefix $[i]$ and each rounded value $j$ the minimum-demand subset of value exactly $j$ that connects to the parent $p(i)$. Value rounding with $\\theta = \\varepsilon v_{\\max}/n$ makes the running time polynomial in $n$ and $1/\\varepsilon$.","core_discovery":"The paper shows that deciding whether every household can be connected for at least half the time is NP-hard, by a reduction from Partition, so computing an egalitarian-optimal allocation is NP-hard even without geographic constraints; since every leximin-optimal allocation is egalitarian, leximin is NP-hard too. For tree networks it gives a $(1-\\varepsilon)$-leximin approximation algorithm: a generic reduction turns leximin into weighted-utilitarian optimization, and the weighted-utilitarian problem is solved as Geographic Knapsack. Over a tree, the paper's Algorithm 1 solves Geographic Knapsack exactly when values are integers, and a value-rounding step makes it an FPTAS, yielding the stated approximation in polynomial time.","pith_inferences":["The tree assumption enters only through Algorithm 1; the reduction from leximin to Geographic Knapsack is graph-agnostic, so a connected-knapsack FPTAS for general graphs would extend the same leximin guarantee without any new fairness machinery.","The proof of Lemma 1 assumes the largest-value item is feasible; a robust implementation should discard items whose demand exceeds the supply before rounding, otherwise the $(1-\\varepsilon)$ guarantee can be violated on instances where the maximum-value item can never be served.","Because utilities are all-or-nothing and additive over time and feasibility is a connectivity property, the same reduction should apply to other scarce resources with similar constraints, such as rationed water or bandwidth, not just electricity."],"forward_implications":["In a tree distribution network, a near-leximin schedule can be computed in polynomial time, so the worst-off household is guaranteed at least $(1-\\varepsilon)$ of the utility it would get in a leximin-optimal schedule, then the second-worst, and so on.","Because leximin refines egalitarian welfare, the same FPTAS is also a $(1-\\varepsilon)$-approximation to the egalitarian objective for trees.","The returned allocation is sparse: only polynomially many configurations receive positive connection time, so the schedule can be written down and implemented.","Any future improvement to the Geographic Knapsack solver — for example, an FPTAS for connected knapsack on general graphs — would automatically improve the leximin result through the same reduction."],"supporting_citations":[{"why":"Supplies the reduction theorem from leximin to weighted-utilitarian allocation; the entire FPTAS depends on this bridge.","marker":"[10]"},{"why":"The standard Knapsack FPTAS whose value-rounding technique is adapted to prove the approximation guarantee.","marker":"[23]"},{"why":"Previous bin-packing based approach for egalitarian electricity allocation that the leximin result improves on; it sets the baseline and motivation.","marker":"[5]"},{"why":"A simultaneous connected-knapsack FPTAS on general graphs; not directly applicable because of the source-connectedness requirement, but the stated route toward general networks.","marker":"[8]"}],"fun_headline_variants":["Fair power splitting is NP-hard, but trees are easy","Leximin electricity: NP-hard generally, but tree grids get FPTAS","Optimal fair electricity? NP-hard except on trees","Electricity fairness: NP-hard, but tree networks are tractable","Fair power allocation: NP-hard, but trees allow approximation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The approximation guarantee relies on the inequality that the largest item value is no more than the total value of an optimal packing, which can fail when the highest-value item is too large ever to fit in a feasible configuration.","fun_headline_variants_meta":{"raw":{"variants":["Fair power splitting is NP-hard, but trees are easy","Leximin electricity: NP-hard generally, but tree grids get FPTAS","Optimal fair electricity? NP-hard except on trees","Electricity fairness: NP-hard, but tree networks are tractable","Fair power allocation: NP-hard, but trees allow approximation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000264,"raw_usage":{"total_tokens":1584,"prompt_tokens":908,"completion_tokens":676,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":524,"completion_tokens_details":{"reasoning_tokens":590}},"tokens_in":524,"tokens_out":676,"duration_ms":6665,"temperature":1.0,"reasoning_tokens":590,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:29:33.650249+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a tree instance with a single item of value $1$ and demand larger than the supply $S$, while all feasible items together have value $1/2$. For $\\varepsilon < 1/2$, the inequality $v_{\\max} \\le \\sum_{i\\in C^*} v_i$ used in Lemma 1 is false; if Algorithm 1 on such an instance returns a packing with value below $(1-\\varepsilon)\\cdot 1/2$, the central guarantee fails, and if it does not, the theorem needs a repaired proof.","supporting_citations":[{"cited_title":"In: Proceedings of the AAAI Conference on Artificial Intelligence","cited_arxiv_id":null,"evidence_quote":"Supplies the reduction theorem from leximin to weighted-utilitarian allocation; the entire FPTAS depends on this bridge."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The standard Knapsack FPTAS whose value-rounding technique is adapted to prove the approximation guarantee."},{"cited_title":"$k$-times bin packing and its application to fair electricity distribution","cited_arxiv_id":"2311.16742","evidence_quote":"Previous bin-packing based approach for egalitarian electricity allocation that the leximin result improves on; it sets the baseline and motivation."},{"cited_title":"In: Latin American Symposium on Theoretical Informatics","cited_arxiv_id":null,"evidence_quote":"A simultaneous connected-knapsack FPTAS on general graphs; not directly applicable because of the source-connectedness requirement, but the stated route toward general networks."}],"review_version":1}