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, ...$


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.