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?