The problem of computing a two-player Nash equilibrium is PPAD-complete

Applications of Mathematics, Mathematics of Computation 1 Minute

You need to know: Vectors, matrices, transpose x^T of vector x, matrix multiplication, algorithms and their running times, polynomial algorithm, polynomial-time reduction, complexity classes P and PPAD (Polynomial Parity Arguments on Directed graphs), PPAD-complete problem.

Background: Let {\mathbb P}^n be the set of vectors x=(x_1,\dots,x_n)\in{\mathbb R}^n such that all x_i \geq 0 and \sum\limits_{i=1}^n x_i = 1. The problem of computing a two-player Nash equilibrium is: given two m\times n matrices A and B with rational entries, compute vectors x^* \in {\mathbb P}^m and y^* \in {\mathbb P}^n such that (x^*)^TAy^* \geq x^TAy^* and (x^*)^TBy^* \geq (x^*)^TBy for all x\in {\mathbb P}^m and y\in {\mathbb P}^n.

The Theorem: On 12th April 2007, Xi Chen, Xiaotie Deng, and Shang-Hua Teng submitted to arxiv a paper in which they proved that the problem of computing a two-player Nash equilibrium is PPAD-complete.

Short context: The problem of computing a two-player Nash equilibrium is a fundamental problem in game theory with applications to, for example, economics. Famous theorem of Nash from 1950 implies that Nash equilibrium exists for any matrices A and B. However, it was an open question if there is a polynomial-time algorithm for computing it. The Theorem implies that such algorithm does not exist, unless a well-believed conjecture P\neqPPAD fails.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Unknown's avatar

Published by Bogdan Grechuk

Published

Leave a comment