= Greedy half-approximation for submodular welfare
{title2=$A(v)\geq\tfrac12\operatorname{Opt}(v)$}
Allocate each remaining item to a bidder with greatest current marginal gain. For nonnegative monotone <submodular set functions>, this uses $O(mn^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(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')$. 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 $\operatorname{Opt}(v')\geq\operatorname{Opt}(v)-2w$. Induction proves the guarantee, with the zero-item case immediate even for nonzero empty-bundle values.
Back to article page
