0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ you can write this as a linear program. do you want something else? $\endgroup$
    – Sasho Nikolov
    Commented Aug 12, 2012 at 18:02
  • $\begingroup$ also, you can find approximate minimax solutions using the multiplicative weights algorithm, see e.g. Freund and Schapire $\endgroup$
    – Sasho Nikolov
    Commented Aug 12, 2012 at 18:17

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .