PaperlayerView exact revision on arXiv

Source-linked AI summary

Peak-Aware One-Way Trading: Competitive and Learning-Augmented Algorithms for Energy Procurement

Jackson Bibbens, Adam Lechowicz, Nicolas Christianson, Bo Sun, Mohammad Hajiesmaili

arXiv:2610.31447v1cs.DS

TL;DR

Online buyers must meet a fixed purchasing obligation despite unknown prices, while a peak charge makes concentrated low-price buying costly. The paper develops competitive and prediction-augmented algorithms for this trade-off, with order-optimal guarantees and a case study showing the value of forecast-based advice.

  • Problem

    PA-OWT asks how to meet a fixed purchasing obligation by a deadline under unknown prices while balancing purchase cost against a charge on the largest purchase.

    Source: §1 · p. 1

  • Method

    The paper develops dual-threshold PAWS and extends it to PAWS-DA, which uses predicted per-round purchasing decisions while controlling the consistency–robustness trade-off.

    Source: §5 · p. 11, §5.3 · p. 14, §7 · pp. 19–20

  • Results

    PAWS and PAWS-DA achieve order-optimal guarantees; with near-optimal forecast-based advice, PAWS-DA [ξ=0.75] performs nearly identically to blind advice following.

    Source: §6.2 · p. 18, §7 · p. 20

  • Takeaways & Limitations

    In the electricity case study, day-ahead forecasts provide near-optimal advice, and PAWS-DA performance improves as it uses more of that advice.

    Source: §6.2 · p. 18

    The model considers a single purchasing obligation over a fixed horizon, and the learning-augmented algorithms focus on decision advice.

    Source: §7 · p. 20

Abstract

from arXiv · show

We introduce peak-aware one-way trading ($\texttt{PA-OWT}$), an online problem in which a player must purchase a fixed quantity of an asset by a deadline, minimizing its total cost plus a charge proportional to the largest single purchase at any time. The model is motivated by electricity procurement, where the cost of energy rewards buying at low prices, but peak demand charges discourage concentrating purchases in short periods. Balancing these incentives is challenging when future prices are unknown: a large purchase can establish a peak that later decisions cannot undo. We develop a peak-aware online algorithm that balances price and peak control with deadline feasibility and achieves the order-optimal competitive ratio. We further extend our results to a learning-augmented algorithm that uses predictions of optimal purchasing decisions to achieve an order-optimal consistency-robustness tradeoff, exploiting accurate advice while retaining worst-case guarantees in the face of arbitrary prediction errors. Finally, we evaluate our algorithms in a case study on electricity procurement using historical electricity price traces to understand the benefits of peak-aware purchasing.

1 Introduction

PA-OWT adds a charge on the largest purchase to flexible online buying, creating tension between exploiting low prices and spreading purchases. The paper develops competitive and prediction-using algorithms and distinguishes this setting from related online-search and peak-aware scheduling models.

1 Introduction

  • The peak charge makes a low-price purchase risky because later cheap prices may arrive, while delaying too much can force a large purchase near the deadline.Electricity bills can combine time-varying energy charges with demand charges based on the highest power demand.Source: §1 · pp. 1–2

1.1 Contributions

  • PAWS achieves the order-optimal competitive ratio for known horizons, while the unknown-horizon setting has a linear lower bound of Ω(T).The known-horizon bound is U/(L+C/T); the unknown-horizon lower bound motivates the paper’s focus on known horizons.Source: §1.1 · pp. 2–3
  • PAWS-DA matches the order-optimal consistency–robustness trade-off, whereas a naive convex combination of PAWS and advice has robustness linear in T.The paper first establishes a lower bound on the achievable trade-off for learning-augmented algorithms.Source: §1.1 · p. 3
  • In the four-region electricity case study, day-ahead prices provide effective advice, and learning-augmented algorithms perform within approximately 20% of the offline optimum on average.Empirical behavior generally follows the theoretical results despite the predictable, non-adversarial test instances.Source: §1.1 · p. 3

