CS Seminar: SOS-based Computational Methods for Polynomial Games. Part II

Dr. Pablo A. Parrilo,  EE & CS, Massachusetts Institute of Technology

In the last few years, techniques based on sum of squares (SOS) decompositions of multivariate polynomials, semidefinite programming (SDP), and results from real algebraic geometry have proved extremely useful in the formulation of hierarchies of convex relaxations for difficult polynomial optimization problems. In this talk we show how these can be extended to a game theoretic setting. In particular, we discuss a class of zero-sum two-person games with an infinite number of pure strategies, where the payoff function is a polynomial expression of the actions of the players.  We show that the value of the game,  and the corresponding optimal strategies, can be computed by solving a single semidefinite program, thus providing a natural generalization of the well-known LP characterization of finite games. We also discuss the possible extensions to correlated equilibria, and to the nonzero sum case. In addition, we show how the results can be applied, with suitable modifications, to a general class of semialgebraic games and problems with two quantifiers.

Wednesday's lecture will be more introductory in nature, and discuss the basic setup of separable games and SOS/SDP methods. On Friday, we will put these basic elements together and discuss some further extensions.

BIOGRAPHY:
Pablo A. Parrilo received an Electronics Engineering undergraduate degree from the University of Buenos Aires, and a Ph.D. in Control and Dynamical Systems from the California Institute of Technology in 1995 and 2000, respectively. He has held short-term visiting appointments at the University of California at Santa Barbara (Physics), Lund Institute of Technology (Automatic Control), and UC Berkeley (Mathematics). From October 2001 through September 2004, he was Assistant Professor of Analysis and Control Systems at the Automatic Control Laboratory of the Swiss Federal Institute of Technology (ETH Zurich). He is currently an Associate Professor at the Department of Electrical Engineering and Computer Science of the Massachusetts Institute of Technology, where he is affiliated with the Laboratory for Information and Decision Systems(LIDS) and the Operations Research Center (ORC).  Prof. Parrilo is the recipient of the 2005 Donald P. Eckman Award of the American Automatic Control Council, as well as the triennial SIAM Activity Group on Control and Systems Theory (SIAG/CST) Prize. He was also a finalist for the Tucker Prize of the Mathematical Programming Society for the years 2000-2003.

His research interests include optimization methods for engineering applications, control and identification of uncertain complex systems, robustness analysis and synthesis, and the development and application of computational tools based on convex optimization and algorithmic algebra to practically relevant engineering problems.

LUNCH WILL BE SERVED.