JUCS - Journal of Universal Computer Science 16(18): 2686-2710, doi: 10.3217/jucs-016-18-2686
How Incomputable is Finding Nash Equilibria?
expand article infoArno Pauly‡
‡ University of Cambridge, Cambridge, United Kingdom

Corresponding author: Arno Pauly ( arno.pauly@cl.cam.ac.uk )

© Arno Pauly.
This article is freely available under the J.UCS Open Content License.
Citation: Pauly A (2010) How Incomputable is Finding Nash Equilibria? JUCS - Journal of Universal Computer Science 16(18): 2686-2710. https://doi.org/10.3217/jucs-016-18-2686
Open Access
Abstract
We investigate the Weihrauch-degree of several solution concepts from noncooperative game theory. While the consideration of Nash equilibria forms the core of our work, also pure and correlated equilibria, as well as various concepts of iterated strategy elimination, are dealt with. As a side result, the Weihrauch-degree of solving systems of linear inequalities is settled.
Keywords
Game Theory, Computable Analysis, Nash Equilibrium, Discontinuity, Weihrauch-degree