§3.1.1 — Pr[B] < 3/4: the preallocation's welfare falls below OPT*/3 with probability < 3/4

Let $v_1,\dots,v_n$ be normalized, monotone valuations and let $x$ be LP-feasible with value $L=\sum_{i,S}x_{i,S}v_i(S)$. Suppose $L>3\,v_i(M)$ for every bidder $i$, i.e. $L>3\max_i v_i(M)$. Let $A=\sum_i v_i(S_i)$ be the welfare of the randomized-rounding preallocation and $B$ the event $A<L/3$. Then

Together with the items bound, this shows that one round of randomized rounding produces a preallocation with both required properties with constant probability.

Formalization Note The paper normalizes $\max_i v_i(M)=1$ and assumes $OPT^*>3$; the statement uses the scale-free equivalent $L>3\max_i v_i(M)$. The paper's definition of $B$ drops the sum ("$v_i(S_i)<\frac13 OPT^*$"); the display $\Pr[B]=\Pr[A<OPT^*/3]$ fixes the meaning used here. The paper's text announces $\Pr[B]<3/4$ and its display ends with $\le 3/4$; the strict inequality is stated, which the display's middle bound $9/(4\,OPT^*)$ with $OPT^*>3$ gives. The statement assumes only LP feasibility of $x$ (the paper uses the optimal $x$, which is a special case).