1.2 Related Work

  • PA-OWT combines one-way trading’s flexible, horizon-wide demand with time-varying prices and a peak penalty, a combination distinct from prior online-search and peak-aware scheduling models.Prior online-search work lacks peak-purchase costs, while much peak-aware dispatch work uses inelastic demand or lacks formal guarantees for flexible demand with time-varying prices.Source: §1 · p. 2, §1.2 · p. 4

2 Problem and Preliminaries

PA-OWT requires online purchases to meet a fixed quantity by a deadline while minimizing both purchase cost and a charge on the largest purchase. The analysis assumes bounded prices and a known horizon, and establishes a linear competitive lower bound when the horizon is unknown.

2.1 Problem Formulation

  • The player buys at least one unit across T rounds, paying p_t x_t for each purchase and a peak charge C max_t x_t; decisions are irrevocable and future prices are unknown.Any quantity still needed in the final round must be purchased then, affecting both purchase cost and the peak charge.Source: §2.1 · p. 5

2.2 Preliminaries & Assumptions

  • The analysis assumes known price bounds 0≤L≤U and a horizon T known in advance; prices otherwise vary arbitrarily, with no stochastic model or future-price access.The paper also restricts attention to deterministic algorithms, noting that convexity permits derandomization without increasing total cost.Source: §2.2 · pp. 6–7
  • When L=0, C≤U, and T is unknown, every algorithm has competitive ratio Ω(T), which is tight up to constant factors in this setting.The proof forces a choice between an early irreversible purchase if cheap prices continue and an expensive compulsory purchase if the horizon ends.Source: §2.2 · p. 6
  • For PA-OWT, when C≥(T−1)(U−L), uniform purchasing x_t=1/T for all t is optimal; the paper therefore assumes C<(T−1)(U−L).Source: §2.2 · p. 7

3 Competitive Algorithms for PA-OWT

PAWS uses a water-level threshold and purchase-rate cap to balance energy cost against peak charges while meeting the deadline. It achieves a competitive ratio at most 2√κ, matching the order of the lower bound up to constant factors.

3 Competitive Algorithms for PA-OWT

  • PAWS achieves a competitive ratio at most 2√κ, and the paper identifies this as order-optimal.The matching lower bound is established in Section 4.Source: §3 · p. 7

3.1 Designing Peak-Aware Water Level Smoothing

  • The offline optimum has a water-filling structure: it purchases equally in slots priced at or below the optimal dual water level.The number of qualifying slots determines the equal purchase amount; learning the water level and how many slots to use are online challenges.Source: §3.1 · p. 8
  • PAWS targets a water level Φ, buying more when prices are farther below it, while limiting purchases to control peak charges and preserve deadline feasibility.If the remaining demand cannot be met under the purchase cap, compulsory purchases begin and subsequent purchases are capped.Source: §3.1 · p. 8

3.2 Competitive Analysis

  • When the offline comparison condition F(Φ) ≤ C holds, the optimum costs at least Φ, supporting the competitive analysis of PAWS.The analysis considers cases with and without compulsory trades.Source: §3.2 · p. 9

4 A Fundamental Limit

The section shows that the known-horizon PA-OWT competitive ratio cannot asymptotically improve on the algorithm's order. A pair of price sequences with a shared prefix forces online algorithms to trade off early purchasing against waiting for lower prices.

4 A Fundamental Limit

  • Two price sequences with a common prefix force any online algorithm to choose between buying before prices rise and waiting for prices to fall.The shared prefix makes the algorithm's decisions identical until the sequences diverge.Source: §4 · p. 10
  • The optimal competitive ratio for PA-OWT is Θ(√κ), attained by PAWS up to constant factors.The lower bound is Ω(√κ), matching the preceding algorithm's upper bound of 2√κ in order.Source: §4 · p. 10

