Question

For square matrix $P$, define

$$V(P) = \sup_x \inf_y x^T P y^T$$

where $x$ and $y$ lie on the unit $n-1$-simplex.

($P$ is a payoff matrix for a symmetric game, $x$ and $y$ are mixed strategies, and $V$ is the value of the game.)

It is known that determining $V(P)$ is NP-hard. However, is there some way to bound $V(P)$ by differentiable functions of the elements of $P$? If I am not mistaken, $V$ is monotonic in each element of $P$.

EDIT: The reason I want differentiable approximations for $V(P)$ is because I am interested in solving a system of equations

$p_1 = V(P_1), p_2 = V(P_2), ...$

where each $P_i$ depends on $p_1, p_2, ...$

Answer 1

If I haven't missed something, this is the "ordinary" two-person zero-sum game, which is a linear programming problem, and solvable in polynomial time. Game theory is full of slight variations, and you might have read about one of those being NP-hard (for instance, there is a paper by Fortnow and Impagliazzo, http://www.cs.caltech.edu/~umans/papers/FIKU05.pdf )

An excellent and concrete description of an algorithm for solving this sort of game is given in Section II 4 of Thomas S. Ferguson's electronic text on "Game Theory", http://www.math.ucla.edu/~tom/

I don't know about the worst case complexity of that particular algorithm, but it probably works fine unless you cook up specifically hard games. And in the intermediate stages, the (sub-optimal) strategies of each player will give bounds on V(P) that successively improve.