Is it enough for linear program constraints to be satisfied in expectation? In the paper Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching, while proving that the RANKING algorithm is $\left(1 - \frac{1}{e}\right)$-competitive, the authors show that the dual is feasible in expectation (see Lemma 3 on page 5). My question is:


  Is it enough for linear program constraints to be satisfied in expectation?


It is one thing to show that the expected value of the objective function is something. But if feasibility constraints are satisfied in expectation, there is no guarantee that it will be satisfied on a given run. Moreover, there are many such constraints. So what is the guarantee that ALL of them will be satisfied on a given run?
I think the difficulty is that this wording slightly misleading; as they state more clearly in the Introduction (1.2), "the expected values of the dual variables constitute a feasible dual solution."

For every fixed setting of the dual variables $X$, we obtain some primal solution of value $f(X)$ and a dual solution of value $\frac{e}{e-1}f(X)$. (The dual is infeasible in some of these cases, but that's fine.)

So the expected value of the primal over all runs of the algorithm is $E[f(X)]$. But $E[X]$ is a dual-feasible solution, so there exists a dual solution of value $\frac{e}{e-1}f(E[X])$. The key trick is that $f(X)$ is linear in the dual variables $X$: In fact, here the dual variables are $\alpha_i$ and $\beta_j$, and each matching of vertex $i$ to $j$ adds a total of $\left(\frac{e-1}{e}\right)(\alpha_i + \beta_j)$ to the primal objective. So $E[f(X)] = f(E[X])$ and the conclusion follows.

(As a side note, I feel that, as this point is one of the main focuses of their paper (according to the abstract), it would have been nicer if they had explained this point! It doesn't seem at all obvious to me, and I would like to find out when it's true more generally.)