Approximately Stable Pricing for Coordinated Purchasing of Electricity

Andrew Perrault, Craig Boutilier

Introduction

The transition to a "smart grid" promises significant efficiency gains through consumer coordination. By shifting loads—such as running appliances during off-peak hours—consumers can flatten demand and negotiate better rates through purchasing groups. However, the complex physics and economics of power generation make it difficult to find pricing schemes that are both fair and stable. Standard pricing models often fail because electricity production involves non-linear, time-dependent costs, such as ramp rates and minimum generation thresholds. This paper proposes two novel algorithms that prioritize system stability and fairness, sacrificing a negligible amount of total efficiency to ensure group cohesion.

Problem Formulation: The Matching Market

The authors model the electricity market as a matching problem where consumers possess multiple potential "demand profiles" reflecting their flexibility. Producers, on the other hand, face physical constraints including:

  1. Ramp Rates: Costs associated with changing output levels.
  2. Base vs. Tracking Layers: The distinction between slow-changing, inexpensive "base" plants (e.g., nuclear) and flexible but costly "tracking" plants (e.g., natural gas).
  3. Minimum Generation: Inefficiencies or damage risks when operating below specific thresholds.
Matching market model between producers and consumers with flexible demand profiles.

Due to these complexities, a mathematically "optimal" assignment of consumers to producers is often unstable. Individuals may find incentives to defect from the group if they perceive a better deal elsewhere or experience "envy" toward peers with similar usage profiles paying lower rates.

Proposed Methods

To address these challenges, the study introduces two distinct cost-sharing mechanisms:

  • Shapley-Like Payments: Derived from cooperative game theory, this method assigns costs based on an agent's average marginal contribution. While theoretically fair, it is computationally intensive (#P-complete), requiring sampling for approximation.
  • Similarity-Based Envy-Free (SBEF) Payments: A more scalable approach that clusters consumers using Ward clustering and decision trees based on demand features (e.g., peak usage, variance). By enforcing uniform unit prices within clusters, the method ensures envy-free outcomes.

To enhance stability, the optimization process incorporates "exclusions" and "cuts," searching for near-optimal solutions that significantly reduce the incentive for members to leave the group.

Experimental Results and Stability Gains

The methods were evaluated using a simulated US residential energy market based on 2011 building data and real-world weather conditions from San Antonio, Texas. The experiments demonstrated a critical "stability-welfare tradeoff": by accepting solutions at approximately 98.5% of theoretical maximum welfare, the system can drastically improve stability.

Reduction in the maximum incentive to defect (MItD) over successive iterations of the optimization algorithm.

Key findings include:

  • Stability: The use of "cuts" in optimization reduced the Maximum Incentive to Defect (MItD) by over 50% compared to the initial optimal solution.
  • Scalability: The SBEF method successfully found stable matchings for 2,500 consumers in approximately 30 minutes, outperforming Shapley-based methods which struggle with groups as small as 50.
  • Welfare Preservation: Near-stable solutions consistently maintained over 98% of maximum social welfare.

Conclusion and Future Directions

This research highlights that absolute mathematical efficiency is often secondary to practical stability in smart grid coordination. By abstracting demand features for fairness and utilizing iterative optimization cuts, purchasing groups can remain cohesive. Future work will need to address potential strategic manipulation by consumers, the evolution of groups over dynamic time windows, and the challenges of eliciting complex demand preferences from human users.

Summary updated

Abstract

Matching markets are often used in exchange settings (e.g., supply chain) to increase economic efficiency while respecting certain global constraints on outcomes. We investigate their application to pricing and cost sharing in group purchasing of electricity in smart grid settings. The task is complicated by the complexities of producer cost functions due to constraints on generation from different sources (they are sufficiently complex that welfare-optimal matchings are not usually in equilibrium). We develop two novel cost sharing schemes: one based on Shapley values that is "fair," but computationally intensive; and one that captures many of the essential properties of Shapley pricing, but scales to large numbers of consumers. Empirical results show these schemes achieve a high degree of stability in practice and can be made more stable by sacrificing small amounts (< 2%) of social welfare.
BibTeX
@inproceedings{perrault2015approximately,
  author = {Andrew Perrault and Craig Boutilier},
  title = {{Approximately Stable Pricing for Coordinated Purchasing of Electricity}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure