HIIT Special Seminar: Juho Hirvonen "Understanding Equilibria of Games as Distributed Computation"
Understanding Equilibria of Games as Distributed Computation
Thursday 19 May 11:00-12:00
via Zoom: request the link by email: [email protected]
Note! The link will be sent by email to Aalto CS, Helsinki CS, Aalto ComNet, and Aalto SPA staff
In this talk I will introduce my research programme where I am using our understanding of the complexity theory of distributed computing to analyse the computational hardness of equilibria in game theory. This is based on the fundamental observation that in graphical games (games on networks such that a graph denotes which players depend on each other) most equilibrium concepts are locally checkable: strategies are in equilibrium if and only if each player is in equilibrium with respect to its neighbours. The hardness of solving such locally checkable problems has been intensely studied in distributed computing, and their complexity theory is relatively well understood.
Since game theory is used to model systems that are distributed, in particular impossibility results from distributed computing will have implications on the possible behaviour of such systems. I will discuss how this connection can be used to understand strategic behaviour. For example, we can show that many natural games do not have Nash equilibria that can be found efficiently. When games do have efficiently computable equilibria, we can study which equilibria are efficiently computable. This is based on our work with Laura Schmid, Krishnendu Chatterjee, and Stefan Schmid (2021).
Juho Hirvonen is currently a postdoctoral researcher at Aalto University, having recently finished an Academy of Finland Postdoctoral period. He defended his thesis in 2016 under the supervision of Professor Jukka Suomela. His thesis received the Aalto Computer Science department’s thesis award. Afterwards, he spent one year as a postdoctoral researcher at the IRIF Research Institute in Paris and a year as postdoctoral researcher at the University of Freiburg under Professor Fabian Kuhn. In 2018 he received a three-year Academy of Finland postdoctoral grant.
His research focus is on the theoretical foundations of distributed computing and connections between distributed computing, game theory, and mechanism design.
Helsinki Institute for Information Technology HIIT
Collaborative institute for research on information technology.