What is a robust way to find the max of $n$ independent, non-identical random variates? Suppose I observe $n$ random variates along with their variance (but not mean) and I'd like to select the one with the largest mean as frequently as possible. The procedure must be memoryless--you cannot keep track of how often you selected each as the max nor can you keep track of any other statistics. What is the best way to do this?
For example, suppose I draw from $n=5$ Normal distributions.  Each has $\mu_i=0$ and $\sigma^2=\tfrac{1}{1+i}$.  In this case I would like to have a scoring rule such that every variate has an equal chance of being chosen as the max--in short, I want to account for the risk present in some of the variates.  If we were to always just select the max, then the lowest variance variable, ie, $i=5$ would be selected the least frequently.  If $n=2$ we wouldn't have to worry about this problem.
More generally it should have the property that variables with a higher mean get selected more often. There is obviously going to be some tradeoff between mean and variance, but I don't know what that should be.
It seems like the answer to this problem has to do with the relative variances  as well as the number of observations per ranking.
One simple idea (which ignores $n$) is just use $x_i - \sigma_i^2$ as a score for ranking.  Is there something better? How would I prove optimality? I've tried playing around with LINEX and Bayesian Decision Theory. I feel the answer lies in the asymmetric loss present in over-prediction (since $n>2$ implies there are more ways to get it wrong then right).
I've also played around with the idea of using (in the above example) a Normal-Normal posterior. This has the effect of lowering the variance (making it more fair) at the expense of adding some bias (making it less fair). Is there something better out there? Is this a reasonable approach?  What if I used LINEX loss under this posterior to derive an optimal rule?
Note that this question is not just: what is the pdf of non-identically distributed random variates (or some variation). It is more about how to minimize the risk of choosing an outlier when we are looking for the "max" (which is clearly not robust). I feel this problem must come up in ranking whenever the score is calculated from a model trained with a univariate loss function (such as ranking using logistic regression).
 A: The best score of the form $x_i + f(\sigma_i)$ is where $f$ is constant — in other words, you can not do better than just picking the largest observation.
The requirement that “variables with a higher mean get selected more often” implies,
by continuity, that variables with the same mean get selected equally often.
So suppose we have a score based on $f$, and suppose we have $n$ independent variables, each with standard deviation $\sigma_i$, but all symmetrically distributed with the same mean $\mu$.
(The assumption of symmetry allows us to conclude that $P[X_i>X_j]$, $P[\mu-X_i>X_j]$, $P[\mu-X_i>\mu-X_j]$ and $P[X_j>X_i]$ are all equal. If the logs of the variables are distributed symmetrically, that would work too; we do not need a full assumption of normality.)
Choose an $i$ for which $f(\sigma_i)$ is highest. Then
\begin{align}
\frac1n
&= P[\text{variable }X_i\text{ is chosen as highest}]\\
&= P[X_i + f(\sigma_i) > X_j + f(\sigma_j) \ \forall i\neq j] \\
&\ge P[X_i > X_j \ \forall i\neq j] \\
&= \frac1n
\end{align}
So in fact all these probabilities are equal, which means $f(\sigma_i)=f(\sigma_j)$ for all $i \neq j$. Since this must be true regardless of the standard deviations in the mix of variables, $f$ must be constant, and the score has the same properties as if $f$ is zero.
