Non-approximability of Bimatrix Nash Equilibria

Keywords and Synonyms

Approximate Nash equilibrium            

Problem Definition

In this entry, the following two problems are considered: 1) the problem of finding an approximate Nash equilibrium in a positively normalized bimatrix (or two-player) game; and 2) the smoothed complexity of finding an exact Nash equilibrium in a bimatrix game. It turns out that these two problems are strongly correlated [3].

Let ${ \cal G=({\mathbf{A}},{\mathbf{B}}) }$ be a bimatrix game, where ${ {\mathbf{A}}=(a_{i,j}) }$ and ${ {\mathbf{B}}=(b_{i,j}) }$ are both ${ n\times n }$ matrices. Game ${ \cal G }$ is said to be positively normalized, if ${ 0\le a_{i,j},b_{i,j}\le 1 }$ for all ${ 1\le i,j\le n }$.

Let ${ \mathbb{P}^n }$ denote the set of all probability vectors in ${ \mathbb{R}^n }$, i. e., non-negative vectors whose entries sum to 1. A Nash equilibrium [8] of ${ \cal G=({\mathbf{A}},{\mathbf{B}}) }$ is a pair of mixed strategies \( { ({\mathbf{x}}^*\in...