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.
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/F16/