computer science and game theory
From The New Palgrave Dictionary of Economics, Second Edition, 2008
Edited by
Steven
N.
Durlauf
and
Lawrence
E.
Blume
Back to top
Back to top
Abstract
Work at the intersection of computer science and game theory is briefly surveyed, with a focus on the work in computer science. In particular, the following topics are considered: various roles of computational complexity in game theory, including modelling bounded rationality, its role in mechanism design, and the problem of computing Nash equilibria; the price of anarchy, that is, the cost of using decentralizing solution to a problem; and interactions between distributed computing and game theory.
Keywords
algorithmic knowledge; algorithmic mechanism design; Bayesian networks; bounded rationality; Byzantine agreement; cheap talk; coalitions; combinatorial auctions; complexity theory; computational complexity; computer science and game theory; distributed computing; efficient representation of games; game theory; Gibbard–Satterthwaite th; implementing mediators; interactive epistemology;
k-resilient equilibrium; (k,t)-robust equilibrium; learning; mechanism design; Markov networks; Nash equilibrium; price of anarchy; Prisoner's Dilemma; regret; strategic voting; tit for tat; voting
Back to top
Back to top
See Also
- computation of general equilibria
- computational methods in econometrics
- computing in mechanism design
- data mining
- electronic commerce
- epistemic game theory: an overview
- epistemic game theory: beliefs and types
- mathematics of networks
- mechanism design (new developments)
- rationality, bounded
- voting paradoxes
The work for this article was supported in part by NSF under grants CTC-0208535 and ITR-0325453, by ONR under grant N00014-02-1-0455, by the DoD Multidisciplinary University Research Initiative (MURI) program administered by the ONR under grants N00014-01-1-0795 and N00014-04-1-0725, and by AFOSR under grant F49620-02-1-0101. Thanks to Larry Blume, Christos Papadimitriou, Ilya Segal, Éva Tardos, and Moshe Tennenholtz for useful comments.
How to cite this article
Halpern, Joseph Y. "computer science and game theory." The New Palgrave Dictionary of Economics. Second Edition. Eds. Steven N. Durlauf and Lawrence E. Blume. Palgrave Macmillan, 2008. The New Palgrave Dictionary of Economics Online. Palgrave Macmillan. 05 November 2017 <http://www.dictionaryofeconomics.com/article?id=pde2008_C000566> doi:10.1057/9780230226203.0287