Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information
Date and Time: Tuesday, November 14, 2023, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Christos Papadimitriou (Columbia University and Google)
Over the past three quarters of a century, the Nash equilibrium has been the central solution concept in game theory -- the meaning and destiny of the game. Ever since computer scientists took an interest in the subject, computational disadvantages of the Nash equilibrium came into light. Still, the Nash equilibrium prevailed, importantly based on the popular belief that "the players will eventually end up there." We have recently shown that this is not so: There are games for which there is no dynamics converging to the Nash equilibria. In view of this negative result, I will propose a new solution concept motivated by dynamics, and based on what computer scientists have called in the past the sink equilibria of a game: the sink strongly connected components of the better-response graph of the game. I will show that this new solution concept is grounded on game dynamics in a very strong and principled way, and that it comes with efficient algorithms for computing both the various equilibria and the probabilities that standard dynamics will converge to them.
Automatic MiSe System Software Version 1.4803M | admin login