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

Safraz Rampersaud, Lena Mashayekhy, Daniel Grosu
Department of Computer Science, Wayne State University, Detroit, MI 48202, USA
31st IEEE International Performance Computing and Communications Conference (IPCCC’12), 2012


   title={Computing Nash Equilibria in Bimatrix Games: GPU-based Parallel Support Enumeration},

   author={Rampersaud, S. and Mashayekhy, L. and Grosu, D.},



Download Download (PDF)   View View   Source Source   



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 faster execution times it is essential to exploit the available parallelism 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-based parallel implementation of the support enumeration method running on conventional multicore machines.
Rating: 2.3/5. From 2 votes.
Please wait...

* * *

* * *

HGPU group © 2010-2023 hgpu.org

All rights belong to the respective authors

Contact us: