In the random utility theory, a person will choose an alternative with maximum perceived utility $\max\{U_i\}$.$$U_i=V_i+\xi_i\ \forall i=1...N$$ where $U_i$ is the perceived utility of alternative $i$, $V_i$ is the actual utility of alternative $i$, $\xi_i$ is the perceived error. Because of $\xi_i$ is a random variable, we cannot get which $U$ is the maximum, we can only get the probability of each $U_i$ to be the maximum. Now consider the expectation of maximum perceived utility $\mathbb{E}[\max\{U_i\}]$, which can be calculated by:
$$ E(V_1,\cdots,V_N)=\mathbb{E}\left[ \underset{\forall i}{\max}\left\{ U_i \right\} \right] =\int{\int{\cdots \int{\underset{\forall i}{\max}\left\{ V_i+\xi _i \right\} f\left( \xi _1,\cdots \xi _1 \right)}}}d\xi _1d\xi _2\cdots d\xi _N $$ where $f\left( \xi _1,\cdots \xi _1 \right)$ is the joint density function of $\xi _1, \cdots \xi _N$, and I want prove $E$ is monotonic with respect to the size of the choice set, i.e. $E(V_1,\cdots, V_N, V_N+1) \ge E(V_1,\cdots, V_N)$.
It is usually assumed mean of $\xi _i$ is zero, $\xi$ is independent among different alternatives. However, even $\xi$ is dependent among different alternatives, the conclusion which I want to prove should still be true. Say, when $\xi _1, \cdots \xi _N$ is Multivariate Normal distributed.
Note that if you have two random variables $X$ and $Y$ then $E\{\max\{X, Y\}\} \ge \max\{E(X), E(Y)\}$ (can you show why?).
It follows that $$ \begin{align} E\left(\max_{i=1}^{n+1} \{U_i\}\right) &= E\left(\max\left\{\max_{i=1}^{n} \{U_i\}, U_{n+1}\right\}\right) \\ &\ge \max \left\{E\left(\max_{i=1}^{n} \{U_i\}\right), E(U_{n+1}) \right\}\\ &\ge E\left(\max_{i=1}^{n} \{U_i\}\right) \end{align} $$