3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you wish to do this inside of a mathematical programming tool, or can you use arbitrary algorithms and libraries? $\endgroup$ – Richard Jul 26 at 14:24
  • $\begingroup$ 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 $\endgroup$ – Abdullah Ali Sivas Jul 26 at 17:20
  • $\begingroup$ @Richard, I'm happy to use arbitrary algorithms. Abdullah Ali Sivas, yes, that's exactly the problem. Thank you for the feedback. $\endgroup$ – D.W. Jul 26 at 17:51
  • $\begingroup$ 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? $\endgroup$ – Richard Jul 26 at 19:56
0
$\begingroup$

You can and should solve this problem without linear programming and apply the Bellman equation instead.

Actually, the minmax theorem -- handled numerically via LP -- is only required to solve the problem where both players simultaneously choose an action.

In contrast, your game consists of a two-step process, and the mathematical model should incorporate this structure. This can be realized by a Markov decision process that is optimized via the Bellman equation. Basically, you there solve two "max" problems instead of one "minmax" problem, which is way easier from both the mathematical and the computational perspective.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This sounds very interesting -- would you mind elaborating on this a little bit? Can you show me what the Bellman equation would be in this context? I've never heard that term before, but Wikipedia seems to indicate it is the recursive formula used in dynamic programming. I'm familiar with dynamic programming but I'm not sure how we'd obtain a suitable recursive formula in this setting, or how we'd set up the problem so that dynamic programming can be applied. Would you mind expanding on your answer? $\endgroup$ – D.W. Jul 28 at 0:54

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.