Optimal auctions for networked markets with externalities

Benjamin Heymann, Alejandro JofréarXiv 2019 · OpenReview

Abstract

Motivated by the problem of market power in electricity markets, we introduced in previous works a mechanism for simplified markets of two agents with linear cost. In standard procurement auctions, the market power resulting from the quadratic transmission losses allows the producers to bid above their true values, which are their production cost. The mechanism proposed in the previous paper optimally reduces the producers' margin to the society's benefit. In this paper, we extend those results to a more general market made of a finite number of agents with piecewise linear cost functions, which makes the problem more difficult, but simultaneously more realistic. We show that the methodology works for a large class of externalities. We also provide an algorithm to solve the principal allocation problem. Our contribution provides a benchmark to assess the sub-optimality of the mechanisms used in practice.

Introduction

In modern electricity markets, the physical constraints of the power grid—specifically transmission losses—create a unique economic challenge: market power. Because transporting energy over long distances results in energy loss (often modeled via the quadratic Joule effect), a producer located near a high-demand node possesses a geographic advantage. This allows them to bid significantly above their actual production costs, knowing that the Independent System Operator (ISO) may still select them to avoid the higher transmission losses associated with a cheaper, more distant competitor.

While standard auction theory works well for non-networked goods, it often fails to minimize procurement costs for the public when these spatial externalities are present. This paper extends Myerson’s classic optimal auction theory to networked environments, providing a mechanism designed to curb strategic bidding and minimize total social cost.

Mechanism Design and Virtual Costs

The core of the proposed approach lies in the application of the Revelation Principle. To mitigate the impact of strategic over-bidding, the authors employ the concept of "virtual costs." Following the logic established by Myerson (1981), the ISO does not evaluate bids at their face value. Instead, it replaces a producer's bid with a virtual cost function that accounts for the probability distribution of the producer's private costs.

By penalizing bids based on these distributions, the mechanism reduces the profit margins of strategic agents. A key contribution of this work is the introduction of a "discernability" condition. This condition ensures that virtual marginal prices remain increasing, serving as the piecewise linear equivalent of the "monotone likelihood ratio property" found in classic economic models. This ensures that the resulting allocation remains consistent and economically sound.

Generalizing to Piecewise Linear Costs

Previous research in this area often relied on simplified linear cost assumptions. However, real-world power plants operate across different "working zones" (e.g., varying fuel types or turbine efficiencies), making their cost structures piecewise linear and convex.

This paper successfully generalizes the optimal auction framework to handle these complex cost functions. This transition makes the underlying optimization problem significantly more difficult but ensures the model is applicable to realistic infrastructure. Furthermore, the authors demonstrate that their characterization of the optimal mechanism holds for a broad class of network constraints beyond quadratic losses, suggesting applicability to other transported goods and networked externalities.

The Fixed-Point Allocation Algorithm

To implement this mechanism, the ISO must solve a complex allocation problem to determine which producers should generate power and in what quantities. The authors derive a dual problem and prove that its solution is the unique fixed point of a monotone operator.

Based on this proof, they propose an iterative fixed-point algorithm. This algorithm is particularly notable for its potential in decentralized applications; it mimics a scenario where agents at different nodes exchange marginal cost information with their neighbors to reach a global optimum.

Performance and Evaluation

The algorithm was tested using synthetic networks generated via the Barabasi-Albert model, creating 100-node graphs that mimic the scale-free properties of real-world infrastructure. The performance was benchmarked against CVX, a standard professional-grade convex optimization package.

  • Computational Efficiency: For linear cost instances, the fixed-point algorithm was approximately 10 times faster than the centralized solver (2.03s vs 30.23s).
  • Reliability: The algorithm consistently converged to the same optimal cost as the CVX solver for both linear and piecewise linear scenarios, proving its robustness for large-scale network problems.

Discussion and Limitations

While the mechanism provides a powerful benchmark for assessing the sub-optimality of current market practices, several areas remain for future exploration. The current model utilizes the "DC approximation" for power flows, which simplifies the physics by ignoring reactive power and voltage constraints. Additionally, the model assumes deterministic demand, though the authors suggest the logic can be extended to stochastic environments.

Finally, the implementation of virtual costs requires the ISO to have knowledge of the probability distributions of producer costs. In practice, this would require the ISO to "learn" these distributions over time through repeated auction cycles. Despite these challenges, the proposed mechanism offers a significant step forward in designing efficient, fair, and computationally viable networked markets.

Summary updated

Abstract

Motivated by the problem of market power in electricity markets, we introduced in previous works a mechanism for simplified markets of two agents with linear cost. In standard procurement auctions, the market power resulting from the quadratic transmission losses allows the producers to bid above their true values, which are their production cost. The mechanism proposed in the previous paper optimally reduces the producers' margin to the society's benefit. In this paper, we extend those results to a more general market made of a finite number of agents with piecewise linear cost functions, which makes the problem more difficult, but simultaneously more realistic. We show that the methodology works for a large class of externalities. We also provide an algorithm to solve the principal allocation problem. Our contribution provides a benchmark to assess the sub-optimality of the mechanisms used in practice.
BibTeX
@misc{heymann2019optimal,
  author = {Benjamin Heymann and Alejandro Jofré},
  title = {{Optimal auctions for networked markets with externalities}},
  year = {2019},
  eprint = {1907.10080},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.10080},
}
Figure