d4-conf-ijcai-2015-0742

The strongest honest anchors are algorithmic. This paper has no numbered in-paper result asserting hardness. Its related-work section cites APX-hardness for envy-free revenue in more general matching markets, but that is an outside result in a different setting, so I would not use it as an anchor here.

My lead is Theorem 3.8, proved in this paper. It says that for any \(\epsilon\in(0,1)\), Auction 2 produces a deterministic outcome that is relaxed \(\epsilon B\)-envy-free and whose social welfare is at least that of any exactly envy-free outcome; its running time is \(O((n^2m/\epsilon)^{1/\epsilon})\). Here \(B\) is the largest bidder budget, and the running time is polynomial in \(n,m\) for fixed \(\epsilon\). The second anchor is Corollary 3.9, also proved here: the modified Auction 2 gives the corresponding relaxed \(\epsilon B\)-envy-free, revenue-maximizing outcome, with the same running-time bound.

I would mirror them with two versions of a Mass-Continuized Envy-Free Sponsored Search problem. The market in both versions has a finite support \(T\) of bidder types \(t=(v_t,B_t)\), with rational masses \(\mu_t>0\) summing to \(1\). A type records the bidder’s value per click and budget, exactly as in the paper. There are position classes \(j=1,\ldots,m\), with qualities \(q_1\ge\cdots\ge q_m\), and each class has supply \(\sigma_j\): the fraction of the population for which a position of that quality is available. The input consists of these rational masses and supplies, the integer values, budgets and qualities, and fixed \(\epsilon\). Let \(\tau=|T|\), and let \(L\) be the input bit length.

A solution is a finite table of nonnegative rational masses \(\lambda_{t,j,p}\). Each entry means that this much of type \(t\) receives position \(j\) and pays integer price \(p\). The entry \(j=0,p=0\) represents receiving no position. Each type’s entries sum to \(\mu_t\); the total mass assigned to position class \(j\) is at most \(\sigma_j\). Every assigned mass must satisfy \(p\le B_t\) and \(p\le v_tq_j\), so budgets and individual rationality match the paper. Prices can be restricted to integers in keeping with Lemma 3.4.

The outcome is exactly envy-free if every bundle \((j,p)\) received by type \(t\) is at least as good for that type as every other received bundle \((k,r)\) whose price \(r\) is within \(B_t\): \(v_tq_j-p\ge v_tq_k-r\). Relaxed \(\epsilon B_{\max}\)-envy-freeness uses the paper’s relaxation: require that inequality with an additive loss of at most \(\epsilon B_{\max}\) when \(r\le B_t-\epsilon B_{\max}\), where \(B_{\max}=\max_t B_t\). Social welfare is \(\sum_{t,j,p}\lambda_{t,j,p}v_tq_j\); revenue is \(\sum_{t,j,p}\lambda_{t,j,p}p\).

The welfare mirror asks for a relaxed \(\epsilon B_{\max}\)-envy-free solution whose social welfare is at least the maximum welfare over exactly envy-free solutions. The revenue mirror asks the same question for revenue. These retain the paper’s individual-level bundle comparisons, budget cutoffs, unit demand and objective functions. The population is the continuous object: each individual still receives one discrete position or none, while a type’s mass may be divided among different bundles.

A plausible regime is a very large pool of advertisers competing in a standardized campaign window, with one unit-demand placement per advertiser. Advertisers fall into a relatively small set of exact value-and-budget classes—for example, because they use standardized campaign tiers—while the platform’s position inventory grows with the pool and has stable per-capita supplies by quality. This is a scenario claim, not a claim that all sponsored-search auctions are high-multiplicity. It makes the comparison \(n\gg\tau\) plausible, and the authors should recognize the mirror: it preserves their bidder types, budgeted utility, envy-freeness, position qualities and welfare or revenue objective. Scaling position supply with population is a co-modification needed to keep the market meaningful.

There is a direct finite bridge. A discrete auction with \(n_t\) bidders of type \(t\) and one copy of position \(j\) per original slot maps to \(\mu_t=n_t/n\) and supply \(1/n\) for that slot. Conversely, when the masses and supplies have common denominator \(D\), scaling by \(D\) yields a finite auction with \(D\mu_t\) bidders of each type and \(D\sigma_j\) positions of each class. The continuous question is whether the added freedom to split type mass enables algorithms whose running time depends on \(m,\tau,L\), rather than on the number of named bidders.

I would bet on Class A for both mirrors: for each fixed \(\epsilon\), seek an algorithm polynomial in \(m,\tau,L\). The welfare and revenue objectives are linear in the mass table, and the finite set of position qualities and supported bidder types gives a natural place to look for a mass-based dynamic program or an optimization formulation. The affordability cutoff in envy-freeness is the obstacle: which comparisons apply depends on whether one bundle’s price is within another type’s budget. So tractability is a research question, not a consequence of Theorem 3.8 or Corollary 3.9. Further questions include whether the relaxation is needed for efficient computation, and whether the support size \(\tau\) admits a useful parameterized bound.

The weakest point is that the paper’s dynamic program is built around individual bidders: it orders them, groups their budgets, and indexes states by bidder counts. Replacing those counts with rational masses is a substantive change, and the paper does not show that the resulting problem has a polynomial-time solution in \(\tau\). The other vulnerability is the inventory regime: a single query has few slots, so the scenario needs a large standardized batch with per-capita position supply. These weaken the algorithmic inference, but not the mirror itself. The question still asks how the paper’s envy-free welfare and revenue problems behave when the society is a distribution over its own bidder types.