It is shown here that the problem of computing a Nash equilibrium for two-person games can be polynomially reduced to an indefinite quadratic programming problem involving the spectrum of the adjacency matrix of a strongly connected directed graph on
is the total number of players’ strategies. Based on that, a new method is presented for computing approximate equilibria and it is shown that its complexity is a function of the average spectral energy of the underlying graph. The implications of the strong connectedness properties on the energy and on the complexity of the method is discussed and certain classes of graphs are described for which the method is a polynomial time approximation scheme (PTAS). The worst case complexity is bounded by a subexponential function in the total number of strategies
and a comparison is made with a previously reported method with subexponential complexity.