Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

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)

Sink equilibria as a solution concept in game theory

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login