d4-conf-wine-2015-0007

I see one defensible mirror, for a specific large-market version of the paper’s bidder-conflict welfare problem.

Take a batch of many similar ad opportunities, with \(N\) advertisers and \(N_t/N\to\mu_t\) for each of \(\tau\) advertiser types. A type gives the advertiser’s valuation function and its conflict relationships: advertisers of type \(t\) have the same valuation \(v_t\), and they conflict with all advertisers in each type \(u\) to which \(t\) points in a directed type graph \(H\). Each \(v_t\) is fractionally sub-additive and is given by a demand oracle. Normalize the market so item \(k\) has supply \(b_k\) per unit population; in a market of size \(N\), that means \(Nb_k\) copies. This supply scaling keeps the allocation meaningful as the population grows.

Here is the continuous problem I would hand to a prover: Type-Conflict Continuous Welfare Maximization. The input is \(I\), the rational masses \((\mu_t)_{t\in T}\) with \(\sum_t\mu_t=1\), the rational supplies \((b_k)_{k\in I}\), the type conflict graph \(H\), and the valuation oracles. Choose \(x_{t,S}\ge 0\), the mass of type \(t\) assigned bundle \(S\subseteq I\), subject to
\[ \sum_{S\subseteq I}x_{t,S}=\mu_t \quad\text{and}\quad \sum_{t\in T}\sum_{S\ni k}x_{t,S}\le b_k \quad\text{for each }k\in I. \]
Let \(A(x)=\{t:\sum_{S\ne\emptyset}x_{t,S}>0\}\). Its welfare is
\[ W(x)=\sum_{\substack{t\in T:\\N_H^+(t)\cap A(x)=\emptyset}} \sum_{S\ne\emptyset}x_{t,S}v_t(S). \]
Thus a type earns value only when none of its conflicting types receives any item, matching the paper’s negative-externality rule at type level. The question is whether one can return a feasible \(x\) with welfare at least \(\mathrm{OPT}/O(\Delta\log\log\Delta/\log\Delta)\), in time polynomial in \(m,\tau,L\) and demand-oracle calls, where \(\Delta\) is the maximum out-degree of \(H\). This is an approximation question about the underlying allocation problem, not its encoding.

My anchor is Theorem 7, proved in the paper. It says that for combinatorial auctions with bidder conflicts, if bidders have fractionally sub-additive valuations and each bidder has a demand oracle, there is a polynomial-time \(O((\Delta\log\log\Delta)/\log\Delta)\)-approximation algorithm for social welfare. The continuous question keeps its goods, welfare objective, valuation restriction, and conflict externality, while replacing counts of interchangeable advertisers by masses and scaling supply with the market. With few advertiser archetypes and a bounded-degree type graph, this is a plausible approximation-tractable question in the programme’s sense. The paper’s cone-program approach makes adaptation a credible direction, though Theorem 7 does not itself establish the mass version.

The regime is a large advertising market with many advertisers but a modest set of repeated valuation and competitor classes. That is a scenario claim, not a claim that every auction has high multiplicity. The mirror is most convincing when competitor classes are economically meaningful—for example, advertisers grouped by product category whose campaigns compete across categories.

The soft spot is that this type model makes conflicts complete between adjacent classes: in the \(N\)-advertiser market, an advertiser may then have \(\Theta(N)\) conflicting advertisers. The theorem’s \(\Delta\) is the degree of the type graph here, not the individual-bidder degree in the paper’s input. So the named result motivates the question, but its guarantee cannot simply be transferred. If conflicts instead run only between particular individuals, their identities may have to enter the type description, causing \(\tau\) to grow with \(N\). I would treat resolving that gap—whether the mass problem admits the theorem’s approximation guarantee, or whether it needs a different continuous representation—as the main prover task.

This case covers Theorem 7’s welfare-approximation result only. It does not claim a mirror for the paper’s truthful mechanisms, or for its limited-slot results.