2
$\begingroup$

For $n\in\mathbb N$, let $\Delta(n)=\{x\in\mathbb R^n:x_i\geq 0, \sum_ix_i=1\}$ be the set of probability vectors in $\mathbb R^n$.

Is there a function $m:\mathbb N\to\mathbb N$ such that for any finite list $A_1,A_2,\ldots,A_k$ of $n\times n$ (real valued) matrices, there exists a subset $J\subset[k]$ with cardinality $m(n)$ such that

$$\min_{x,y\in\Delta(n)}\max_{i\in[k]} xA_i y \ = \min_{x,y\in\Delta(n)}\max_{i\in J} xA_i y\quad ? $$

Moreover, can $m(n)$ be polynomial in $n$?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

The answer is "no". Solution proposed by Omri Solan.

For $n=2$, let $m=m (2) $. Take matrices $A_0,\ldots,A_k $ such that $$(x,1-x)A_i (y,1-y)=-(x-\tfrac i k)(y-\tfrac i k). $$ By setting $i $ as close as possible to $\frac {x+y}{2}k $, it follows that the min-max over all $i\in\{0,\ldots,k \}$ is at least $-(\frac {1}{2k})^2$. Whereas, a subset $J\subset\{0\leq i_1<\cdots <i_m\leq k \} $ defines partition the unit interval into $m+1$ intervals of the form $[\frac {i_j}{k},\frac {i_{j+1}}{k}] $; setting $x=y $ at the center of the largest interval shows that the min-max over $J $ is at most $ -(\frac {1}{2(m+1)})^2$.

$\endgroup$

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.