Support Vector-based Estimation of Multilinear Games for Feature Selection and Explanation

In many games, players' decisions consist of multiple subdecisions, and hence can give rise to an exponential number of pure strategies. However, this set of pure strategies is often structured, allowing it to be represented compactly, as in network congestion games, security games, and extensive form games. Reduction to the standard normal form generally introduces exponential blow-up in the strategy space and therefore are ine cient for computation purposes. Although individual classes of such games have been studied, there currently exists no general purpose algorithms for computing solutions such as Nash equilibrium (NE) and (coarse) correlated equilibrium. To address this, we define multilinear games generalizing all. Informally, a game is multilinear if its utility functions are linear in each player's strategy, while fixing other players' strategies. Thus, if pure strategies, even if they are exponentially many, are vectors in polynomial dimension, then we show that mixed-strategies have an equivalent representation in terms of marginals forming a polytope in polynomial dimension. The canonical representation for multilinear games can still be exponential in the number of players, a typical obstacle in multi-player games. Therefore, it is necessary to assume additional structure that allows computation of certain sub-problems in polynomial time. Towards this, we identify two key subproblems: computation of utility gradients, and optimizing linear functions over strategy polytope. Given a multilinear game, with polynomial time subroutines for these two tasks, we show the following: (a) We can construct a polynomially-computable and polynomiallycontinuous fixed-point formulation, and show that its approximate fixedpoints are approximate NE. This gives containment of approximate NE computation in PPAD, and settles its complexity to PPAD-complete. (b) Even though a coarse correlated equilibrium can potentially have exponential representation (being a probability distribution of pure strategy profiles), through LP duality and a carefully designed separation oracle, we provide a polynomial-time algorithm to compute one with polynomial representation. (c) Finally, we show existence of an approximate NE with support-size logarithmic in the strategy polytope dimensions.