I am looking for references or solutions to the following subset maximization problem. Consider there are $n$ firms which a decision maker can apply to. Denote $N=\{1,\dots,n\}$. Each application costs her $c_i$ dollars. The decision maker knows a priori that the firm $i$ offers a wage $R_i$ with probability $p_i$. The decision maker only allows to accept one offer. I want to know which firms the decision maker should apply to so that she obtains maximum expected payoff.
More specifically, Let $A_i=1$ if the decision maker chooses to accept firm $ i$'s offer and $A_i=0$ otherwise. Let $I_i=1$ if the decision maker chooses to apply to firm $i$ and $I_i=0$ otherwise. The decision maker tries to solve the following problem
$$\max_{S\subseteq N}\, V(S) = \max_{S\subseteq N}\,\mathop{\mathbb{E}}\left[\sum_{i\in S}\left(R_iA_i-I_ic_i\right)\right].$$
I am looking for an algorithm that could solve this problem. I tried to solved this problem by considering how to enlarge the candidate set. In particular, assume that $R_i> R_j$ for $i>j$. Let $S_k = \{n,n-1,\dots,k\}$ for all $k\in N$. I have showed that if $V(S_k) > V(S_{k-1})$, then $V(S_k \cup \{j\}) >V(S_{k-1}\cup \{j\})$ for all $j< k-1$. That is, if the firm $k-1$ is excluded, then it cannot be re-added afterward. However, this method could not determine which element should be eliminated after we cannot add any more element in this descending order. Could anyone give me some hints about how to solve this problem or point me to some references? Thanks!
Not an answer, but too long for a comment. What's inside your $\mathbb{E}$ is not random, and $I_i=1 \iff i \in S$. Instead let $X_i$ be a $\text{Bernoulli}(p_i)$ random variable. The decision maker's problem is then:
$$\max_{S\subseteq N}\mathop{\mathbb{E}}\left[\left(\max_{i\in S} R_i X_i\right) -\sum_{i\in S} c_i\right] =\max_{S\subseteq N}\left\{ -\sum_{i\in S} c_i + \mathop{\mathbb{E}}\left[\max_{i\in S} R_i X_i\right]\right\}$$
That is, the decision maker selects $S$, incurring an immediate cost of $\sum_{i\in S} c_i$, and waits for Nature to decide the random reward $\max_{i \in S} R_i X_i$.
Without loss of generality (relabeling the firms if necessary), assume $R_i \le R_{i+1}$ for all $i$, so that the decision maker will accept the offer from the largest $i$ that offers. Let $R = \max_{i\in S} R_i X_i$. We have $R = R_i$ if $X_i=1$ and $X_j=0$ for all $j \in S$ such that $j > i$, and this event happens with probability $p_i \prod_{j \in S: j > i} (1-p_j)$. So $$\mathop{\mathbb{E}}\left[R\right] = \sum_{i\in S} \left[R_i p_i \prod_{j \in S: j > i} (1-p_j)\right], $$ and the problem is: $$\max_{S\subseteq N}\left\{ -\sum_{i\in S} c_i + \sum_{i\in S} R_i p_i \prod_{j \in S: j > i} (1-p_j)\right\}$$