Greedy half-approximation for submodular welfare ($A(v)\ge \frac{1}{2}\mathrm{Opt}(v)$)

Allocate each remaining item to a bidder with greatest current marginal gain. For nonnegative monotone submodular set functions, this uses $O(m{n}^2)$ value queries and achieves the displayed guarantee. To prove it by induction, let the first allocation give item $j$ to bidder $r$, and set $w=v_r(\{j\})$. Contract that item into bidder $r$'s value by replacing it with $v_r^{\prime }(S)=v_r(S\cup \{j\})-w$ and leave the other bidders' values unchanged. The remaining greedy run is identical, and $A(v)=w+A(v^{\prime })$. Move $j$ from its owner in an optimal allocation to $r$. Submodularity bounds the owner's loss by its initial singleton marginal, which is no larger than the selected greedy marginal and hence no larger than $w$. The receiver's value cannot decrease, so $\mathrm{Opt}(v^{\prime })\ge \mathrm{Opt}(v)-2w$. Induction proves the guarantee, with the zero-item case immediate even for nonzero empty-bundle values.