Combinatorial Auctions and Approximation Mechanisms

Given a graph $G=(V,E)$ and $k$: let the items be the edges $E$, and give each vertex $i$ a player with $S_i^* = \{e\in E \mid i\in e\}$ (the adjacent edges) and $v_i^* = 1$.

A set $W$ satisfies $S_i^*\cap S_j^* = \emptyset$ for distinct $i,j\in W$ iff the corresponding vertices form an independent set, and the social welfare is exactly its size. Membership in NP is trivial — guess the allocation and compute.

∎

First, a truthful bidder never gets negative utility: zero when losing, and when winning his value is at least the critical value, which equals his payment.

Suppose the bidder’s true type is $(S,v)$ and he reports $(S',v')$. If $(S',v')$ loses or $S'\not\supseteq S$, truth is at least as good. So assume $(S',v')$ wins and $S'\supseteq S$.

Reporting $(S,v')$ is no worse than $(S',v')$. Let the payments be $p'$ and $p$. For every $x<p$, bidding $(S,x)$ loses since $p$ is critical; by monotonicity $(S',x)$ also loses, so $p'\ge p$. Hence switching still wins and the payment does not increase.

Reporting $(S,v)$ is no worse than $(S,v')$. If $(S,v)$ wins with critical value $p''$, then any $v'>p''$ wins with the same payment, and any $v'<p''$ loses for zero utility. If $(S,v)$ loses, then $v$ is below the critical value, so any winning $(S,v')$ costs more than $v$ — an unprofitable deviation.

∎

Let $OPT$ be an optimal winner set and $W$ the greedy output. For $i\in W$ let $OPT_i = \{j\in OPT,\ j\ge i \mid S_i^*\cap S_j^*\ne\emptyset\}$ — those excluded because of $i$, plus $i$ itself. Since $OPT\subseteq\bigcup_{i\in W}OPT_i$, it suffices to show $\sum_{j\in OPT_i}v_j^*\le\sqrt m\,v_i^*$.

Every $j\in OPT_i$ came after $i$ in the greedy order, so $v_j^*\le v_i^*\sqrt{|S_j^*|}/\sqrt{|S_i^*|}$. Summing and applying Cauchy–Schwarz,

$$\sum_{j\in OPT_i}v_j^* \le \frac{v_i^*}{\sqrt{|S_i^*|}}\sum_{j\in OPT_i}\sqrt{|S_j^*|} \le \frac{v_i^*}{\sqrt{|S_i^*|}}\sqrt{|OPT_i|\sum_{j\in OPT_i}|S_j^*|}$$

Every $S_j^*$ for $j\in OPT_i$ intersects $S_i^*$, and since $OPT$ is an allocation those intersections are disjoint, giving $|OPT_i|\le|S_i^*|$; also $\sum_{j\in OPT_i}|S_j^*|\le m$. Substituting gives $\sqrt{|S_i^*|\,m}$, hence the claim.

∎

Each bidder receives his demand, so for any feasible fractional $X^*$, using $\sum_S X_{i,S}^*\le1$,

$$v_i(S_i^*)-\sum_{j\in S_i^*}p_j^* \ \ge\ \sum_{S}X_{i,S}^*\Big(v_i(S)-\sum_{j\in S}p_j^*\Big)$$

Sum over bidders. It remains to check the price terms: the left side totals $\sum_{j}p_j^*$ exactly, since unallocated items have price zero, while the right side is at most $\sum_j p_j^*$ since each price has coefficient at most 1 by the item constraint.

∎

Take the integral primal optimum and a dual optimum $p^*,u^*$. Complementary slackness makes constraint $u_i+\sum_{j\in S}p_j\ge v_i(S)$ binding wherever $x_{i,S_i^*}=1$, so $u_i^* = v_i(S_i^*)-\sum_{j\in S_i^*}p_j^*$; the same constraint for other bundles then gives the demand condition. And where the item constraint is strict — which for integral solutions means the item is unallocated — complementary slackness forces $p_j^*=0$.

∎

Base: an atomic bid is already an OR* bid. OR step: merge the clause sets of the sub-bids. XOR step: for each pair of atoms $(S,v)$, $(T,v')$ in two different sub-bids, introduce a dummy $x_{ST}$; each bid $(S,v)$ becomes $(S\cup\{x_{ST}\mid T\},v)$ where $T$ ranges over atoms of all other sub-bids.

This gives exactly $s$ clauses, but possibly many dummies. The only role of a dummy is to forbid two or more atoms being taken together, so replace them all with at most $\binom s2$ new dummies, one per forbidden pair, added to both atoms of that pair.

∎

To compute the marginal value $v(S\cup\{j\})-v(S)$: set $p_i=0$ for $i\in S$, $p_i=\infty$ for $i\notin S\cup\{j\}$, and binary search on $p_j$ — the highest $p_j$ whose demand contains $j$ is the marginal value. Then $v(S) = \sum_{j\in S}\big(v(\{i\in S : i\le j\}) - v(\{i\in S : i<j\})\big)$.

∎

The dual has only $n+m$ variables but exponentially many constraints; the ellipsoid method runs in polynomial time on such programs given a separation oracle.

Rewrite the dual constraint as $u_i\ge v_i(S)-\sum_{j\in S}p_j$. A demand query to bidder $i$ at prices $p$ reveals exactly the $S$ maximizing the right-hand side. So to test feasibility of $(u,p)$: query each bidder for his demand $D_i$, and check only the $n$ constraints $u_i+\sum_{j\in D_i}p_j\ge v_i(D_i)$ (with $v_i(D_i)$ simulated by demand queries). If none is violated, $(u,p)$ is feasible; otherwise we have a violated constraint.

Recovering the primal. Ellipsoid encounters only polynomially many constraints; deleting the rest leaves the same dual optimum. Take the dual of that reduced program — same solution as the original primal, but with polynomially many variables — solve it, and set all other variables to zero.

∎

For a 0/1 valuation $v$ define the dual $v^*(S) = 1-v(S^c)$. Note $v^*$ is a monotone 0/1 valuation, and for every partition, $v(S)+v^*(S^c) = 1$.

Key lemma: for $v\ne u$, the communication sequence on $(v,v^*)$ differs from that on $(u,u^*)$.

Suppose not. Then the same sequence occurs on $(v,u^*)$: Alice does not see $u^*$ so she behaves as in $(v,v^*)$; Bob behaves as in $(u,u^*)$; neither ever notices a deviation. Likewise for $(u,v^*)$. So one allocation $(S,S^c)$ is produced in all four cases — impossible.

Since $u\ne v$ there is $T$ with, WLOG, $v(T)=1$ and $u(T)=0$, so $v(T)+u^*(T^c)=2$ and optimality on $(v,u^*)$ forces $v(S)+u^*(S^c)\ge2$. But $(v(S)+v^*(S^c))+(u(S)+u^*(S^c)) = 2$, so $u(S)+v^*(S^c)\le0$ — the allocation is not optimal for $(u,v^*)$, contradiction.

From the lemma to the bound: the number of communication sequences is at least the number of distinct 0/1 valuations, which is at least $2^{\binom{m}{m/2}}$ (count valuations that are 0 below size $m/2$, 1 above, and free at size $m/2$). A binary sequence set of that size needs one sequence of length $\ge\binom{m}{m/2}$.

∎

Claim: at every stage, $S_i\subseteq D_i$ for every bidder. True initially. Consider an update step for bidder $i$: for $i$ himself, $S_i$ afterwards equals $D_i$ exactly (the price changes on newly added items match those defining $D_i$). For $k\ne i$, two things can happen — items may be taken from $S_k$ by $i$, which shrinks $S_k$ without affecting $D_k$; and prices outside $S_k$ may rise, which does not affect $S_k$, while substitutes directly implies the only items that can leave $D_k$ are those whose price strictly increased, hence not in $S_k$.

Given the claim, no item ever demanded is left unallocated, so $\bigcup_iS_i$ contains every positively priced item; termination requires all $D_i=S_i$. Near-optimality follows as in the First Welfare Theorem.

∎

Each step raises at least one price and a bundle price never exceeds its value, so the auction terminates. The allocation is revenue-maximizing by construction, so it suffices that each bidder gets an $\epsilon$-demand. Losers get $\emptyset$, their demand, by the termination condition. For a winner, the auction maintains that every bundle with $p_i(T_i)>0$ is an $\epsilon$-demand: such a $T_i$ was $i$‘s exact demand at some earlier round, hence an $\epsilon$-demand after the increment, and since then only other bundles’ prices have risen.

∎

Feasibility: since $T_{LB}\ge T_j\ge\frac{\sum_{k\le j}p_k}{\sum_{l\le i_j}s_l}$ we can fractionally assign jobs $1..j$ within the first $i_j$ machines; and $T_j\ge p_j/s_{i_j}$ gives $p_j/s_i\le T_{LB}$ whenever $j$ lands on $i$. Setting $j=n$ gives full assignment.

Monotonicity: if $s_i$ rises to $\alpha s_i$, then $T_{LB}'\le\alpha T_{LB}$ (scaling all speeds by $\alpha$ scales $T_{LB}$ by $\alpha$, and the actual other speeds are no larger). If $i$ was full, $l_i' \le T_{LB}'s_i \le \alpha T_{LB}s_i = l_i'$… more precisely $l_i'\le T'_{LB}s_i\le T_{LB}\alpha s_i$, matching. Otherwise $i$ is the last nonempty machine, and since $T_{LB}'\ge T_{LB}$ all earlier machines take at least as much as before, so $i$ cannot gain load.

∎

Approximation: machine $i$ may get two extra jobs — $j$ shared with $i-1$ and $k$ shared with $i+1$. If $j$ rounds to $i$ then $i$ had at least $1-\alpha$ of it, so the extra load is at most $\alpha p_j$; similarly at most $(1-\alpha)p_k$ for $k$. Since $\max\{p_j,p_k\}\le T_{LB}$, the total extra is at most $T_{LB}$.

Truthfulness: machine $i-1$ gets $j$ with probability $\alpha$, so $i$ gets it with probability $1-\alpha$, and gets $k$ with probability $\alpha$ — so the expected load equals the fractional load, which is monotone.

∎

Three observations. (a) For $i>1$ and $\beta<d_i$, $T_{LB}(\beta,d_{-i})\le\frac54T_{LB}(d_i,d_{-i})$: give machine $i$ nothing and shift each earlier machine’s jobs down one; machines $2..i-1$ stay under the limit since each is faster than its successor, and machine 1 gains at most a factor $\frac54$ since always $d_1\ge4d_2$. (b) If a machine $i>1$ slows, the work on faster machines does not decrease, since $T_{LB}$ is monotone. (c) If the fastest machine slows but stays fastest, its work does not increase: all breakpoints shift by the same factor $c$, so if no $s_i$ crosses a new breakpoint everything scales and machine 1 keeps the same jobs; if some do, their $d_i$ fall, so $T_{LB}$ falls and machine 1 gets no more.

Now suppose $i$ slows to $s_i'$. If $i$ is fastest and stays so, use (c). If the title of fastest passes to $i'$, insert an artificial breakpoint where their speeds coincide; $i$‘s work as fastest is at least $\frac85s_iT$ while its work once $i'$ is fastest is at most $2\frac{s_1}{2.5}T<\frac85s_iT$. If $i$ is not fastest but full, then $d_i'<d_i$ so by (a) its work goes from $\ge Td_i$ to at most $2\cdot\frac54T\frac{d_i}{2.5}=Td_i$. If $i$ is not full, use (b).

∎