$ALG \ge \sum_j Q_j$ for every preallocation

Let every bidder $i$ have an XOS valuation $v_i$ with admissible clause set $W_i$, let $\mathrm{cl}_i$ be an XOS oracle for $v_i$, and let $\mathrm{win}$ be a highest-clause assignment rule. Fix any preallocation $\sigma=(S_1,\dots,S_n)$, write $p^i=\mathrm{cl}_i(S_i)$ and $Q_j=\max_{i}p^i_j$, and let $\mathrm{ALG}(\sigma)$ be the welfare of the allocation that gives each item $j$ to bidder $\mathrm{win}(\sigma,j)$. Then

The inequality holds pointwise, for every outcome of the rounding step; it reduces the analysis of the algorithm to a lower bound on the expectation of each $Q_j$ separately.

Formalization Note The paper justifies the step by the clause bound $\sum_{j\in T}p^{(i,S)}_j\le v_i(T)$ "for every $T\subseteq S$". The bundle a bidder receives need not lie inside its preallocated bundle, so the argument uses the bound for every $T$, which holds because $p^{(i,S)}$ is a clause of $v_i$'s expression. At least one bidder ($n\ge1$) is assumed.