Suppose $X$ is real-valued random variable and $\phi$ an increasing function. An upper set is either an open or a closed right half line. Below, all expectations are assumed to exist and $I$ denotes the indicator function.
Shaked and Shanthikumar (2007) claims the following: it is possible, for each $m$, to define a sequence of upper sets $U_i$'s, a sequence of $a_i$'s, and a $b$ (all of which may depend on $m$), such that as $m\to\infty$, $$ E\left[\sum_{i=1}^m a_i I_{U_i}(X)\right]-b\to E[\phi(X)] $$
I vaguely guess that the Monotone Convergence Theorem is somehow involved but I can't conjure up a construction that does the job. Can you please help me?
We use a argument similar to the construction of Riemann Stieljes integral via lower sum. Call the function on the left hand side $\psi$ $$ \psi_n(x)=\sum^{m(n)}_{i=1}a_iI_{U_i}(x)-b. $$ It is important to realize that $\psi_n$ is a step function. For concreteness, let $U_i=[c_i,\infty)$. Relabel the index set so that $c_1<c_2<\ldots<c_m$. Then $\psi_n$ has the following representation ($m$ may depend on $n$) $$ \psi_n(x)=\sum^m_{i=0}d_iI_{A_i}(x) $$ where $$ d_0=-b,\quad d_i=\sum^i_{j=1}(a_i-b),\quad A_0=(-\infty,c_1), \quad,A_i=[c_{i},c_{i+1}),\quad A_m=[c_m,\infty). $$ Now we can apply the standard simple function approximation to the increasing function $\phi$. Note that for increasing function, Riemann type step function approximation suffices, but we do need to take care of the unbounded support of the Lebesgue-Stieltjes integral/expectation. As example, consider the following construction $$ m(n)=2^{3n+1},\quad c_i=-2^n+\frac{i}{2^{2n}},\quad d_0=\sup\phi^{-1}(\lbrace -2^n\rbrace),\quad d_i=\inf_{x\in A_i}\phi(x). $$ What we are doing is uniformly partitioning the compact interval $[-2^n,2^n]$ and approximate $\phi$ using its infimum on each interval. A little thought should convince you that $\psi_n\uparrow\phi$ pointwise. Note that as $n\rightarrow \infty$, two things must be happening:
the compact inverval $[-2^n,2^n]$ needs to expand to cover all of $\mathbb{R}$ eventually.
the partition on any fixed compact interval $[-M,M]$ must be finer and finer.
Invoke the probability version of Monotone Convergence Theorem to establish $$ E[\psi_n(x)]\uparrow E[\phi]. $$ We have to make sure that the sequence $\lbrace \psi_n\rbrace$ is uniformly bounded below. This is ensured by assuming $$ \lim_{x\rightarrow-\infty}\phi(x)>-\infty. $$ $(a_i,b_i,U_i)$ can be solved back from $(c_i,d_i)$ by our construction and the proof is complete.