The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points
share
Introduced by the celebrated works of Debreu and Rosen in the 1950s and 60s, concave n-person games have found many important applications in Economics and Game Theory. We characterize the computational complexity of finding an equilibrium in such games. We show that a general formulation of this problem belongs to PPAD, and that finding an equilibrium is PPAD-hard even for a rather restricted games of this kind: strongly-convex utilities that can be expressed as multivariate polynomials of a constant degree with axis aligned box constraints. Along the way we provide a general computational formulation of Kakutani's Fixed Point Theorem, previously formulated in a special case that is too restrictive to be useful in reductions, and prove it PPAD-complete.
READ FULL TEXT