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?