DIMACS Theory of Computing Seminar

Title: Approximating Nash Equilibrium Via Multilinear Minimax

Speaker: Bahman Kalantari, Rutgers University

Date: Wednesday, September 21, 2016 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

On the one hand we state {\it Nash equilibrium} (NE) as a formal theorem on multilinear forms and give a pedagogically simple proof, free of game theory terminology. On the other hand, inspired by this formalism, we prove a {\it multilinear minimax theorem}, a generalization of von Neumann's bilinear minimax theorem. Next, we relate the two theorems by proving that the solution of a multilinear minimax problem, computable via linear programming, serves as an approximation to Nash equilibrium point, where its multilinear value provides an upper bound on a convex combination of {\it expected payoffs}. Furthermore, each positive probability vector once assigned to the set of players induces a {\it diagonally-scaled} multilinear minimax optimization with a corresponding approximation to NE. In summary, in this note we exhibit an infinity of multilinear minimax optimization problems each of which provides a polynomial-time computable approximation to Nash equilibrium point, known to be difficult to compute. The theoretical and practical qualities of these approximations are the subject of further investigations.