Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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