CS Seminars

In 1951 Nash showed that every game has a mixed equilibrium; whether such an equilibrium can be found efficiently has been open since that time. Two decades later Aumann proposed a relaxation called correlated equilibrium, which can be found efficiently by linear programming. These two problems become more interesting and meaningful in the case of succintly representable multiplayer games. For correlated equilibria, a novel use of the ellipsoid algorithm yields a polynomial-time algorithm in this case; for Nash equilibria a sequence of reductions (discovered in collaboration with Costas Daskalakis and Paul Goldberg) sheds light to the complexity of finding Nash equilibria.