  Nash equilibrium} (NE) can be stated as a formal theorem on a multilinear
form, free of game theory terminology. On the other hand, inspired by this
formalism, we state and prove a {\it multilinear minimax theorem}, a
generalization of von Neumann's bilinear minimax theorem. As in the bilinear
case, the proof is based on relating the underlying optimizations to a
primal-dual pair of linear programming problems, albeit more complicated LPs.
The theorem together with its proof is of independent interest. Next, we use
the theorem to associate to a multilinear form in NE a {\it multilinear minimax
relaxation} (MMR), where the primal-dual pair of solutions induce an
approximate equilibrium point that provides a nontrivial upper bound on a
convex combination of {\it expected payoffs} in any NE solution. In fact we
show any positive probability vector associated to the players induces a
corresponding {\it diagonally-scaled} MMR approximate equilibrium with its
associated upper bound. By virtue of the proof of the multilinear minimax
theorem, MMR solution can be computed in polynomial-time. On the other hand, it
is known that even in bimatrix games NE is {\it PPAD-complete}, a complexity
class in NP not known to be in P. The quality of MMR solution and the
efficiency of solving the underlying LPs are the subject of further
investigation. However, as shown in a separate article, for a large set of test
problems in bimatrix games, not only the MMR payoffs for both players are
better than any NE payoffs, so is the computing time of MMR in contrast with
that of Lemke-Howsen algorithm. In large size problems the latter algorithm
even fails to produce a Nash equilibrium. In summary, solving MMR provides a
worthy approximation even if Nash equilibrium is shown to be computable in
polynomial-time.
