Open access
Author
Date
2024Type
- Master Thesis
ETH Bibliography
yes
Altmetrics
Abstract
Recently, new class of dynamic resource allocation mechanisms, called karma mechanisms, have shown great promise in acheiving fair and efficient outcomes. The analysis of karma mechanisms relies on the availability of versatile computational tools to predict the Nash equilibrium of a "karma game". Existing algorithms used to compute Nash equilibria of a karma game are centralized in nature, severely limiting the size and complexity of problems they can address. In this thesis, we formulate the karma game as a Multi Agent Reinforcement Learning (MARL) problem and adopt MARL techniques to compute Nash equilibria in arbitrarilty complex karma games. In our study of MARL for large populations, we found that a mature understanding of how to empirically assess convergence to a Nash equilibrium is lacking. For this reason, we first develop empirical convergence measures in a previously studied problem instance with known Nash equilibrium, before tackling a complex problem involving a grid of roads in a city center. Motivated by the observed empirical convergence, we moreover survey the state of the art on theoretical convergence guarantees in large population MARL, highlighting the shortcomings of existing methods and the current gap between theory and practice. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000670521Publication status
publishedContributors
Examiner: Dörfler, Florian
Examiner: He, Niao
Examiner: Elokda, Ezzat
Examiner: Yardim, Batuhan
Publisher
ETH ZurichSubject
Karma games; Karma mechanisms; Reinforcement learning (RL); MULTI-AGENT SYSTEMS (ARTIFICIAL INTELLIGENCE); Mean field games; Mechanism DesignOrganisational unit
09478 - Dörfler, Florian / Dörfler, Florian09729 - He, Niao / He, Niao
Related publications and datasets
More
Show all metadata
ETH Bibliography
yes
Altmetrics