Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-153 | 21st September 2015 16:58

Computing Equilibria: A Computational Complexity Perspective

RSS-Feed




TR15-153
Authors: Tim Roughgarden
Publication: 22nd September 2015 09:15
Downloads: 858
Keywords: 


Abstract:

Computational complexity is the subfield of computer science that rigorously studies the intrinsic difficulty of computational problems. This survey explains how complexity theory defines “hard problems”; applies these concepts to several equilibrium computation problems; and discusses implications for computation, games, and behavior. We assume minimal prior background in computer science.

This document is a preprint of a 2010 article in Economic Theory.



ISSN 1433-8092 | Imprint