Register now After registration you will be able to apply for this opportunity online.
This opportunity is not published. No applications will be accepted.
Second order methods for Generalized Nash equilibrium problems
In this project we aim to exploit second-order method to derive efficient and provably-convergent algorithms for the computation of generalized nash equilibria in multi-agent decision problems.
Keywords: Game theory, Distributed Optimization, Second-order methods
Multi-agent decision making has attracted considerable
attention over the past decade as
paradigm to model problems involving heterogeneous
agents, that potentially share common
resources. In this context, equilibrium solutions
based on generalized Nash equilibrium
problems (GNEPs) find broad applicability
in social science and engineering, encompassing
problems in power grid, traffic management,
sensing, and networks.
From a control-theoretic perspective, the
objective is to develop a coordination mechanism
for updating the strategies of the agents towards a generalized Nash equilibrium. The task,
however, is difficult since the objective function and the constraints of each agent are interdependent.
Under some regularity assumptions, the problem is typically cast as a variational inequality and
solved via projected gradient methods. In this project, inspired by recent results from the machine
learning community, we aim at deriving provably-convergent second-order algorithms to solve
GNEPs, where we wish to take advantage of curvature information to speed up the convergence.
Depending on the student interest, different directions are possible. On one side, we can focus
on the design of hessian-free second order methods design algorithm that approximate secondorder
curvature information via the history of past gradient realizations, thus avoiding the need of
Hessian vector product computations. On the other side, we can employ homotopy methods to
design algorithms that first solve a simplified problem and then deform this problem into the original
complicated one.
Multi-agent decision making has attracted considerable attention over the past decade as paradigm to model problems involving heterogeneous agents, that potentially share common resources. In this context, equilibrium solutions based on generalized Nash equilibrium problems (GNEPs) find broad applicability in social science and engineering, encompassing problems in power grid, traffic management, sensing, and networks. From a control-theoretic perspective, the objective is to develop a coordination mechanism for updating the strategies of the agents towards a generalized Nash equilibrium. The task, however, is difficult since the objective function and the constraints of each agent are interdependent. Under some regularity assumptions, the problem is typically cast as a variational inequality and solved via projected gradient methods. In this project, inspired by recent results from the machine learning community, we aim at deriving provably-convergent second-order algorithms to solve GNEPs, where we wish to take advantage of curvature information to speed up the convergence. Depending on the student interest, different directions are possible. On one side, we can focus on the design of hessian-free second order methods design algorithm that approximate secondorder curvature information via the history of past gradient realizations, thus avoiding the need of Hessian vector product computations. On the other side, we can employ homotopy methods to design algorithms that first solve a simplified problem and then deform this problem into the original complicated one.
The goals of the project are as follows:
1. Learn about Game Theory, Distributed Optimization and Second-order methods;
2. Develop a second-order algorithm to compute generalized Nash equilibria and provide convergence
certificates;
3. Validate the designed algorithm via numerical simulations on a benchmark problem of choice
and compare it with first-order methods to show off the computational benefits of the new
formulation.
The goals of the project are as follows:
1. Learn about Game Theory, Distributed Optimization and Second-order methods;
2. Develop a second-order algorithm to compute generalized Nash equilibria and provide convergence certificates;
3. Validate the designed algorithm via numerical simulations on a benchmark problem of choice and compare it with first-order methods to show off the computational benefits of the new formulation.
If you are an highly-motivated student with interest in game theory and optimizaiton, please send your resume/CV (including lists of relevant publications/projects) and transcript of
records in PDF format via email to mfochesato@ethz.ch, ccenedese@ethz.ch and gbelgioioso@ethz.ch.
If you are an highly-motivated student with interest in game theory and optimizaiton, please send your resume/CV (including lists of relevant publications/projects) and transcript of records in PDF format via email to mfochesato@ethz.ch, ccenedese@ethz.ch and gbelgioioso@ethz.ch.