Beschreibung:
Introduction
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.
Project Description and Main Steps
The specific tasks are as follows.
The project starts off with the DC-OPF electricity markets described in [1]. 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 [2].
An investigation is then performed on no-regret learning algorithms, starting from standard algorithms such as multiplicative weights update [3]. 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 [4]. We build on existing iterated best-response algorithms, discussed in [4] and [5], 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 equilibrium concepts.
There is a potential to propose an alternative payment rule from this study. If time permits, the analysis can be extended to the Swiss Reserve Markets. Depending on the scope, we may also address alternative solution concepts such as the ones attained by no-envy learning.
At the end of the project, the work will be presented at the Automatic Control Laboratory in a 25min seminar.
Required Background
Courses in optimization and game theory, and a good working knowledge of MATLAB or Python are required. Familiarity with YALMIP or CVXPY is an advantage.
Acquired Skills
Student gets a solid grasp of mechanism design in combinatorial auctions, and a wide range of solution concepts in game theory.
Procedure
Please apply by writing to Orcun Karaca okaraca@control.ee.ethz.ch and including your CV and transcript of grades at Bachelor and Master's level.
Main References
An extensive list will be provided to the student.
[1] DC-OPF markets: Wu, Felix, et al. "Folk theorems on transmission access: Proofs and counterexamples." Journal of Regulatory Economics 10.1 (1996): 5-23.
[2] Pricing rules: Karaca, Orcun, et al. "Designing coalition-proof reverse auctions over continuous goods." arXiv preprint (2017).
[3] Correlated Equilibrium: Roughgarden, Tim. Twenty lectures on algorithmic game theory. Cambridge University Press, 2016.
[4] Bayes-Nash Equilibrium: Rabinovich, Zinovi, et al. "Computing pure Bayesian-Nash equilibria in games with finite actions and continuous types." Artificial Intelligence 195 (2013): 106-139.
[5] Bayes-Nash Equilibrium: Bosshard, Vitor, et al. "Computing Bayes-Nash equilibria in combinatorial auctions with continuous value and action spaces." Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI). Melbourne, Australia. 2017
Weitere Informationen
|
Professor:
Maryam Kamgarpour
|
