Approximating the maximin value of a zero-sum game - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T06:51:06Z http://mathoverflow.net/feeds/question/63073 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63073/approximating-the-maximin-value-of-a-zero-sum-game Approximating the maximin value of a zero-sum game charles.y.zheng 2011-04-26T20:40:38Z 2011-05-12T10:22:13Z <p>For square matrix \$P\$, define</p> <p>\$\$V(P) = \sup_x \inf_y x^T P y^T\$\$</p> <p>where \$x\$ and \$y\$ lie on the unit \$n-1\$-simplex.</p> <p>(\$P\$ is a payoff matrix for a symmetric game, \$x\$ and \$y\$ are mixed strategies, and \$V\$ is the value of the game.)</p> <p>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\$.</p> <p>EDIT: The reason I want differentiable approximations for \$V(P)\$ is because I am interested in solving a system of equations</p> <p>\$p_1 = V(P_1), p_2 = V(P_2), ...\$</p> <p>where each \$P_i\$ depends on \$p_1, p_2, ...\$</p> http://mathoverflow.net/questions/63073/approximating-the-maximin-value-of-a-zero-sum-game/63267#63267 Answer by Johan Wästlund for Approximating the maximin value of a zero-sum game Johan Wästlund 2011-04-28T07:48:55Z 2011-04-28T07:48:55Z <p>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, <a href="http://www.cs.caltech.edu/~umans/papers/FIKU05.pdf" rel="nofollow">http://www.cs.caltech.edu/~umans/papers/FIKU05.pdf</a> )</p> <p>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", <a href="http://www.math.ucla.edu/~tom/" rel="nofollow">http://www.math.ucla.edu/~tom/</a> </p> <p>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.</p>