| paper | d4-journals-jair-2017-0044 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\) · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Lemma 29
statement extracted from the paper’s text layer
Given advertiser types \(t=(q_t,v_t,c_t)\) with rational masses \(\mu_t\) summing to \(1\), \(K\) ordered slots per page, rational position factors \(\lambda_s\), and an inventory ratio \(\rho\in(0,1]\), consider a continuum of pages of total mass \(\rho/K\), each assigned a full integral slate. For each ordered slate \(\sigma\in T^K\), choose its page mass \(y_\sigma\geq 0\), subject to \(\sum_\sigma y_\sigma=\rho/K\) and \(\sum_\sigma n_t(\sigma)y_\sigma\leq\mu_t\) for every type \(t\), where \(n_t(\sigma)\) counts that type in the slate. Maximize \(\sum_\sigma y_\sigma\sum_{s=1}^K q_{t_s}v_{t_s}\Lambda_s\prod_{r<s}c_{t_r}\), with \(\Lambda_s=\prod_{j<s}\lambda_j\), and find an optimal rational slate-mass distribution.
A linear program over masses \(y_\sigma\) of integral APDC slates assigned to a continuum of pages. Type masses \(\mu_t\) are the shared advertiser supplies, each bounded by its total use across pages; the objective is total expected social welfare. There are \(O(\tau^K)\) slate variables, so the explicit LP is tractable for fixed \(K\), while joint polynomial-time tractability in \(K\) and \(\tau\) depends on the pricing problem.
The mirror covers APDC social-welfare allocation through Lemma 29’s winner-determination objective; it leaves the equilibrium bounds, dominated-ads results, sorted-ads guarantees, and payment claims aside.
The strongest positive mirror is the paper’s APDC winner-determination problem, lifted to a high-multiplicity batch of auctions. The right regime is a large ad exchange clearing many similar search pages in a campaign window: advertisers have identical quality, value, and continuation-effect parameters within each type, but there are many advertisers and relatively few distinct types. Each ad impression has finite inventory and can be used once across the batch. The paper itself names multiple slates as future work, which makes this extension recognizable as a continuation of its allocation problem.
Call the mirror APDC Inventory-Batch Welfare Allocation\(_\infty\). An instance has a finite support \(T\) of advertiser types \(t=(q_t,v_t,c_t)\), rational masses \(\mu_t\geq0\) summing to \(1\), \(K\) ordered slots per page, rational position factors \(\lambda_s\), and a rational inventory ratio \(\rho\in(0,1]\). A type is complete for this allocation problem: its ads share click quality \(q_t\), value \(v_t\), and continuation probability \(c_t\). Consider a continuum of pages of total mass \(\rho/K\); each page receives a full, integral \(K\)-ad slate. For each ordered slate \(\sigma=(t_1,\ldots,t_K)\), let \(y_\sigma\geq0\) be the mass of pages receiving it. The question is to choose \(y\) maximizing
\[ \sum_{\sigma} y_\sigma \sum_{s=1}^{K} q_{t_s}v_{t_s}\Lambda_s \prod_{r<s}c_{t_r}, \qquad \Lambda_s=\prod_{j<s}\lambda_j, \]
subject to
\[ \sum_\sigma y_\sigma=\frac{\rho}{K}, \qquad \sum_\sigma n_t(\sigma)y_\sigma\leq\mu_t \quad\text{for every }t\in T, \]
where \(n_t(\sigma)\) counts occurrences of type \(t\) in slate \(\sigma\). A solution is an optimal rational slate-mass distribution; because the population is atomless, it can be realized by assigning every page an integral slate, even though type mass is split fractionally across slates. The slots remain discrete. What becomes continuous is the advertiser population and its inventory.
My anchor is Lemma 29, stated in this paper and derived there from the cited Color Coding results of Alon, Yuster, and Zwick (1994). It says that colored-ads finds an optimal social-welfare allocation for \(N\) ads and \(K\) slots with probability \(1-e^{-r/e^K}\) after \(r\) random restarts; each restart takes \(O(2^K N)\) time, and the algorithm uses \(O(2^K+N)\) memory. The lemma concerns the underlying APDC allocation problem, not just an encoding. It is a result of this paper, though its proof is referred to standard color-coding properties. The paper gives no numbered hardness result for this allocation problem: its introductory statement that APDC optimization is commonly believed hard is not a proved hardness anchor here.
For the batch mirror, enumerate the \(O(\tau^K)\) ordered type slates, where \(\tau=|T|\). Their welfare contributions and inventory use are fixed coefficients, so the stated problem is a linear program with \(\tau+1\) constraints. I expect it to be tractable for fixed, small \(K\), with running time polynomial in the explicit slate count and input bit length. I do not claim a polynomial bound jointly in \(K\) and \(\tau\): finding an efficient pricing algorithm for the slate columns is a further question, and could reveal continuum-specific hardness. The mirror therefore gives a concrete optimization question and a plausible route to Class A in the small-slot regime emphasized by the paper, without claiming that the paper’s finite-\(N\) difficulty simply disappears.
The scope is the paper’s APDC social-welfare allocation and its exact-winner-determination result. I would leave the GSP and PDC-VCG equilibrium comparisons, their price-of-anarchy and price-of-stability bounds, and the DSIC payment claims outside this mirror; they require additional strategic modeling.
The weak point is the batch-inventory regime. The paper studies a single auction where advertisers compete for that page’s slots; this mirror adds a campaign-level constraint that an ad’s mass is used only once across a batch. That makes the continuous population meaningful, but it is not a literal limit of the single-auction instance. The case rests on the authors recognizing the same APDC slate-welfare problem under a plausible inventory regime, rather than accepting a direct continuization of their exact original auction.
Lemma 29 is a genuine computational result: colored-ads finds an optimal APDC allocation, with per-restart time \(O(2^K N)\). The strongest objection is that its allocation is for one page, which has only \(K\) winners. With \(n\) advertisers and fixed \(K\), at most a \(K/n\) fraction of the population is selected. In a normalized continuum that fraction vanishes, so welfare per advertiser collapses to zero. Keeping unnormalized welfare instead asks an atomless model to select \(K\) individual advertisers. The continuum of users does not fix this: their behavior is already represented through expected click-through rates.
A nondegenerate version must scale the number of pages with the advertiser population. The proposed inventory-batch LP does that, and it is a serious candidate mirror: its slate variables represent full integral assignments to each page, while type mass is split across pages. But it couples multiple auctions through shared advertiser supply. That is a campaign-level allocation problem, not the single-page winner-determination problem of Lemma 29. In particular, the coloring algorithm’s result does not transfer directly to this batch problem.
That distinction is the negative case’s limit. The paper explicitly names multiple slates as future work, and the batch model is a plausible high-multiplicity version of that direction. With fixed \(K\), its \(O(\tau^K)\) slate LP is already tractable; with variable \(K\), its pricing problem could still be an interesting question. Scaling \(K\) instead would avoid the single-page degeneracy, but would change the page model itself. Equilibrium and payment results have a similar difficulty: a single slot serves an individual bidder, so a mass model needs a batch or capacity structure to preserve meaningful allocations and deviations.
So I can make a strong case that Lemma 29 has no useful direct single-auction continuum limit. I cannot honestly extend that to “no worthwhile continuous mirror in any scenario.” The batch-inventory mirror survives the programme’s scope test, and the paper’s stated interest in multiple slates makes it hard to dismiss as unrelated. The negative case is therefore weak against the proponent’s best version.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.