Register now After registration you will be able to apply for this opportunity online.
This opportunity is not published. No applications will be accepted.
Fast Computation of Dynamic Population Games with Madupite
Dynamic Population Games (DPGs) are an important class of games that models many real-world problems, including energy systems, epidemics, and the recently proposed “karma economies” for fair resource allocation. A DPG consists of a large population of self-interested agents each solving an individual Markov Decision Process (MDP). The MDP of each agent is coupled to the actions of others and is hence parametrized by the policies adopted in the population. Computing the Nash equilibrium of a DPG is challenging as it involves iteratively solving MDPs many times. This suffers from the well-known curse of dimensionality which severely limits the size of the state and action spaces that are computationally tractable.
Madupite is a novel distributed high-performance solver for large-scale infinite horizon discounted MDPs, which leverages PETSc to implement inexact policy iteration methods in a distributed fashion. Despite its software complexity, Madupite comes with a very intuitive Python interface and a detailed documentation, that allow any Python user to easily deploy it to efficiently simulate and solve large-scale MDPs in a fully distributed fashion. Preliminary benchmarks have showcased the great potential of Madupite, which is capable of efficiently handling MDPs with millions of states.
Motivated by the recent development of Madupite, this project aims at developing fast computation tools that are capable of solving large-scale DPGs.
Keywords: Programming (Python/C++), Markov Decision Processess, Game Theory, Karma Economy
The project will investigate the potential of using Madupite to speed up the computation of Nash equilibria in DPGs. This requires developing a mature understanding of the theory of DPGs, as well as the solution techniques of Madupite, in order to identify how to best combine these tools. The main goal is to develop a publicly accessible code base that solves DPGs with Madupite acting as the inner MDP solver. This code base will be used to assess the speed-up with respect to existing benchmarks, as well as compute Nash equilibria in problem instances that were infeasible before. As a case study, we will compute equilibria in complex, multi-domain karma economies.
The project will investigate the potential of using Madupite to speed up the computation of Nash equilibria in DPGs. This requires developing a mature understanding of the theory of DPGs, as well as the solution techniques of Madupite, in order to identify how to best combine these tools. The main goal is to develop a publicly accessible code base that solves DPGs with Madupite acting as the inner MDP solver. This code base will be used to assess the speed-up with respect to existing benchmarks, as well as compute Nash equilibria in problem instances that were infeasible before. As a case study, we will compute equilibria in complex, multi-domain karma economies.
- Review the literature on DPGs and Madupite to have a mature understanding of these tools;
- Develop a publicly accessible code base to solve DPGs with Madupite following best programming practices;
- Test the developed solver on existing benchmarks and previously intractable instances.
- Review the literature on DPGs and Madupite to have a mature understanding of these tools; - Develop a publicly accessible code base to solve DPGs with Madupite following best programming practices; - Test the developed solver on existing benchmarks and previously intractable instances.
Please apply directly to the posting on SiROP. We look forward to your application.
Matilde Gargiani (gmatilde@ethz.ch), Ezzat Elokda (elokdae@ethz.ch)
Please apply directly to the posting on SiROP. We look forward to your application. Matilde Gargiani (gmatilde@ethz.ch), Ezzat Elokda (elokdae@ethz.ch)
IFA-fast-DPG-computation-madupite.pdf
