Krill Prize Laureate 2018
Complexity and Learning of Equilibria
Equilibria are the central solution concepts in game theory. However, these solutions impose strong assumptions on the rationality of the players. Players know the utilities
of all players they are facing, players are able to compute an equilibrium, and finally after computing equilibria players are able to agree on the same equilibrium and
play accordingly. This criticism raises the following natural question:
1. Can players learn to play an equilibrium using some
natural learning rule that does not require the above
2. If so, how fast can players learn it?
3. How hard is equilibrium computation?
In my research I am trying to address these question by considering the equilibrium computation task in various computational models; E.g., communication complexity
and query complexity.