# Solve two-player game - minimize the l-infinity norm of a matrix-vector product

I have a matrix $$M$$ with non-negative real entries, and I would like to minimize the objective function $$\Phi(v) = \|Mv\|_\infty,$$ where $$v$$ is constrained to be a probability vector, i.e., $$v_1+\dots+v_n=1$$ and $$v_i\ge 0$$. Is there an efficient algorithm for this?

Motivation. This comes up in solving a two-player game, where the first player chooses $$v$$ (which represents a probability distribution on the columns of $$M$$), then the second player sees $$v$$ and chooses a row $$i$$, and the first player loses $$(Mv)_i$$ and the second player gains $$(Mv)_i$$. I want to find an efficient algorithm to find the optimal strategy for the first player.

Best I can do. I can see how to solve this with linear programming. We introduce a variable $$\ell$$ to represent the final loss of the first player, then we add the linear inequalities $$M_i v \le \ell$$ (and the constraints on $$v$$) and we minimize $$\ell$$. Is there a more efficient algorithm than this?

• Do you wish to do this inside of a mathematical programming tool, or can you use arbitrary algorithms and libraries? – Richard Jul 26 at 14:24
• Looks like you are trying to solve $\min_v\max_i M_iv$ and that is a tough problem to solve, especially when $M$ is nonsingular. I don't know if you can do any better than linear programming – Abdullah Ali Sivas Jul 26 at 17:20
• @Richard, I'm happy to use arbitrary algorithms. Abdullah Ali Sivas, yes, that's exactly the problem. Thank you for the feedback. – D.W. Jul 26 at 17:51
• Keep in mind that linear programming solves many problems quickly in practice. What kind of input sizes are you looking at? Do you know LP is too slow? – Richard Jul 26 at 19:56