How hard is it to compute Nash equilibrium?

Tegoroczna nagroda Nevanlinny, za osiągnięcia w matematycznych aspektach nauk informatycznych, przyznana została Constantinosowi Daskalakisowi za jego wkład w badanie złożoności obliczeniowej podstawowych problemów w dziedzinie rynków, aukcji, równowag, oraz innych zagadnień ekonomicznych. Na kolokwium przedstawię jeden z najsławniejszych wyników Daskalakisa, dotyczący złożoności obliczania równowagi Nasha.

This years Nevanlinna prize, a prize in mathematical aspects of information sciences, was awarded to Constantinos Daskalakis for his contributions to understanding of the computational complexity of fundamental problems in markets, auctions, equilibria, and other economic structures. During the seminar I will present one of the most famous results of Daskalakis, concerning the complexity of computing Nash equilibrium.