The paper linked to is a low quality imitation of the current literature. Among its flaws it has the common fallacy that if a problem has a large number of states than inspecting all the states is always hard.
I strongly recommend instead some of the interesting actual work on Nash Equilibria and Correlated Equilibria:
"Nash equilibria: Complexity, symmetries, and approximation" Contantinos Daskalakis, Computer Science Review (2009) vol. 3 (2) pp. 87-100
"Computing Correlated Equilibria in Multi-Player Games" Christos H Papadimitriou, (2009).
Assistant Professor of Finance and Risk Engineering at the Polytechnic Institute of New York University
Ph.D. in Finance from the University of Chicago Booth School of Business
Hedge fund portfolio manager
Policy scholar for a free market think tank
Award-winning journalist
Columnist for the Fairfield County Weekly
Columnist for LewRockwell.com
Author of Yankee Wake Up and Free Your Inner Yankee
I strongly recommend instead some of the interesting actual work on Nash Equilibria and Correlated Equilibria:
"Nash equilibria: Complexity, symmetries, and approximation" Contantinos Daskalakis, Computer Science Review (2009) vol. 3 (2) pp. 87-100
"Computing Correlated Equilibria in Multi-Player Games" Christos H Papadimitriou, (2009).