Computing all solutions of Nash equilibrium problems with discrete strategy sets

The Nash equilibrium problem is a widely used tool for modeling noncooperative games. Many solution methods have been proposed in the literature to compute solutions of Nash equilibrium problems with continuous strategy sets, but, aside from some specific methods for some particular applications, there are no general algorithms to compute solutions of Nash equilibrium problems in which the strategy set of each player is assumed to be discrete. We define a branching method to compute the whole solution set of Nash equilibrium problems with discrete strategy sets. This method is equipped with a procedure that, by fixing variables, effectively prunes the branches of the search tree. Furthermore, we propose a preliminary procedure that by shrinking the feasible set improves the performance of the branching method when tackling a particular class of problems. Moreover, we prove existence of equilibria and we propose an extremely fast Jacobi-Type method which leads to one equilibrium for a new class of Nash equilibrium problems with discrete strategy sets. Our numerical results show that all the proposed algorithms work very well in practice. © 2016 Society for Industrial and Applied Mathematics.