Open access
Author
Date
2018Type
- Doctoral Thesis
ETH Bibliography
yes
Altmetrics
Abstract
This thesis studies equilibrium problems in aggregative games. A game describes the interaction among selfish rational agents, each of them choosing his strategy to optimize his own cost function, which depends also on the strategies of the other agents. In particular, the thesis focuses on aggregative games, where the cost of each agent is a sole function of his strategy and of the average agents’ strategy. Not only such class of games can model a wide spectrum of applications, ranging from traffic or transmission networks to electricity or commodity markets, but it also lends itself to an elegant mathematical analysis.
The first part of the thesis investigates the relation between Nash and Wardrop equilibria, which are two classical concepts in game theory. Thanks to the powerful framework of variational inequalities, we derive bounds on the distance between the two equilibria and use them to show that the agents’ strategies at the Nash equilibrium converge to those at the Wardrop equilibrium, when the number of agents grows to infinity. Moreover, we propose novel sufficient conditions to guarantee uniqueness of the Nash equilibrium for a specific aggregative game, which is often used in applications.
The second part of the thesis is dedicated to the design of algorithms that converge to Nash equilibrium and to Wardrop equilibrium in presence of constraints coupling the agents’ strategies. Due to privacy issues and to the large number of agents at hand in real-life applications, centralized solutions might not be desirable. Hence, we first propose two parallel algorithms, where a central operator gathers and broadcasts aggregate information to coordinate the computations carried out by the agents. Then we design a distributed algorithm that only relies on local communications among the agents. We test the proposed algorithms in three case studies, where we also numerically verify the results of the first part of the thesis.
The last part of the thesis introduces the novel concept of equilibrium with inertia. Both classical Nash and Wardrop equilibria assume that each agent has the flexibility to change his strategy whenever this leads to an improvement. In some applications, however, this hypothesis is not realistic. We show that introducing an inertial coefficient which penalizes action switches leads to a richer set of equilibria, which is however in general not convex. Since classical algorithms for Nash and Wardrop equilibria cannot be used in presence of the inertial coefficients, we propose natural agents dynamics and guarantee their convergence to an equilibrium with inertial coefficients. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000289079Publication status
publishedExternal links
Search print copy at ETH Library
Publisher
ETH ZurichSubject
Game Theory; Algorithms; Aggregative Games; NetworksOrganisational unit
02650 - Institut für Automatik / Automatic Control Laboratory
More
Show all metadata
ETH Bibliography
yes
Altmetrics