Convex Geometry, Extremal Measures, and Correlated Equilibria in Polynomial Games

Abstract:

This bulk of this talk will be about the geometry of convex sets of probability distributions, in particular those specified by finitely many parameters. The only real prerequisites will be basic probability and finite-dimensional linear algebra. The motivation from game theory, which will be given little attention in the talk itself, is as follows.

Nash equilibria are perhaps the most well-known solution concept for games. Correlated equilibria are a convex relaxation of these which corresponds to dropping the independence constraint on players (random) strategy choices. In finite games the relaxation is actually a linear program, so we generally think of correlated equilibria as being computationally and geometrically simpler than Nash equilibria.

In polynomial games (those with intervals for strategy sets and polynomials for utilities), both types of equilibria involve probability distributions over infinite sets and so are a priori infinite-dimensional objects. It is easy to show (and has been known since the 1950's) that for Nash equilibria the full description of the probability distribution chosen by a player is not relevant for strategic considerations: only finitely many moments of this distribution matter, up to the degree of the utilities. This gives a finite-dimensional description of the set of Nash equilibria. A choice of distribution for each player is a Nash equilibrium if and only the corresponding moments satisfy certain conditions.

For computational purposes a similar finite-dimensional description of the set of correlated equilibria would be useful. The obvious candidate is to express the correlated equilibrium conditions in terms of all the joint moments corresponding to monomials which are present in the utilities. This does not work out as expected.

We will show, via an explicit example, that the set of correlated equilibria of a polynomial game does not admit a finite-dimensional description in terms of (generalized) moments. To do so we note that any extreme point of a convex set of probability distributions which is described by moments has finite support (bounded in terms of the number of moments used). We exhibit extreme correlated equilibria of arbitrarily large finite and even infinite support with a little help from ergodic theory.

Biography:

Noah is in his sixth and final year as a LIDS student where he has been working with advisors Asu Ozdaglar and Pablo Parrilo since day one. His research is focused on game theory, usually with a view towards computation, along with any mathematical topics he can manage to connect to it. He is also interested in optimization, particularly algebraic methods such as linear and semidefinite programming. Noah's master's thesis won the EECS department's Ernst A. Guillemin Thesis Award, 1st place. Outside of school he enjoys German-style games, chocolate, and the outdoors.