Computing Nash Equilibria in Bimatrix Games: GPU-Based Parallel Support Enumeration

摘要

Computing Nash equilibria is a very important problem in strategic analysis of markets, conflicts, and resource allocation. Unfortunately, computing these equilibria even for moderately sized games is computationally expensive. To obtain lower execution times it is essential to exploit the parallel processing capabilities offered by the currently available massively parallel architectures. To address this issue, we design a GPU-based parallel support enumeration algorithm for computing Nash equilibria in bimatrix games. The algorithm is based on a new parallelization method which achieves high degrees of parallelism suitable for massively parallel GPU architectures. We perform extensive experiments to characterize the performance of the proposed algorithm. The algorithm achieves significant speedups relative to the OpenMP and MPI-based parallel implementations of the support enumeration method running on a cluster of multi-core computers.