Theorem 3.3 — the greedy price-update algorithm is a 2-approximation for XOS bidders

Let $v_1,\dots,v_n$ be XOS valuations on the items $M=\{1,\dots,m\}$, each given by an XOS expression (a nonempty set of additive clauses with nonnegative item values, $v_i(S)=\max_k w^i_k(S)$). Run the greedy price-update algorithm of §3.3: bidders are processed in order $1,\dots,n$; bidder $i$ takes its demand $S_i$ at the current item prices (removing those items from earlier bidders), and the prices of the items of $S_i$ are set to their values in a maximizing clause for $S_i$ in $v_i$. Let $A_1,\dots,A_n$ be the resulting allocation. Then, for every demand oracle and every XOS oracle used by the algorithm, and for every allocation $O_1,\dots,O_n$,

In the paper's words, the algorithm provides a 2-approximation to the optimal allocation. It uses only demand queries and XOS queries and, unlike the LP-based algorithms of §3.1–3.2, is combinatorial.

Formalization Note The paper compares with the optimal allocation; the statement quantifies over every allocation, which is equivalent. The oracles are arbitrary functions meeting their specifications, so the guarantee holds for every tie-breaking in the demand and in the choice of maximizing clause. Running time is not modelled.