Τίτλος: Nash Equilibria and Complexity
Ομιλητής: Κωνσταντίνος Δασκαλάκης, Massachusetts Institute of Technology (ΜΙΤ)
Ημερομηνία/Ώρα: Παρασκευή 19 Αυγούστου 2011, 1:15μμ
Αίθουσα: Αμφιθέατρο Κτιρίου Επιστημών, Πολυτεχνειούπολη
The existence of Nash Equilibrium is established via Brouwer's Fixed point theorem, raising questions about its computational tractability. In the first part of the talk, we survey results on the complexity of the Nash equilibrium, showing that it is generally intractable. In view of these results, the credibility of the Nash equilibrium is questioned: do markets and players converge to equilibria, if finding them is an intractable problem?
In the second part of the talk, we discuss ways to go around the computational barrier, such as looking at approximation or special classes of games. We develop probabilistic tools to algorithmically exploit the symmetry that underlies certain game-theoretic applications, such as traffic networks and social interactions.
Constantinos (or Costis) Daskalakis is an Assistant Professor of EECS at MIT. Prior to MIT, he was an undergraduate student at the National Technical University of Athens, a PhD student at UC Berkeley, and a postdoctoral researcher at Microsoft Research New England. His research interests lie in Algorithmic Game Theory and Applied Probability, in particular computational aspects of markets and the Internet, social networks, and computational problems in Biology. Costis has been honored with a 2007 Microsoft Graduate Research Fellowship, the 2008 Game Theory and Computer Science Prize from the Game Theory Society, the 2008 ACM Doctoral Dissertation Award, a NSF Career Award, a 2010 Sloan Foundation Fellowship in Computer Science, the 2011 SIAM Outstanding Paper Prize, and the MIT Ruth and Joel Spira Award for Distinguished Teaching.