pith. sign in

arxiv: 2605.15750 · v1 · pith:KVBSXZBZnew · submitted 2026-05-15 · 📡 eess.SY · cs.SY

Fairness-Guaranteed Online Power Allocation Policies for EV Fast Charging Stations

Can Berk Saner , Yong-Sheng Soh , Antonios Varvitsiotis This is my paper

Pith reviewed 2026-05-20 17:05 UTC · model grok-4.3

classification 📡 eess.SY cs.SY
keywords EV fast chargingpower allocationfairnessenvy-freenessPareto efficiencyproportionalityonline algorithmscharging stations
0
0 comments X

The pith

Two online algorithms allocate power at EV fast charging stations fairly using only instantaneous requests while guaranteeing envy-freeness, Pareto efficiency, and proportionality.

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

The paper presents two online power allocation policies for fast charging stations that deliver fairness guarantees without any prior knowledge of EV charge curves. FAIR-OPAP-C handles stations with continuously adjustable power while FAIR-OPAP-M manages modular stations with discrete power units. Both methods rely solely on real-time power requests available through standard protocols and enforce a unified fairness definition that combines envy-freeness, Pareto efficiency, and proportionality. This setup addresses oversubscribed stations where total available power is capped, allowing equitable access and high utilization in real time on constrained hardware.

Core claim

The authors formalize fairness in EV power allocation with a unified framework that includes envy-freeness, Pareto efficiency, and proportionality. They introduce FAIR-OPAP-C for conventional stations with continuous power delivery and FAIR-OPAP-M for modular stations with discrete modules, both providing theoretical guarantees while depending only on instantaneous power requests from standard protocols.

What carries the argument

The FAIR-OPAP-C and FAIR-OPAP-M online policies that enforce the unified fairness framework using only current power requests.

If this is right

  • The policies achieve near-linear scalability for conventional stations and logarithmic scalability for modular stations.
  • They deliver superior performance across metrics compared to seven existing benchmarks from EV charging and fair division literature.
  • Runtimes remain below 1 ms even for 300 EVs, supporting real-time operation on edge devices.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same request-only approach could extend to other constrained resource allocation settings with unknown per-user demand functions.
  • Infrastructure operators could deploy these methods without collecting proprietary EV battery data.
  • Integration with dynamic grid signals might allow fairness to coexist with system-level objectives like peak shaving.

Load-bearing premise

The fairness guarantees hold when the algorithms use only instantaneous power requests without any prior knowledge of state-of-charge dependent charge curves.

What would settle it

A simulation or deployment where users experience envy or the allocation is not Pareto efficient despite following the policies with varying EV power limits would falsify the theoretical guarantees.

Figures

Figures reproduced from arXiv: 2605.15750 by Antonios Varvitsiotis, Can Berk Saner, Yong-Sheng Soh.

