Register now After registration you will be able to apply for this opportunity online.
This opportunity is not published. No applications will be accepted.
Learning Algorithms and Equilibrium Analysis for Electricity Market Auctions
In this project, we study the electricity market auctions for which many different mechanisms have been proposed in the past. Using learning algorithms, our goal is to assess several prominent mechanisms via game-theoretic solution concepts such as correlated equilibrium and Bayes-Nash equilibrium.
Keywords: game theory, optimization, mechanism design, auction theory, combinatorial auctions, nonlinear pricing,
learning, no-regret algorithms, iterated best-response algorithms,
electricity markets, energy systems, electric power dispatch, electrical power systems
Over the last couple of decades, the electricity markets have been undergoing a rapid transformation from tightly regulated monopolies to deregulated competitive market structures. Hence, there has been a surge of research activities on studying various market mechanisms. The goal of this work is to study a subset of the existing market mechanisms, conducted as reverse auctions. In these markets, generators submit their bids, and then the independent system operator determines the power allocation and the payment for each generator. Here, the central element is the design of the payment rule, since the generators have incentives to strategize around it. In particular, the operator designs the payment rule to ensure that the generators reveal their true costs in order to achieve a stable grid with maximum social welfare.
Under the commonly-used pay-as-bid and nodal pricing rules, generators can bid strategically to influence their profits since these mechanisms do not incentivize truthful bidding. As an alternative, under the Vickrey-Clarke-Groves (VCG) payment rule, truthful bidding is the dominant-strategy Nash equilibrium. Despite this desirable property, coalitions of generators can strategically bid to increase their collective VCG utility. These manipulations occur when the VCG outcome is not in the core. The core is a concept from coalitional game theory where the participants have no incentives to leave the grand coalition, that is, the coalition of all participants. Instead, if the payments are selected from the core, coalition-proofness is ensured. Naturally, such core-selecting payment rules relax the truthfulness of the VCG mechanism.
Many of these previously mentioned payment rules are not truthful. Thus, to understand their properties, we must study them at equilibrium instead of at truth. Early analysis for core-selecting, pay-as-bid and nodal pricing rules were derived in full-information Nash equilibrium. However, bidders work hard to keep their private information secret. Hence, it is not realistic to assume that bidders have access to full information to compute their equilibrium strategy. Instead, more appropriate assumptions are that each bidder knows his own valuation, but either has an imperfect information about the other bidders’ valuations, or has a probability distribution over the set of all states of the auction. In the literature, there are well-studied learning algorithms that yield these solution concepts which are more general than the one of full-information Nash. Specifically, the goal of this project is to study no-regret learning algorithms for correlated equilibrium and iterated best-response algorithms for Bayes-Nash equilibrium. These learning algorithms can potentially provide us with a valuable tool to analyze these non-truthful rules on their way to convergence to an equilibrium.
Over the last couple of decades, the electricity markets have been undergoing a rapid transformation from tightly regulated monopolies to deregulated competitive market structures. Hence, there has been a surge of research activities on studying various market mechanisms. The goal of this work is to study a subset of the existing market mechanisms, conducted as reverse auctions. In these markets, generators submit their bids, and then the independent system operator determines the power allocation and the payment for each generator. Here, the central element is the design of the payment rule, since the generators have incentives to strategize around it. In particular, the operator designs the payment rule to ensure that the generators reveal their true costs in order to achieve a stable grid with maximum social welfare.
Under the commonly-used pay-as-bid and nodal pricing rules, generators can bid strategically to influence their profits since these mechanisms do not incentivize truthful bidding. As an alternative, under the Vickrey-Clarke-Groves (VCG) payment rule, truthful bidding is the dominant-strategy Nash equilibrium. Despite this desirable property, coalitions of generators can strategically bid to increase their collective VCG utility. These manipulations occur when the VCG outcome is not in the core. The core is a concept from coalitional game theory where the participants have no incentives to leave the grand coalition, that is, the coalition of all participants. Instead, if the payments are selected from the core, coalition-proofness is ensured. Naturally, such core-selecting payment rules relax the truthfulness of the VCG mechanism.
Many of these previously mentioned payment rules are not truthful. Thus, to understand their properties, we must study them at equilibrium instead of at truth. Early analysis for core-selecting, pay-as-bid and nodal pricing rules were derived in full-information Nash equilibrium. However, bidders work hard to keep their private information secret. Hence, it is not realistic to assume that bidders have access to full information to compute their equilibrium strategy. Instead, more appropriate assumptions are that each bidder knows his own valuation, but either has an imperfect information about the other bidders’ valuations, or has a probability distribution over the set of all states of the auction. In the literature, there are well-studied learning algorithms that yield these solution concepts which are more general than the one of full-information Nash. Specifically, the goal of this project is to study no-regret learning algorithms for correlated equilibrium and iterated best-response algorithms for Bayes-Nash equilibrium. These learning algorithms can potentially provide us with a valuable tool to analyze these non-truthful rules on their way to convergence to an equilibrium.
The specific goals of this project are as follows.
The project starts off with the DC-OPF electricity markets. Grid and generator data are provided by the IEEE test systems. Using these test systems, the initial goal is to get familiar with the existing payment rules and how they are computed.
An investigation is then performed on no-regret learning algorithms, starting from standard algorithms such as multiplicative weights update. The goal of this study is to develop an efficient algorithm to compute the correlated equilibrium of the IEEE test systems. Using this approach, we can compare the correlated equilibrium of different payment rules under several criteria. For instance, these criteria could be efficiency and total payment. We may further address risk-averse and risk-seeking behaviour to go beyond quasi-linear utilities assumption.
Then, we conduct a study on the Bayes-Nash approach. We build on existing iterated best-response algorithms and develop a variant for the Bayes-Nash equilibrium of the IEEE test systems. It is then crucial to repeat a similar equilibrium analysis for the Bayes-Nash equilibrium. Finally, the objective is to provide a discussion/comparison on Bayes-Nash and correlated equilibria.
Required Background: Courses in optimization and game theory, and a good working knowledge of MATLAB or Python are required.
Acquired skills: Student gets a solid grasp of mechanism design in auctions, and a wide range of solution concepts in game theory.
The specific goals of this project are as follows.
The project starts off with the DC-OPF electricity markets. Grid and generator data are provided by the IEEE test systems. Using these test systems, the initial goal is to get familiar with the existing payment rules and how they are computed.
An investigation is then performed on no-regret learning algorithms, starting from standard algorithms such as multiplicative weights update. The goal of this study is to develop an efficient algorithm to compute the correlated equilibrium of the IEEE test systems. Using this approach, we can compare the correlated equilibrium of different payment rules under several criteria. For instance, these criteria could be efficiency and total payment. We may further address risk-averse and risk-seeking behaviour to go beyond quasi-linear utilities assumption.
Then, we conduct a study on the Bayes-Nash approach. We build on existing iterated best-response algorithms and develop a variant for the Bayes-Nash equilibrium of the IEEE test systems. It is then crucial to repeat a similar equilibrium analysis for the Bayes-Nash equilibrium. Finally, the objective is to provide a discussion/comparison on Bayes-Nash and correlated equilibria.
Required Background: Courses in optimization and game theory, and a good working knowledge of MATLAB or Python are required.
Acquired skills: Student gets a solid grasp of mechanism design in auctions, and a wide range of solution concepts in game theory.
Please apply by writing to Orcun Karaca at okaraca@ethz.ch and including your CV and transcript of grades at Bachelor and Master's level.
Please apply by writing to Orcun Karaca at okaraca@ethz.ch and including your CV and transcript of grades at Bachelor and Master's level.