Algebraic approach to Nash equilibria for finite normal form games

Abstract

In this work we consider methods for computing Nash equilibria of finite normal form games that emphasize use of polynomial algebra. Nash equilibria of a game can be characterized as solutions to a system of polynomial equations that we call the game system (GS). We adopt this characterization of Nash equilibria and apply polynomial algebra as a computational framework. Our work is concerned with finding all Nash equilibria given a single equilibrium (a sample equilibrium), without repeating the solution procedure for the sample equilibrium.

In the present work we consider two subclasses of finite normal form games. The class of rational payoff irrational equilibria(RPIE) games consists of the games where all the game payooff values are rational numbers while all equilibria are irrational number tuples. The class of integer payooff irrational equilibria (IPIE) games is defined similarly. The main emphasis in our work is algorithmic. We develop in detail two major algorithms required for each of the classes under consideration: a membership algorithm and an equilibria computation algorithm. We develop in detail the underlying computational techniques from polynomial algebra, and present proofs of their correctness. We compare these techniques with other algorithms and discuss their computational complexity. We also discuss approaches for constructing examples of these classes of games.

Our overall philosophy is to exploit the following: Galois groups of univariate polynomials in the ideal I of GS and a single sample solution of the GS. We use group action by Galois groups on a sample solution to extend our knowledge about the remaining solutions of the GS, which include all the Nash equilibria. The primary setting of our work remains Galois theory over the field of rational numbers. As we progress to IPIE games, we use the more generalized Galois theory over commutative rings. Accordingly, several subsidiary results of an essentially algebraic nature are derived in the course of our development. We also briefly consider the possibility of games over finite fields.

For the problem of computing all the Nash equilibria of the classes of games, we present two separate but similar algorithms for RPIE and IPIE games. The algorithms work in two phases: computation of a sample solution of the GS, followed by computation of Nash equilibria using the Galois group action. For RPIE games, in the first phase, computation of a sample solution is carried out by identifying a Grobner basis for the ideal I of the GS, while the same computation for another algorithm for IPIE games is performed with multivariate Newton Raphson method(MVNRM). The next phase { that of computing all other solutions { involves application of the Galois group over a sample solution. However, not all of these solutions correspond to Nash equilibria. Hence we resort to the Nash equilibrium verification algorithm to reject superfluous solutions and retain only the solutions corresponding to Nash equilibria.

We derive an important condition on the polynomial ideal I of GS to reduce repeated factorizations and substitutions, further reducing computational complexity of the presented algorithms. Further a condition is derived for computing equilibria of subclasses of games in closed form.

We present algorithms that use knowledge of a sample solution to compute other equilibria of the games. The presented methods do not require repeated factorizations and provide exact solutions. The work enables us to use algebraic properties and structure available in the GS of a game. It highlights some important interrelations of the equilibria of a game. The research reported in this work opens up interesting connections between algebraic geometry and game theory, thereby expanding the horizon of the problem of computing equilibria in game theory.