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 sta

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).