Figure 1
Figure 1. Figure 1: Charge curves of different EV models (Data source: [ [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Conventional vs. modular architectures. The discrete nature of modular FCSs makes most power allocation strategies developed for conventional FCSs unsuit￾able. Despite their growing deployment, literature accounting for modular operational constraints remains limited [13], [21], and none incorporate the online setting. B. Contributions Existing power allocation methods typically assume con￾ventional FCS ar… view at source ↗
Figure 3
Figure 3. Figure 3: Comprehensive performance comparison of all evaluated power allocation policies across both conventional (top panel) and modular (bottom panel) [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Responsiveness to dynamic exogenous power caps of F [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Computational time as a function of the number of connected EVs: [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
read the original abstract

The rapid expansion of electric vehicles (EVs) necessitates scalable and efficient fast charging station (FCS) infrastructure. These stations often operate in oversubscribed configurations where the total port rating exceeds a station-level cap reflecting infrastructure limits, grid constraints or market setpoints. In such settings, ensuring fairness in real-time power allocation is essential to prevent user bias and secure equitable access to limited resources while maximizing infrastructure utilization. This task is further complicated by state-of-charge dependent EV power limits defined by charge curves, for which accurate data is often unavailable. This paper introduces two fairness-guaranteed online power allocation policies: FAIR-OPAP-C for conventional FCSs with continuously adjustable power delivery, and FAIR-OPAP-M for modular FCSs composed of discrete assignable power modules. Unlike existing methods, these algorithms require no prior knowledge of charge curves, utilizing only instantaneous power requests available via standard protocols. We formalize fairness with a unified framework encompassing envy-freeness, Pareto efficiency, and proportionality, and establish theoretical guarantees for both algorithms. The algorithms rely on lightweight operations, achieving near-linear and logarithmic scalability for the conventional and modular cases, respectively. Comprehensive evaluations show the proposed methods achieve superior performance across various metrics among seven benchmarks from EV charging and fair division literature. Furthermore, they are orders of magnitude faster than optimization-based approaches, with runtimes below 1 ms for up to 300 EVs, validating their suitability for real-time deployment on hardware-constrained edge devices.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper proposes two online power allocation algorithms, FAIR-OPAP-C for continuously adjustable power and FAIR-OPAP-M for discrete modular power units, to allocate limited station power to EVs in real time. It defines a unified fairness framework based on envy-freeness, Pareto efficiency, and proportionality; claims theoretical guarantees for these properties using only instantaneous power requests (no prior charge-curve knowledge); reports near-linear and logarithmic computational scaling; and shows superior empirical performance versus seven benchmarks from the EV-charging and fair-division literatures, with sub-millisecond runtimes up to 300 EVs.

Significance. If the theoretical guarantees are rigorously established, the contribution is meaningful: it supplies practical, protocol-compatible policies that simultaneously enforce multiple fairness notions while remaining computationally lightweight enough for edge deployment. The extensive benchmarking and explicit complexity claims are strengths that would support adoption in oversubscribed fast-charging infrastructure.

major comments (1)
  1. [§4] §4 (Theoretical Analysis): The central claim that both algorithms maintain long-term proportionality and envy-freeness under unknown, state-dependent charge curves is load-bearing yet insufficiently supported. The provided abstract and high-level description give no indication of a Lyapunov-style drift argument or explicit deviation bound that would carry fairness forward when an EV’s feasible power drops after an allocation; an instantaneous-request policy can produce an allocation that is envy-free at t but Pareto-dominated or proportionality-violating at t+1 once the charge curve changes.
minor comments (2)
  1. [Abstract] Abstract: the phrases “near-linear and logarithmic scalability” and “unified framework” would benefit from explicit big-O statements and a one-sentence enumeration of the three fairness axioms.
  2. [Algorithms and Figures] Figure captions and algorithm pseudocode: variable names for instantaneous power requests versus feasible limits should be distinguished typographically to avoid reader confusion when charge curves are later introduced.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their constructive and detailed review of our manuscript. We address the major comment on the theoretical analysis below, providing clarification on the scope of our guarantees while revising the manuscript to improve exposition.

read point-by-point responses

  1. Referee: [§4] §4 (Theoretical Analysis): The central claim that both algorithms maintain long-term proportionality and envy-freeness under unknown, state-dependent charge curves is load-bearing yet insufficiently supported. The provided abstract and high-level description give no indication of a Lyapunov-style drift argument or explicit deviation bound that would carry fairness forward when an EV’s feasible power drops after an allocation; an instantaneous-request policy can produce an allocation that is envy-free at t but Pareto-dominated or proportionality-violating at t+1 once the charge curve changes.

    Authors: We appreciate the referee’s observation regarding the dynamic nature of fairness under evolving charge curves. Our analysis in §4 establishes that, at each discrete time step t and given only the instantaneous power requests (which encode the current feasible sets induced by the unknown, state-dependent charge curves), both FAIR-OPAP-C and FAIR-OPAP-M produce allocations that are envy-free, Pareto efficient, and proportional with respect to those instantaneous requests. Because the policies are purely online and recompute the allocation from scratch at every decision epoch using the latest requests, any change in an EV’s feasible power is immediately reflected in the subsequent round; thus the per-step properties are re-established before the next allocation occurs. We do not claim or derive a Lyapunov drift bound on cumulative long-term fairness metrics, as our contribution centers on lightweight, protocol-compatible policies that enforce the three fairness notions instantaneously without requiring charge-curve models. We have revised §4 to include an explicit remark clarifying this dynamic, per-step maintenance and added a short corollary discussing why repeated application precludes persistent Pareto domination or proportionality violations across steps. If the referee considers a formal long-term deviation bound essential, we are prepared to explore its inclusion. revision: partial

Circularity Check

0 steps flagged

No circularity: fairness guarantees follow from explicit definitions and algorithmic construction

full rationale

The paper introduces standard fair-division properties (envy-freeness, Pareto efficiency, proportionality) as a unified framework and then designs two online policies whose rules are shown to satisfy those properties by direct construction using only instantaneous power requests. No parameter is fitted to data and then relabeled as a prediction, no self-citation supplies a load-bearing uniqueness theorem, and no ansatz is smuggled in. The derivation chain is therefore self-contained against external benchmarks and does not reduce any claimed guarantee to its own inputs by definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard fair-division concepts applied to the EV charging domain and the modeling choice that instantaneous power requests are sufficient inputs.

axioms (1)
  • domain assumption Envy-freeness, Pareto efficiency, and proportionality together constitute an appropriate unified fairness framework for real-time EV power allocation.
    Invoked to formalize fairness and establish theoretical guarantees.

pith-pipeline@v0.9.0 · 5802 in / 1246 out tokens · 71585 ms · 2026-05-20T17:05:29.708071+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

49 extracted references · 49 canonical work pages

  1. [1]

    (2025) Global EV Outlook 2025

    International Energy Agency (IEA). (2025) Global EV Outlook 2025. Accessed: May 10, 2026. [Online]. Available: https://www.iea.org/repo rts/global-ev-outlook-2025

    work page 2025

  2. [2]

    (2022) Policy Brief on Public Charging Infrastructure

    ——. (2022) Policy Brief on Public Charging Infrastructure. Accessed: May 10, 2026. [Online]. Available: https://www.iea.org/reports/policy-b rief-on-public-charging-infrastructure

    work page 2022

  3. [3]

    (2023) The Critical Role of UL 60730-1 in Oversubscribing EV Charging Sites

    Ampcontrol. (2023) The Critical Role of UL 60730-1 in Oversubscribing EV Charging Sites. Accessed: May 10, 2026. [Online]. Available: https: //www.ampcontrol.io/post/the-critical-role-of-ul-60730-1-in-oversubsc ribing-ev-charging-sites

    work page 2023

  4. [4]

    Adaptive charging networks: A framework for smart electric vehicle charging,

    Z. J. Lee, G. Lee, T. Lee, C. Jin, R. Lee, Z. Low, D. Chang, C. Ortega, and S. H. Low, “Adaptive charging networks: A framework for smart electric vehicle charging,”IEEE Trans. Smart Grid, vol. 12, no. 5, pp. 4339–4350, 2021

    work page 2021

  5. [5]

    Department of Transportation

    U.S. Department of Transportation. (2025) Types of EV Infrastructure Planning. Accessed: May 10, 2026. [Online]. Available: https://www.tr ansportation.gov/rural/ev/toolkit/ev-infrastructure-planning/planning-t ypes

    work page 2025

  6. [6]

    Optimization of multiport dc fast charging stations operating with power cap policy,

    R. Buckreus, R. Aksu, M. Kisacikoglu, M. Yavuz, and B. Balasubra- manian, “Optimization of multiport dc fast charging stations operating with power cap policy,”IEEE Trans. Transp. Electrific., vol. 7, no. 4, pp. 2402–2413, 2021

    work page 2021

  7. [7]

    Analysis of the simultaneity factor of fast-charging sites using monte-carlo simulation,

    F. Silber, S. Scheubner, and A. M ¨artz, “Analysis of the simultaneity factor of fast-charging sites using monte-carlo simulation,”Int. J. Electr. Power Energy Syst., vol. 155, p. 109540, 2024

    work page 2024

  8. [8]

    Electric Vehicle Database,

    EV-Database.org., “Electric Vehicle Database,” 2025, accessed: May 10,

    work page 2025

  9. [9]

    Available: http://ev-database.org

    [Online]. Available: http://ev-database.org

    work page

  10. [10]

    Opti- mization techniques in electric vehicle charging scheduling, routing and spatio-temporal demand coordination: a systematic review,

    E. Elghanam, A. Abdelfatah, M. S. Hassan, and A. Osman, “Opti- mization techniques in electric vehicle charging scheduling, routing and spatio-temporal demand coordination: a systematic review,”IEEE Open J. Veh. Technol., 2024

    work page 2024

  11. [11]

    Optimal dynamic power allocation for electric vehicles in an extreme fast charging station,

    H. Ren, Y . Zhou, F. Wen, and Z. Liu, “Optimal dynamic power allocation for electric vehicles in an extreme fast charging station,”Appl. Energy, vol. 349, p. 121497, 2023

    work page 2023

  12. [12]

    Energy consumption optimization for the electric vehicle routing problem with state-of-charge-dependent discharging rates,

    Y . J. Kim and B. Do Chung, “Energy consumption optimization for the electric vehicle routing problem with state-of-charge-dependent discharging rates,”J. Clean. Prod., vol. 385, p. 135703, 2023

    work page 2023

  13. [13]

    Smoothed least-laxity-first algorithm for electric vehicle charging: Online decision and performance analysis with resource augmentation,

    N. Chen, C. Kurniawan, Y . Nakahira, L. Chen, and S. H. Low, “Smoothed least-laxity-first algorithm for electric vehicle charging: Online decision and performance analysis with resource augmentation,” IEEE Trans. Smart Grid, vol. 13, no. 3, pp. 2209–2217, 2021

    work page 2021

  14. [14]

    Surrogate-assisted combina- torial optimization of ev fast charging stations,

    J. Lin, D. Gebbran, and T. Dragi ˇcevi´c, “Surrogate-assisted combina- torial optimization of ev fast charging stations,”IEEE Trans. Transp. Electrific., vol. 10, no. 1, pp. 2183–2191, 2023

    work page 2023

  15. [15]

    Combination of charging policies for fair and efficient ev charging under limited capacity,

    S. Limmer and T. Rodemann, “Combination of charging policies for fair and efficient ev charging under limited capacity,” in2024 22nd Int. Conf. Intell. Syst. Appl. Power Syst. (ISAP). IEEE, 2024, pp. 1–6

    work page 2024

  16. [16]

    Conic optimization for electric vehicle station smart charging with battery voltage constraints,

    T. Morstyn, C. Crozier, M. Deakin, and M. D. McCulloch, “Conic optimization for electric vehicle station smart charging with battery voltage constraints,”IEEE Trans. Transp. Electrific., vol. 6, no. 2, pp. 478–487, 2020

    work page 2020

  17. [17]

    The impact of considering state-of-charge-dependent maximum charging powers on the optimal electric vehicle charging scheduling,

    K. Qian, R. Fachrizal, J. Munkhammar, T. Ebel, and R. C. Adam, “The impact of considering state-of-charge-dependent maximum charging powers on the optimal electric vehicle charging scheduling,”IEEE Trans. Transp. Electrific., vol. 9, no. 3, pp. 4517–4530, 2023

    work page 2023

  18. [18]

    Hierarchical game for networked electric vehicle public charging under time-based billing model,

    Y . Yu, C. Su, X. Tang, B. Kim, T. Song, and Z. Han, “Hierarchical game for networked electric vehicle public charging under time-based billing model,”IEEE Trans. Intell. Transp. Syst., vol. 22, no. 1, pp. 518–530, 2020

    work page 2020

  19. [19]

    Smart charging of electric vehicles considering soc-dependent maximum charging powers,

    B. Schaden, T. Jatschka, S. Limmer, and G. R. Raidl, “Smart charging of electric vehicles considering soc-dependent maximum charging powers,” Energies, vol. 14, no. 22, p. 7755, 2021

    work page 2021

  20. [20]

    Fair and efficient electric vehicle charging scheduling optimization considering the maximum individual waiting time and operating cost,

    M. Tan, Y . Ren, R. Pan, L. Wang, and J. Chen, “Fair and efficient electric vehicle charging scheduling optimization considering the maximum individual waiting time and operating cost,”IEEE Trans. Veh. Technol., vol. 72, no. 8, pp. 9808–9820, 2023

    work page 2023

  21. [21]

    A charge curve and battery management system aware optimal charging scheduling framework for electric vehicle fast charging stations with heterogeneous customer mix,

    C. B. Saner, J. Saha, and D. Srinivasan, “A charge curve and battery management system aware optimal charging scheduling framework for electric vehicle fast charging stations with heterogeneous customer mix,” IEEE Trans. Intell. Transp. Syst., vol. 24, no. 12, pp. 14 890–14 902, 2023

    work page 2023

  22. [22]

    A social welfare theory-inspired lexicographic optimal charging scheduling framework for modular ev fast charging stations,

    ——, “A social welfare theory-inspired lexicographic optimal charging scheduling framework for modular ev fast charging stations,”IEEE Trans. Intell. Transp. Syst., vol. 25, no. 11, pp. 18 648–18 660, 2024

    work page 2024

  23. [23]

    An investigation into key influence factors for the everyday usability of electric vehicles,

    A. T. Thorgeirsson, S. Scheubner, S. F ¨unfgeld, and F. Gauterin, “An investigation into key influence factors for the everyday usability of electric vehicles,”IEEE Open J. Veh. Technol., vol. 1, pp. 348–361, 2020

    work page 2020

  24. [24]

    Effect of ambient temperature on ev charging curves after seven years of ev operation,

    V . Blazek, I. Pergl, P. Kedron, M. Piecha, and M. Bajaj, “Effect of ambient temperature on ev charging curves after seven years of ev operation,” in2023 23rd Int. Sci. Conf. Electr. Power Eng. (EPE). IEEE, 2023, pp. 1–5

    work page 2023

  25. [25]

    Diffcharge: Generating ev charging scenarios via a denoising diffusion model,

    S. Li, H. Xiong, and Y . Chen, “Diffcharge: Generating ev charging scenarios via a denoising diffusion model,”IEEE Trans. Smart Grid, vol. 15, no. 4, pp. 3936–3949, 2024. [25]ISO 15118-1:2019: Road vehicles — Vehicle to grid communication interface, International Organization for Standardization Std., 2019. 10

    work page 2024

  26. [26]

    (2025) Terra HP Charger – Up to 350 kW

    ABB. (2025) Terra HP Charger – Up to 350 kW. Accessed: May 10,

    work page 2025

  27. [27]

    Available: https://new.abb.com/ev-charging/high-power -charging

    [Online]. Available: https://new.abb.com/ev-charging/high-power -charging

    work page

  28. [28]

    (2025) Kempower Power Unit

    Kempower. (2025) Kempower Power Unit. Accessed: May 10, 2026. [Online]. Available: https://kempower.com/solution/kempower-power-u nit/

    work page 2025

  29. [29]

    (2025) Troniq Modular

    EVBox. (2025) Troniq Modular. Accessed: May 10, 2026. [Online]. Available: https://evbox.com/en/ev-chargers/troniq-modular

    work page 2025

  30. [30]

    Brandt, V

    F. Brandt, V . Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, Handbook of computational social choice. Cambridge University Press, 2016

    work page 2016

  31. [31]

    B. J. Plaut,Algorithms for Fair Public and Private Resource Allocation. Stanford University, 2021

    work page 2021

  32. [32]

    An internet- inspired proportional fair ev charging control method,

    E. Ucer, M. C. Kisacikoglu, M. Yuksel, and A. C. Gurbuz, “An internet- inspired proportional fair ev charging control method,”IEEE Syst. J., vol. 13, no. 4, pp. 4292–4302, 2019

    work page 2019

  33. [33]

    Proportionally fair and scalable ev charging under distribution line voltage constraints,

    T. Theodoropoulos, P. Pantazopoulos, E. Karfopoulos, P. Lytrivis, G. Karaseitanidis, and A. Amditis, “Proportionally fair and scalable ev charging under distribution line voltage constraints,”Electr. Power Syst. Res., vol. 208, p. 107797, 2022

    work page 2022

  34. [34]

    Fair and scalable electric vehicle charging under electrical grid constraints,

    G. Tsaousoglou, J. S. Giraldo, P. Pinson, and N. G. Paterakis, “Fair and scalable electric vehicle charging under electrical grid constraints,”IEEE Trans. Intell. Transp. Syst., vol. 24, no. 12, pp. 15 169–15 177, 2023

    work page 2023

  35. [35]

    Equity, envy, and efficiency,

    H. R. Varian, “Equity, envy, and efficiency,”J. Econ. Theory, vol. 9, no. 1, pp. 63–91, 1974

    work page 1974

  36. [36]

    Fair online allocation of perishable goods and its application to electric vehicle charging,

    E. H. Gerding, A. Perez-Diaz, H. Aziz, S. Gaspers, A. Marcu, N. Mattei, and T. Walsh, “Fair online allocation of perishable goods and its application to electric vehicle charging,” inProceedings of IJCAI-19, 2019, pp. 5569–5575

    work page 2019

  37. [37]

    Sequential fair alloca- tion of limited resources under stochastic demands,

    S. R. Sinclair, G. Jain, S. Banerjee, and C. L. Yu, “Sequential fair alloca- tion of limited resources under stochastic demands,”arXiv:2011.14382, 2020

    work page arXiv 2011

  38. [38]

    Bertsekas and R

    D. Bertsekas and R. Gallager,Data networks. Prentice Hall, 1992

    work page 1992

  39. [39]

    Max-min fairness and its applications to routing and load-balancing in communication networks: a tutorial,

    D. Nace and M. Pi ´oro, “Max-min fairness and its applications to routing and load-balancing in communication networks: a tutorial,”IEEE Communications surveys & tutorials, vol. 10, no. 4, pp. 5–17, 2009

    work page 2009

  40. [40]

    The unreasonable fairness of maximum nash welfare,

    I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang, “The unreasonable fairness of maximum nash welfare,”ACM Trans. Econ. Comput., vol. 7, no. 3, pp. 1–32, 2019

    work page 2019

  41. [41]

    A fair share scheduler,

    J. Kay and P. Lauder, “A fair share scheduler,”Commun. ACM, vol. 31, no. 1, pp. 44–55, 1988

    work page 1988

  42. [42]

    J. A. Stankovic, M. Spuri, K. Ramamritham, and G. Buttazzo,Deadline scheduling for real-time systems: EDF and related algorithms. Springer, 1998, vol. 460

    work page 1998

  43. [43]

    MOSEK ApS,MOSEK Optimization Toolbox for MATLAB, Apr. 2025. [Online]. Available: https://docs.mosek.com/11.0/matlabapi.pdf APPENDIX A. Proof of Theorem 1 We prove the theorem by verifying that the allocation produced by FAIR-OPAP-C (Alg. 1) satisfies the three fairness criteria: envy-freeness, Pareto efficiency, and proportionality. We first handle the tr...

    work page 2025

  44. [44]

    (i)𝑖∈ F:𝑢 𝑖 (𝑝 𝑖)=1≥𝑢 𝑖 (𝑝 𝑗 )for all𝑗

    Envy-Freeness:We verify𝑢 𝑖 (𝑝 𝑖) ≥𝑢 𝑖 (𝑝 𝑗 )for all𝑖, 𝑗. (i)𝑖∈ F:𝑢 𝑖 (𝑝 𝑖)=1≥𝑢 𝑖 (𝑝 𝑗 )for all𝑗. No envy. (ii)𝑖, 𝑗∈ U:𝑝 𝑖 =𝑝 𝑗 =𝜔 ∗, so𝑢 𝑖 (𝑝 𝑖)=𝑢 𝑖 (𝑝 𝑗 ). No envy. (iii)𝑖∈ U, 𝑗∈ F: By the Lemma 1,𝑝 𝑖 =𝜔 ∗ ≥𝑝 req 𝑗 =𝑝 𝑗. Since𝑢 𝑖 (·)is non-decreasing,𝑢 𝑖 (𝑝 𝑖) ≥𝑢 𝑖 (𝑝 𝑗 ). No envy. All cases are covered. The allocation is envy-free.□

    work page

  45. [45]

    (i) We claim𝑝 𝑖 =min(𝜔 ∗, 𝑝req 𝑖 ) ≤𝑝 req 𝑖 for all𝑖∈ E

    Pareto Efficiency:We establish two properties and show they together imply Pareto efficiency. (i) We claim𝑝 𝑖 =min(𝜔 ∗, 𝑝req 𝑖 ) ≤𝑝 req 𝑖 for all𝑖∈ E. For 𝑖∈ F, the algorithm sets𝑝 𝑖 =𝑝 req 𝑖 , and by the Lemma 1,𝜔 ∗ ≥𝑝 req 𝑖 , so𝑝 𝑖 =𝑝 req 𝑖 =min(𝜔 ∗, 𝑝req 𝑖 ). For𝑖∈ U, the algorithm sets𝑝 𝑖 =𝜔 ∗ via the else branch. Since EVs are processed in ascending ...

    work page

  46. [46]

    Since we are considering the caseU≠∅, (otherwise, fairness is trivial),𝑝 CS < Í 𝑖 𝑝req 𝑖 holds, so𝐶 0 =𝑝 CS and the initial value of𝜔is𝑝 CS/|E |

    Proportionality:We show𝑢 𝑖 (𝑝 𝑖) ≥𝑢 𝑖 (𝑝 CS)/|E |for all 𝑖∈ E. Since we are considering the caseU≠∅, (otherwise, fairness is trivial),𝑝 CS < Í 𝑖 𝑝req 𝑖 holds, so𝐶 0 =𝑝 CS and the initial value of𝜔is𝑝 CS/|E |. By the Lemma 1,𝜔 ∗ ≥𝑝 CS/|E |. For𝑖∈ F:𝑢 𝑖 (𝑝 𝑖)=1≥𝑢 𝑖 (𝑝 CS)/|E |, since𝑢 𝑖 (𝑝 CS) ≤1. On the other hand, for𝑖∈ U:𝑝 𝑖 =𝜔 ∗ ≥𝑝 CS/|E |. We use the p...

    work page

  47. [47]

    Here, we use the convention𝑢 𝑖 (𝑥)=0for𝑥 <0

    EF1:We verify𝑢 𝑖 (𝑚 𝑖) ≥𝑢 𝑖 (𝑚 𝑗 −1)for all𝑖, 𝑗∈ E. Here, we use the convention𝑢 𝑖 (𝑥)=0for𝑥 <0. (i)𝑖∈ F:𝑢 𝑖 (𝑚 𝑖)=1≥𝑢 𝑖 (𝑚 𝑗 −1)for all𝑗. (ii)𝑖, 𝑗∈ U: By Lemma 2, all EVs inUhave the same allocation at the start of the final round; the final partial round, if any, increases some but not all by 1. Hence |𝑚 𝑖 −𝑚 𝑗 | ≤1, so𝑚 𝑖 ≥𝑚 𝑗 −1. Since𝑢 𝑖 (·)is non- d...

    work page

  48. [48]

    (i) We claim𝑚 𝑖 ≤ ⌈𝑚 req 𝑖 ⌉for all𝑖∈ E

    Pareto Efficiency:We establish two conditions and show they together imply Pareto efficiency. (i) We claim𝑚 𝑖 ≤ ⌈𝑚 req 𝑖 ⌉for all𝑖∈ E. For𝑖∈ F, the algorithm removes𝑖fromUexactly when𝑚 𝑖 =⌈𝑚 req 𝑖 ⌉, after which𝑖receives no further modules, so𝑚 𝑖 =⌈𝑚 req 𝑖 ⌉. For𝑖∈ U, if𝑚 𝑖 had reached⌈𝑚 req 𝑖 ⌉, the algorithm would have removed𝑖fromU, contradicting𝑖∈ U. ...

    work page

  49. [49]

    For𝑖∈ F,𝑢 𝑖 (𝑚 𝑖)=1, so proportionality holds trivially

    Proportionality:We show𝑢 𝑖 (𝑚 𝑖) ≥𝑢 𝑖 (𝑚CS)/|E |for all 𝑖∈ E. For𝑖∈ F,𝑢 𝑖 (𝑚 𝑖)=1, so proportionality holds trivially. If there exists some𝑖∈ U, then not all rounded demands were satisfied, and therefore𝐶 0 =𝑚 CS < Í 𝑗 ⌈𝑚req 𝑗 ⌉. We use this fact to establish a lower bound on𝑚 𝑖. Lemma 3(Lower bound for unfulfilled EVs).For all𝑖∈ U, 𝑚𝑖 ≥ ⌊𝑚 CS/|E |⌋. Proo...

    work page