@article {654174,
	title = {The computational complexity of Nash equilibria in concisely represented games},
	journal = {ACM Transactions on Computation Theory },
	volume = {4},
	number = {2},
	year = {2012},
	abstract = {
	Version History:\&nbsp;Preliminary versions as\&nbsp;ECCC\&nbsp;TOR05-52 (https://eccc.weizmann.ac.il/report/2005/052/; attached as ECCC2005.pdf)\&nbsp;and in\&nbsp;EC {\textquoteright}06 (https://dl.acm.org/doi/10.1145/1134707.1134737; attached as EC2006.pdf).



	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{\textquoteright}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.

},
	url = {https://dl.acm.org/doi/abs/10.1145/2189778.2189779},
	author = {Grant Schoenebeck and Salil Vadhan}
}
