Pith. sign in

REVIEW 2 major objections 5 minor 23 references

Fairly Wired: Towards Leximin-Optimal Division of Electricity

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Fair division of scarce electricity is NP-hard, but tree networks admit a fully polynomial-time approximation scheme for leximin.

desk verdict 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. read the letter →

arxiv 2506.02193 v1 pith:TM5HHIKO submitted 2025-06-02 cs.GT cs.DScs.MA

Eden Hartman , Dinesh Kumar Baghel , Erel Segal-Halevi This is my paper
classification cs.GTcs.DScs.MA
keywords leximinapproximationegalitarianallocationNP-hardelectricitydistributionfairdivisionalgorithmsgeographicknapsacktreenetworks
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [Section 4.1, Lemma 1 (proof of Theorem 5)] 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.
  2. [Section 4.1, Algorithm 1 and Theorem 4] 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.
minor comments (5)
  1. [Abstract and Section 1] The text uses 'FTPAS' instead of 'FPTAS' in at least two places; this should be corrected.
  2. [Section 1.1] There is a typo in 'an agenF's demand'; it should read 'an agent's demand'.
  3. [Section 2, definition of X] 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.
  4. [Section 4.1, proof of Lemma 1] 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.
  5. [Section 4.1, Theorem 5 runtime proof] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the leximin-to-utilitarian reduction is imported from prior work by overlapping authors but is an independent theorem; the geographic-knapsack FPTAS is derived self-containedly.

full rationale

The paper's derivation chain is: Theorem 3 reduces leximin electricity allocation to Geographic Knapsack via the black-box reduction of Hartman et al. [10]; Algorithm 1 then solves the integer-value Geographic Knapsack instance exactly (Theorem 4, proved by induction on the DP table), with the standard rounding Lemma 1 supplying the (1-epsilon) factor. Step (i) cites prior work by two of the present authors, but the cited theorem is a parameter-free, general reduction whose stated assumptions do not include the present FPTAS, so it is independent support rather than a circular premise. Step (ii) is self-contained: the DP and its correctness proof in Section 4.1 never assume the leximin result or the output of the reduction. No fitted parameter is renamed as a prediction, no uniqueness theorem is invoked to forbid alternatives, and no ansatz is smuggled in via citation. The reviewer-identified gap in Lemma 1 (the inequality v_max <= sum_{i in C*} v_i can fail when the highest-value item has d_i > S and therefore cannot appear in any legal packing) is a correctness risk, not a circularity: it does not make the claimed approximation equivalent to an input by construction. Consequently, no specific circular reduction can be quoted, so the correct finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No free parameters or invented entities. The main external dependencies are the reduction theorem from [10] and the additive utility model; plus an unstated condition in Lemma 1 about oversized items.

assumptions (3)
  • domain assumption Theorem 2 from [10]: an alpha-approximate weighted utilitarian allocation oracle yields an alpha-leximin-approximate allocation in polynomial time.
    Central to the main result; cited from prior work by overlapping authors, not proven in this paper.
  • domain assumption Agents have uniform additive utilities: u_i(A) equals total time agent i is connected.
    Underlies the equivalence between allocations and convex combinations of configurations, and the reduction to weighted utilitarian.
  • ad hoc to paper Items with demand exceeding supply (d_i > S) are effectively excluded from legal packings; v_max is defined over fitting items so v_max <= V(C*).
    Lemma 1 requires v_max <= sum_{i in C*} v_i, which fails if the max-value item is oversized; the paper does not state this exclusion.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fairly Wired: Towards Leximin-Optimal Division of Electricity." pith.science (2026). https://pith.science/paper/TM5HHIKO

@misc{pith2026250602193,
  author       = {Pith},
  title        = {Pith review of: Fairly Wired: Towards Leximin-Optimal Division of Electricity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TM5HHIKO}},
  note         = {Machine review of arXiv:2506.02193}
}
read the original abstract

In many parts of the world - particularly in developing countries - the demand for electricity exceeds the available supply. In such cases, it is impossible to provide electricity to all households simultaneously. This raises a fundamental question: how should electricity be allocated fairly? In this paper, we explore this question through the lens of egalitarianism - a principle that emphasizes equality by prioritizing the welfare of the worst-off households. One natural rule that aligns with this principle is to maximize the egalitarian welfare - the smallest utility across all households. We show that computing such an allocation is NP-hard, even under strong simplifying assumptions. Leximin is a stronger fairness notion that generalizes the egalitarian welfare: it also requires to maximize the smallest utility, but then, subject to that, the second-smallest, then the third, and so on. The hardness results extends directly to leximin as well. Despite this, we present a Fully Polynomial-Time Approximation Scheme (FPTAS) for leximin in the special case where the network connectivity graph is a tree. This means that we can efficiently approximate leximin - and, in particular, the egalitarian welfare - to any desired level of accuracy.

