This obviously depends on the "closeness" measure of the lower bound. FWIW, for any $n$ (let $n = 2k$ even for simplicity) and the following input values: - $\alpha_1 = \alpha_k = 0$, $\alpha_{k + 1} = \alpha_{2k} = 1$, - $v_1 = v_2 = \ldots = v_{2k} = 1$, - $p(1) = \ldots = p(2k) = \frac{1}{k + 1}$, $\mathbb{E}(X)$ can be both: - $\frac{1}{k + 1}$, when $S_1, \ldots, S_{k + 1}$ are equiprobable, and $S_1, \ldots, S_k$ are singleton sets $\{1\}, \ldots, \{k\}$, $S_{k + 1} = \{k + 1, \ldots, 2k\}$, - $1 - \frac{1}{k + 1}$, for a symmetrical construction. Thus, $\mathbb{E}(X)$ can't be approximated from below within factor $O(n)$, or $1 - \Omega(1 / n)$ absolute error.