Allocating Variance to Maximize Expectation

We design efficient approximation algorithms for maximizing the expectation of the supremum of families of Gaussian random variables. In particular, let $OPT:=\max_{\sigma_1,\cdots,\sigma_n}\mathbb{E}\sum_{j=1}^{m}\max_{i\in S_j} X_i$, where $X_i$ are Gaussian, $S_j\subset[n]$ and $\sum_i\sigma_i^2=1$, then our theoretical results include: - We characterize the optimal variance allocation -- it concentrates on a small subset of variables as $|S_j|$ increases, - A polynomial time approximation scheme (PTAS) for computing OPT when $m=1$, and - An $O(\log n)$ approximation algorithm for computing OPT for general $m>1$.

Suppose you are managing a set of uncertain choices, such as different investment portfolios or genetic factors in personalized medicine, and you want to distribute a limited budget of "variability" (or variance) among them to maximize the expected value of the 90th percentile outcome. This paper mathematically solves this challenge, proving that as the number of choices grows, the optimal strategy is to concentrate the variability on a select few rather than spreading it evenly. To implement this strategy, we designed algorithms that can automatically determine this ideal distribution, even when the choices are arranged in complex, overlapping groups. These new mathematical tools have practical applications for real-world planning, such as helping sellers maximize their returns in auction markets or helping medical researchers optimize outcomes in complex therapies.