5 Learning-Augmented Algorithms for PA-OWT

The paper studies algorithms that use predictions of optimal purchasing decisions while retaining worst-case guarantees. It establishes limits on consistency and robustness, then proposes PAWS-DA, which matches the order-optimal trade-off and can use other prediction forms converted to decision advice.

5.1 Lower Bound on Consistency-Robustness Trade-off

  • Any (1 + ε)-consistent learning-augmented algorithm must meet a lower bound on robustness that grows with κ and tightens as ε decreases.The proof uses instances sharing prices and advice initially: consistency on accurate advice requires early purchases that are costly when prices later fall.Source: §5.1 · pp. 11–12

5.2 Naive Convex Combination Algorithm

  • Mix, a convex combination of PAWS decisions and advice, is (1 + ε)-consistent but cannot match the optimal trade-off because its robustness can depend linearly on T.The section motivates a more sophisticated method to control peak-charge effects when advice is wrong.Source: §5.2 · pp. 12–13

5.3 Augmenting PAWS with Decision Advice

  • PAWS-DA targets advice using aggressive or balanced tracking, with rate limits and robust decisions to control purchases.In balanced tracking, it can ignore advice when its accrued cost is high; the parameter H bounds the cost attributable to advice.Source: §5.3 · pp. 13–14
  • PAWS-DA achieves the order-optimal consistency–robustness trade-off for learning-augmented PA-OWT.Its robustness bound is stated to match the lower bound for any learning-augmented algorithm.Source: §5.3 · pp. 15–16

5.4 Converting other forms of predictions into decision advice

  • Other prediction forms can be converted into decision advice and used by PAWS-DA without changing the algorithm, with the same guarantees when accurate converted advice attains offline optimal cost.The example predicts the optimal dual price and the number of prices no greater than that value; together, these specify which prices to accept and how much to buy.Source: §5.4 · pp. 16–17

6 Experiments

The experiments evaluate PAWS and PAWS-DA against four baselines using historical prices from four U.S. grids. Day-ahead advice performs well in the tested settings, while sensitivity experiments examine parameter changes and advice corruption.

6.1 Experimental Setup

  • The study samples 1,000 96-step instances per ISO across four U.S. grids, setting U to the 99th-percentile price and C=U/2.The price data comprises 15-minute real-time and day-ahead prices; negative real-time prices are clipped to zero.Source: §6.1 · p. 17
  • Day-ahead offline optima proxy decision advice; corruption tests blend real-time optimal decisions with worst-case advice.The baseline comparison includes BlindAdvice, Mix, OWT, and Uniform.Source: §6.1 · pp. 17–18

6.2 Experimental Results

  • ≈22% lower average empirical competitive ratio for PAWS-DA [ξ=0.5] than Mix [μ=0.5], while retaining a robustness guarantee.PAWS-DA [ξ=0.75] performs nearly identically to BlindAdvice when day-ahead advice is near-optimal.Source: Figure 1 · p. 18, §6.2 · p. 18
  • Peak-charge variation accounts for more algorithmic differences than energy cost; OWT and Uniform perform relatively worse in ERCOT.The authors attribute ERCOT’s relative performance to its more frequent price spikes.Source: §6.2 · p. 18
  • As C grows relative to U, all algorithms improve; competitive ratios rise with T, while PAWS is less affected than Uniform.Uniform is near-optimal for small T but degrades more as T increases.Source: Figure 2 · p. 19, §6.2 · p. 19
  • Under advice corruption, BlindAdvice and Mix degrade linearly, whereas PAWS-DA variants degrade sublinearly and PAWS and Uniform are unaffected.With day-ahead advice, PAWS-DA [ξ→0] has an approximately 10% lower competitive ratio than PAWS on real instances, within the same 95% confidence interval.Source: Figure 2 · p. 19, §6.2 · p. 19

7 Conclusion

