Multilinear Approximate Carathéodory Theorem for Sparse Game Optimization

Many optimization and learning problems involve several probability distributions whose joint effect is captured by a vector-valued multilinear map. We prove a multilinear approximate Carathéodory theorem that replaces each marginal distribution by a small uniform one while approximately preserving the map, with a support bound independent of the ambient dimension. We apply this result to $n$-player games parameterized by their interaction density $\Delta$: after removing intrinsic and strategically irrelevant payoff terms, at most $\Delta$ actions have nonzero remaining payoff for each fixed profile of the opponents. We show that every such game admits a $k$-uniform $\varepsilon$-Nash equilibrium with $k\in O((\log\Delta+\log n)/\varepsilon^2)$, improving the best-known general bound and giving a PTAS when $n$ and $\Delta$ are constant. The logarithmic dependence on $\Delta$ is necessary, and $k\in\Omega(\sqrt{\log n})$ may be required, resolving an open problem of Babichenko, Barman, and Peretz (2014). Finally, the same compression method yields a PTAS for polymatrix games with a fixed number of players and bounded column sparsity in $A^{i,j}+(A^{j,i})^\top$, extending Barman's (2018) two-player result.