The Computational Complexity of Nash Equilibria in Concisely Represented Games

DSpace/Manakin Repository

The Computational Complexity of Nash Equilibria in Concisely Represented Games

Citable link to this page

 

 
Title: The Computational Complexity of Nash Equilibria in Concisely Represented Games
Author: Schoenebeck, Grant R.; Vadhan, Salil P.

Note: Order does not necessarily reflect citation order of authors.

Citation: Schoenebeck, Grant R., and Salil Vadhan. 2012. The Computational Complexity of Nash Equilibria in Concisely Represented Games. ACM Transactions on Computation Theory 4, no. 2: 1–50.
Full Text & Related Files:
Abstract: Games may be represented in many different ways, and different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. The traditional method of representing a game is to explicitly list all the payoffs, but this incurs an exponential blowup as the number of agents grows. We study two models of concisely represented games: circuit games, where the payoffs are computed by a given boolean circuit, and graph games, where each agent’s payoff is a function of only the strategies played by its neighbors in a given graph. For these two models, we study the complexity of four questions: determining if a given strategy is a Nash equilibrium, finding a Nash equilibrium, determining if there exists a pure Nash equilibrium, and determining if there exists a Nash equilibrium in which the payoffs to a player meet some given guarantees. In many cases, we obtain tight results, showing that the problems are complete for various complexity classes.
Published Version: doi:10.1145/2189778.2189779
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:12763606
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters