This paper by Evangelos Markakis is an interesting application of Singular Value Decomposition in computational game theory.

To explain the usage, I have to establish a few definitions.  In a two player game, the players have n_1 and n_2 strategies they can choose from.  When player one chooses strategy n_1^i and player two chooses strategy n_2^j, we say the pay off for player one is R_{ij} and the pay off for player two is C_{ij}, giving us two matrices R and C (we choose R to be the name of the matrix for player one’s pay offs as her choices run down the rows of the pay off matrices, and similarly choose C as player two’s strategies vary across columns).

A player uses a pure strategy if they deterministically select one of there n strategies.  A pair of strategies x* in {1,…,n_1} and y* in {1,…,n_2} is a Nash Equilibrium if x* is the best response to y* for player one and y* is the best response to x* for player two.

A mixed strategy is probability distribution over the pure strategies.  The support of a mixed strategy x, denoted Supp(x), is the number of pure strategies assigned positive probability.  A similar definition holds for Nash Equilibrium with mixed strategies, that requires the mixed strategy x be the best possible response to y in an expected value sense over all possible distributions.

For a given matrix A, and epsilon approximation of A adds a term to entry of at most epsilon magnitude.  Similarly, an epsilon Nash Equilibrium is nearly a Nash Equilibrium, where each player’s strategy is within epsilon of the optimal strategy given the opposing strategy.

The relevant result of the paper was as follows.  This paper shows that when the payoff matrix R has rank at most k, then there exists a mixed strategy x with support of at most k+1 that is a mixed strategy Nash Equilibrium against y*.  Further, both players receive the same pay off they received in the case x*,y*.  They then go on to show that if R can be epsilon approximated by a matrix with rank at most k, then there exists a mixed strategy x with support at most k+1 that is a 2epsilon mixed strategy Nash Equilibrium against y*.  In the algorithm to compute these, they use the singular value decomposition to approximate R by the rank k matrix, and have that how large epsilon must be is a function of the singular values.  This epsilon computation makes further calculations much faster, as the zeros are easier to deal with.  This is all used in the two person game case to compute an exact equilibrium with linear programming.

If you found something unclear or would like to read more, I recommend you first read Section 4.2 of the article, Small Support epsilon-equilibria, which has some definitions (beginning on page 49, labeled 42).  Then read Section 4.2.3 is where the Singular Value Decomposition is used (beginning on page 55 labeled 48).

Computational Aspects of Game Theory and Microeconomics

Here is the wikipedia page on Nash Equilibrium for general information

http://en.wikipedia.org/wiki/Nash_equilibrium

This is a link to a new text book written (in part) by a Cornell Professor Eva Tardos on Algorithmic Game Theory.

http://theory.stanford.edu/~tim/agt/toc_brief.html