Chess is EXPTIME-Complete, which makes it significantly harder than NP-Complete problems.
Perhaps you are interested in the study of economic networks. Strategic network formation sounds like a good starting point. A lot of the work examines when certain classes of graphs arise under pure strategy Nash equilibria. There are exponentially many pure strategies. Enumerating the vertices of the polytope is likely not feasible.
Edit: Some of the big names in the area include Matthew O. Jackson, Rachel Kranton, Sanjeev Goyal, and Hans Haller. I would start with their papers. In particular, Matthew O. Jackson has a book on the subject.
Here are links to their homepages/CVs so you can scout out their publications. Economic networks are a pretty hot area at the moment, so you can likely look at journals like Econometrica to see what is being published.
http://web.stanford.edu/~jacksonm/papersarticles.html
http://econ.duke.edu/people/kranton/networks
http://www.econ.vt.edu/cvsandresearch/hallercv.pdf