Given two n x m matrices A and B, consider the game where simultaneously player I picks a row i and player II picks a column j. Player I's payoff is A(i,j) and player II's payoff is B(i,j).
Nash proved that for all A and B there are probability distributions σ on the rows and τ on the columns so that if the player I plays according to σ and player II plays according to τ
- There is no i such that if player I chooses row i his expected payoff will increase with player II still playing according to τ.
- There is no j such that if player II chooses column j her expected payoff will increase with player I still playing according to σ.
Using linear programming we can find Nash Equilibrium in a zero-sum game (A(i,j)=-B(i,j) for all i,j) or if we know the set of i where σ(i)=0 and the j where τ(j)=0.
We can also find a correlated equilibrium in polynomial-time which is a distribution on pairs (i,j). However to implement a correlated equilibrium you need either a third trusted party or use some cryptographic techniques.
I don't know a good survey on the complexity of Nash Equilibrium but perhaps my readers will have some good references.