Search

Equilibria computation is of great importance to many areas such as economics, control theory, and recently computer science. We focus on the computation of Nash equilibria in two-player general-sum normal form games, also called bimatrix games. One efficient method to compute these equilibria is based on enumerating the vertices of the best response polyhedrons of the two players and checking the equilibrium conditions for every pair of vertices. We design and implement a parallel algorithm for computing Nash equilibria in bimatrix games based on vertex enumeration. We analyze the performance of the proposed algorithm by performing extensive experiments on a grid computing system.

We propose a parallel algorithm for finding Nash equilibria in n-player noncooperative games. The algorithm is based on enumerating the supports of mixed strategies in parallel and solving for each support the corresponding multilinear equations giving the candidate equilibria.We implemented the proposed algorithm using MPI on a cluster of computers.We performed extensive experiments on random games to show the performance of theparallel algorithm.

We consider the problem of computing all Nash equilibria in bimatrix games (i.e., nonzero-sum two-player noncooperative games). Computing all Nash equilibria for large bimatrix games using single-processor computers is not feasible due to the exponential time required by the existing algorithms. We consider the use of parallel computing which allows us to solve larger games. We design and implement a parallel algorithm for computing all Nash Equilibria in bimatrix games. The algorithm computes all Nash equilibria by searching all possible supports of mixed strategies. We perform experiments on a cluster computing system to evaluate the performance of the parallel algorithm.