MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $x \in S^n $ where $S^n = ${$ [x_1,x_2,...,x_{n+1}]\in \mathbb{R}^{n+1} \mid x \ge 0 , \sum x_i = 1 $} and let $f_i : I^n \to \mathbb{R}$ be a finite $m$-sized family of LINEAR functions such that: $f(x_1,x_2,...,x_{n+1}) = c_0 + c_1 x_1 + c_2 x_2 + ... + c_{n+1} x_{n+1} $ where $c_j \in [0,1], c_0=0$

Assume knowledge of the $c_{i,j}$. I wish to compute:

$M=\max_x \min_i f_i(x)$

This is guaranteed to exist due to compacity on $S^n$.

The origin from this problem is from trying to compute a minimax solution for a specific kind of game. If you guys wish i can expand upon the original problem later.

share|cite|improve this question
you can write this as a linear program. do you want something else? – Sasho Nikolov Aug 12 '12 at 18:02
also, you can find approximate minimax solutions using the multiplicative weights algorithm, see e.g. Freund and Schapire – Sasho Nikolov Aug 12 '12 at 18:17

Your Answer


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

Browse other questions tagged or ask your own question.