Loading...
Please wait, while we are loading the content...
Similar Documents
Games on Graphs The Complexity of Pure Nash Equilibria
| Content Provider | Semantic Scholar |
|---|---|
| Author | Thomas, Antonis |
| Copyright Year | 2011 |
| Abstract | In this thesis, we analyze the problem of computing pure Nash equilibria in succinctly representable games, with a focus on graphical and action-graph games. While the problem is NP-Complete for both models, it is known to be polynomial time computable when restricted to games of bounded treewidth. We propose a dynamic programming approach for computing pure Nash equilibria of graphical games. Our algorithm attacks the combinatorics of the problem directly, in contrast to previous algorithms that use mappings to other problems. The analysis yields substantial improvements over the known bounds on the time complexity of the problem. From the viewpoint of parameterized complexity, we prove that computing pure Nash equilibria for graphical games is W [1]-Hard when parameterized by treewidth. On the other hand, our algorithm becomes Fixed-Parameter-Tractable for games with bounded cardinality strategy sets. Moreover, we discuss the implication of our algorithm for solving games with O(log n) bounded treewidth. Finally, it is possible to construct a sample, and the maximum payoff, pure Nash equilibrium without additional computational effort. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.uu.nl/research/techreps/repo/CS-2011/2011-024.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