The paper studies peak-aware one-way trading and develops order-optimal algorithms for competitive and learning-augmented settings. It identifies multiple obligations with shared peaks and alternative advice models as directions for future work.

7 Conclusion

  • PAWS is a dual-threshold algorithm with an order-optimal competitive ratio for known-horizon PA-OWT.The paper also characterizes limits of online purchasing and finds that knowing the horizon significantly changes what is possible.Source: §7 · pp. 19–20
  • PAWS-DA uses decision advice and provides order-optimal guarantees for the consistency-robustness trade-off.The paper establishes a lower bound on that trade-off.Source: §7 · p. 20
  • The model covers one purchasing obligation over a fixed horizon; future work could consider overlapping obligations with a shared peak and other advice models.The paper also identifies energy storage for peak shaving as a possible extension.Source: §7 · p. 20

Artificial Intelligence Use Acknowledgment

The acknowledgment describes generative AI use in algorithm and proof development, experimental code, and literature search.

Artificial Intelligence Use Acknowledgment

  • ChatGPT models generated PAWS and PAWS-DA and several matching lower bounds; the authors independently checked proofs and take responsibility for the paper.Codex generated experimental code, and AI tools assisted the literature search.Source: Artificial Intelligence Use… · p. 23

A Proofs of Preliminaries

The appendix proves preliminary bounds for PA-OWT, including a linear lower bound when the horizon is unknown and a condition under which uniform purchasing is optimal.

A Proofs of Preliminaries

  • With L=0, C≤U, and an unknown horizon, any PA-OWT algorithm has competitive ratio Ω(T).The proof uses price sequences that force a large purchase or leave the algorithm with substantial cost relative to the offline optimum.Source: A Proofs of Preliminaries · p. 23
  • For PA-OWT, when C ≥ (T−1)(U−L), uniform purchasing x_t = 1/T in every round is optimal; an online player buying 1/T each round is therefore 1-competitive in this regime.Source: A Proofs of Preliminaries · pp. 23–24
  • An optimal plan can be chosen to buy equally in the k cheapest rounds for some k, at cost (sum of their prices + C)/k.For a fixed largest purchase, buying at the lowest prices first minimizes cost; the cost varies linearly over the relevant purchase-size intervals.Source: A Proofs of Preliminaries · pp. 23–24

B Proofs of Learning-Augmented Algorithms

The proofs establish limits on what individual predictions can achieve, show that accurate cost and purchase-count predictions together recover the offline optimum, and bound PAWS-DA’s consistency and robustness.

B Proofs of Learning-Augmented Algorithms

  • PAWS-DA is (1 + ε)-consistent, with ε defined by a maximum involving Φ, L, and H.The supplied proposition gives the consistency guarantee, but its displayed formula is incomplete.Source: B Proofs of Learning-Augmented… · p. 24
  • When the direct-advice cost is at most H, PAWS-DA’s extra purchases displace at most one unit of lower-priced buying and raise the peak by at most (Φ − L)/C.Source: B Proofs of Learning-Augmented… · p. 24
  • PAWS-DA’s robustness proof handles cases with and without compulsory trades; without one, its cost is bounded by H + Φ + (Φ − L).The proof also compares this bound against an offline-cost lower bound; the supplied robustness formula is incomplete.Source: B Proofs of Learning-Augmented… · p. 25
  • Cost prediction alone cannot yield consistency below 4/3 − o(1), while purchase-count prediction alone has consistency at least 1 + 1/(4k̂ − 3).Source: B Proofs of Learning-Augmented… · pp. 25–26
  • With accurate cost and purchase-count predictions, following the advised threshold-and-count schedule attains the offline optimum.The schedule buys 1/k̂ whenever p_t ≤ λ̂; with perfect predictions it matches the optimal primal solution.Source: B Proofs of Learning-Augmented… · pp. 25, 27
Loading 2610.31447v1…