Integer LP formulation and the existence of a solution
Express this problem as an integer linear program in which the variables take on values on [0,1] 


$$\begin{align}
\text{max: } &amp;\sum_i^m y_i \cdot p_i - \sum_j^n x_j \cdot s_j &amp;\\
\text{subject to: } &amp;x_i \geq y_j &amp;\forall i \in L_j \\
 &amp;0 \leq x_i \leq 1 &amp;\forall i \\
 &amp;0 \leq y_j \leq 1 &amp;\forall j
\end{align}$$

We see that if we select an investor $y_j$ we must select all of the investor's actors $x_i$ for $i \in L_j$. Our profit is the residual income left over from paying actors.


  Show that there must in fact be an integral optimal solution (as is the case, for example, with maximum flow and bipartite matching)


If our constraint matrix $A$ is totally unimodular, then the relaxed LP is sufficient to give a 0-1 solution.

Sketch: Observe that $A$ is an $N \times M$ matrix where $N = n + m$ and $M = \sum_j^m |L_j|$. This defines an incidence matrix of a bipartite graph where each row corresponds to an edge $(y_j, x_i)$ with coefficients $(-1, 1)$. We see that any cycle in the graph defined by $A$ will be balanced. That is, for any cycle $C$, $\prod_{e \in C: e=(u,v)} A_{e, v} = 1$. The proof for this can be done using the fact that any cycle in a bipartite graph is even. The corollary to this is that the incidence matrix for any balanced signed graph is totally unimodular.