# A bound on the number of bilinear functions needed in order to obtain the minmax

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$?

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$.