Show simple item record

dc.contributor.authorSchoenebeck, Grant R.
dc.contributor.authorVadhan, Salil P.
dc.date.accessioned2014-09-02T13:20:48Z
dc.date.issued2012
dc.identifier.citationSchoenebeck, 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.en_US
dc.identifier.issn1942-3454en_US
dc.identifier.issn1942-3462en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:12763606
dc.description.abstractGames 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.en_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherAssociation for Computing Machinery (ACM)en_US
dc.relation.isversionofdoi:10.1145/2189778.2189779en_US
dash.licenseLAA
dc.titleThe Computational Complexity of Nash Equilibria in Concisely Represented Gamesen_US
dc.typeJournal Articleen_US
dc.description.versionAccepted Manuscripten_US
dc.relation.journalACM Transactions on Computation Theoryen_US
dash.depositing.authorVadhan, Salil P.
dash.waiver2012-07-16
dc.date.available2014-09-02T13:20:48Z
dc.identifier.doi10.1145/2189778.2189779*
workflow.legacycommentsFrom Waiver Tableen_US
dash.contributor.affiliatedVadhan, Salil


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record