Figures

Figures reproduced from arXiv: 2506.02193 by the authors.

Figure 1
Figure 1. An example graph after renumbering of the nodes. Note that the nodes farthest from the root are given the smallest numbers (1, 2, 3, 4, 5). Also, all siblings (children of the same parent node) have consecutive numbers, e.g. the siblings 7, 8, 9, 10 of parent node 12 are given consecutive numbers. Here, each of the nodes 1, 4, 5, 6, 7, 11 is a “first child”. Moreover, we have c(6) = 3, c(8) = 4, c(9) = 5, c(11) = 6,… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 20 canonical work pages

  1. [10]

    In: Proceedings of the AAAI Conference on Artificial Intelligence

    Hartman, E., Aumann, Y., Hassidim, A., Segal-Halevi, E.: Reducing leximin fairness to utilitarian op- timization. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 39, pp. 13905–13914 (2025)

    work page 2025

  2. [1]

    Akasiadis,C.,Chalkiadakis,G.:Mechanismdesignfordemand-sidemanagement.IEEEIntelligentSystems 32(1), 24–31 (Jan 2017).https://doi.org/10.1109/MIS.2017.6

    work page doi:10.1109/mis.2017.6 2017

  3. [2]

    Fair Allocation Based Soft Load Shedding

    Ali, S., Mansoor, H., Khan, I., Arshad, N., Faizullah, S., Khan, M.A.: Fair allocation based soft load shedding. Advances in Intelligent Systems and Computing1251 AISC, 407–424 (2021).https://doi. org/10.1007/978-3-030-55187-2_32, arXiv: 2002.00451 Citation Key: Ali2021 ISBN: 9783030551865

    work page Pith review arXiv 2021

  4. [3]

    2019 6th International Conference on Con- trol, Decision and Information Technologies, CoDIT 2019 p

    Azasoo, J.Q., Kanakis, T., Al-Sherbaz, A., Agyeman, M.O.: Improving electricity network efficiency and customer satisfaction in generation constrained power system. 2019 6th International Conference on Con- trol, Decision and Information Technologies, CoDIT 2019 p. 2010–2015 (2019).https://doi.org/10. 1109/CoDIT.2019.8820482, citation Key: Azasoo2019 ISBN...

    work page arXiv 2019

  5. [4]

    15156, p

    Baghel, D.K., Ravsky, A., Segal-Halevi, E.: k-Times Bin Packing and its Application to Fair Electric- ity Distribution, Lecture Notes in Computer Science, vol. 15156, p. 483–500. Springer Nature Switzer- land, Cham (2024).https://doi.org/10.1007/978-3-031-71033-9_27,https://link.springer.com/ 10.1007/978-3-031-71033-9_27

    work page doi:10.1007/978-3-031-71033-9_27 2024

  6. [5]

    Baghel, D.K., Ravsky, A., Segal-Halevi, E.:k-times bin packing and its application to fair electric- ity distribution (arXiv:2311.16742) (Jan 2025).https://doi.org/10.48550/arXiv.2311.16742,http: //arxiv.org/abs/2311.16742, arXiv:2311.16742 [cs]

    work page Pith review arXiv doi:10.48550/arxiv.2311.16742 2025

  7. [6]

    Brain, M.: How power grids work,https://www.science.smith.edu/~jcardell/Courses/EGR220/ ElecPwr_HSW.html, [Accessed 23-May-2025]

    work page 2025

  8. [7]

    Pro- ceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020-May(Aamas), 204–212 (2020), citation Key: Buermann2020

    Buermann, J., Gerding, E.H., Rastegari, B.: Fair allocation of resources with uncertain availability. Pro- ceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2020-May(Aamas), 204–212 (2020), citation Key: Buermann2020

    work page 2020

Show all 23 references
  1. [8]

    In: Latin American Symposium on Theoretical Informatics

    Dey, P., Kolay, S., Singh, S.: Knapsack: Connectedness, path, and shortest-path. In: Latin American Symposium on Theoretical Informatics. pp. 162–176. Springer (2024)

    2024

  2. [9]

    In: Proceedings of the Twenty- Eighth International Joint Conference on Artificial Intelligence

    Gerding, E.H., Perez-Diaz, A., Aziz, H., Gaspers, S., Marcu, A., Mattei, N., Walsh, T.: Fair online allo- cation of perishable goods and its application to electric vehicle charging. In: Proceedings of the Twenty- Eighth International Joint Conference on Artificial Intelligenc...

    2019

  3. [11]

    International Energy Agency: Nigeria: Electricity (2025),https://www.iea.org/countries/nigeria/ electricity, accessed: 2025-05-26

    2025

  4. [12]

    International Energy Agency: United kingdom: Electricity (2025),https://www.iea.org/countries/ united-kingdom/electricity, accessed: 2025-05-26 16 Eden Hartman, Dinesh Kumar Baghel, and Erel Segal-Halevi

    2025

  5. [13]

    Janjua, S., Ali, M.U., Kallu, K.D., Ibrahim, M.M., Zafar, A., Kim, S.: A game-theoretic approach for electricpowerdistributionduringpowershortage:Acasestudyinpakistan.AppliedSciences(Switzerland) 11(11) (2021).https://doi.org/10.3390/app11115084, citation Key: Janjua2021

    2021 doi

  6. [14]

    Renewable and Sustain- able Energy Reviews16(2), 1116–1126 (2012).https://doi.org/10.1016/j.rser.2011.11.013, citation Key: Kaygusuz2012

    Kaygusuz, K.: Energy for sustainable development: A case of developing countries. Renewable and Sustain- able Energy Reviews16(2), 1116–1126 (2012).https://doi.org/10.1016/j.rser.2011.11.013, citation Key: Kaygusuz2012

    2012 doi

  7. [15]

    In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence

    Oluwasuji, O.I., Malik, O., Zhang, J., Ramchurn, S.D.: Algorithms for fair load shedding in developing countries. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. p. 1590–1596. International Joint Conferences on Artificial Intell...

    2018 doi

  8. [16]

    Autonomous Agents and Multi-Agent Systems34(1), 12 (Apr 2020).https: //doi.org/10.1007/s10458-019-09428-8

    Oluwasuji, O.I., Malik, O., Zhang, J., Ramchurn, S.D.: Solving the fair electric load shedding problem in developing countries. Autonomous Agents and Multi-Agent Systems34(1), 12 (Apr 2020).https: //doi.org/10.1007/s10458-019-09428-8

    2020 doi

  9. [17]

    Energy, Sustainability and Society p

    Oyedepo, S.O.: Energy and sustainable development in nigeria: the way forward sustainable energy renew- able energy energy efficiency energy conservation review background. Energy, Sustainability and Society p. 1–17 (2012)

    2012

  10. [18]

    Electric Power Components and Systems41(9), 879–895 (2013).https://doi.org/10.1080/ 15325008.2013.792884

    Pahwa, S., Scoglio, C., Das, S., Schulz, N.: Load-shedding strategies for preventing cascading failures in power grid. Electric Power Components and Systems41(9), 879–895 (2013).https://doi.org/10.1080/ 15325008.2013.792884

    2013

  11. [19]

    International Journal of Electrical Power and Energy Systems67, 582–590 (2015).https: //doi.org/10.1016/j.ijepes.2014.12.041, citation Key: Shi2015

    Shi, B., Liu, J.: Decentralized control and fair load-shedding compensations to prevent cascading failures in a smart grid. International Journal of Electrical Power and Energy Systems67, 582–590 (2015).https: //doi.org/10.1016/j.ijepes.2014.12.041, citation Key: Shi2015

    2015 doi

  12. [20]

    Statista: Nigeria: population 1950-2024 (2025),https://www.statista.com/statistics/1122838/ population-of-nigeria/, accessed: 2025-05-26

    2025

  13. [21]

    Statista: United kingdom: Total population from 1887 to 2023 (2025),https://www.statista.com/ statistics/281296/uk-population/, accessed: 2025-05-26

    2025

  14. [22]

    11th International Conference on Autonomous Agents and Multiagent Systems 2012, AAMAS 2012: Innovative Applications Track2(June), 568–575 (2012), citation Key: Stein2012

    Stein, S., Gerding, E., Robu, V., Jennings, N.R.: A model-based online mechanism with pre-commitment and its application to electric vehicle charging. 11th International Conference on Autonomous Agents and Multiagent Systems 2012, AAMAS 2012: Innovative Applications Track2(Jun...

    2012

  15. [23]

    Vazirani, V.V.: Approximation algorithms, vol. 1. Springer (2001)

    2001

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.