| paper | d4-conf-wine-2020-0011 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard to approximate within \(k^{1-\varepsilon}\) for every fixed \(0<\varepsilon<1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.1
statement extracted from the paper’s text layer
Given categories \(\Theta\), a finite support \(\mathcal T\) of complete advertiser types \(t=(\theta,v)\) with rational masses \(\mu_t\) summing to \(1\), and \(N\) ordered slots with rational capacities \(q_j\) summing to \(1\), nonincreasing discounts \(\alpha_{\theta,j}\), and gap matrix \(G\), choose \(z_{t,j}\in\{0,1\}\) and assigned masses \(x_{t,j}\ge 0\). Require \(\sum_t z_{t,j}\le 1\), \(x_{t,j}\le q_jz_{t,j}\), and \(\sum_jx_{t,j}\le\mu_t\); if \(z_{t,j}=1\) for category \(\theta\), then \(z_{t',\ell}=0\) for every type \(t'\) of category \(\phi\) and every \(1\le\ell-j\le G_{\theta\phi}\). Maximize \(\sum_{t=(\theta,v),j}v\alpha_{\theta,j}x_{t,j}\).
A single shared ordered slate with per-capita slot capacities: advertisers are grouped into complete types carrying mass, each slot receives at most one type, and the objective is mass-weighted welfare under the paper's category gap rules.
The proposed aggregate model treats slots as one shared sequence; it does not specify how to represent multiple separate feeds whose gap rules apply within each feed rather than across feeds.
fatal: False
The question mirrors the gap-rule welfare problem and supports Theorem 4.1's hardness anchor; it does not establish a continuous analogue of Theorem 4.2's specific dynamic-programming bound. It leaves the no-gap allocation and pricing results, including Theorem 3.1 and Corollary 3.7, outside the stated case.
My lead is the gap-rule welfare problem. It has a named hardness result, and the reduction’s obstruction survives when each ad type represents a large cohort. I would mirror this part of the paper, not claim that every result in it has a useful continuous counterpart.
Continuous-Mass Gap-Constrained Ad Allocation. An instance has a finite set \(\Theta\) of ad categories and a finite support \(\mathcal T\subseteq\Theta\times\mathbb Q_{\ge0}\) of complete advertiser types \(t=(\theta,v)\), with rational masses \(\mu_t\) summing to \(1\). It also has \(N\) ordered slots with rational capacities \(q_j\) summing to \(1\), nonincreasing rational discount curves \(\alpha_{\theta,j}\), and a gap matrix \(G\). A type records everything relevant to the allocation: its category and value per conversion.
Choose \(z_{t,j}\in\{0,1\}\) to indicate which type, if any, occupies slot \(j\), and \(x_{t,j}\ge0\) for the mass assigned there. Require \(\sum_t z_{t,j}\le1\), \(x_{t,j}\le q_jz_{t,j}\), and \(\sum_jx_{t,j}\le\mu_t\). If \(z_{t,j}=1\) for a type in category \(\theta\), then no later slot \(\ell\) with \(1\le\ell-j\le G_{\theta\phi}\) may be assigned a type in category \(\phi\). The question is to maximize
\[
\sum_{t=(\theta,v)}\sum_{j=1}^{N}v\,\alpha_{\theta,j}x_{t,j}.
\]
Here mass is advertiser population, and \(q_j\) is per-capita slot capacity. The ordered slots and gap rules retain their role in the paper’s problem.
My anchor is Theorem 4.1, proved in this paper. It states that the Ad Types problem with Gap Rules is hard to approximate within \(k^{1-\epsilon}\) for every \(\epsilon>0\), unless \(\mathrm{P}=\mathrm{NP}\), even when every discount curve is identically \(1\). The proof reduces Maximum Independent Set: it uses \(k=n=|V|\), one value-\(1\) ad per type, and sets \(G_{ij}=k\) for graph edges and \(0\) otherwise. Thus the maximum welfare equals the independent-set size.
The theorem’s printed construction has only one ad per type, so by itself it is not a high-multiplicity instance. But the reduction scales within the paper’s model. Given a graph on \(k\) vertices, take \(N=rk\) slots and \(r\) identical advertisers per vertex-type, each of mass \(1/N\). Each type then has mass \(1/k\). Set all values and discounts to \(1\); for every graph edge set both directed gaps to \(N\), and set other gaps, including same-type gaps, to \(0\). Adjacent types cannot both appear anywhere in the slot sequence. Any independent set \(S\) can use all \(r\) ads of each type in \(S\), giving welfare \(|S|/k\); conversely, the types used by any feasible allocation form an independent set. The continuous problem therefore has optimum \(\alpha(G)/k\), where \(\alpha(G)\) is the maximum independent-set size. Fractional masses do not evade the type conflicts, so the approximation hardness carries over. Here \(N\) can be much larger than the support size \(\tau=k\).
A plausible regime is a large publisher allocation with many advertisers in a small number of campaign categories, where advertisers within a cohort share the same value and other relevant attributes. Mutual-exclusion rules between categories—for example, competing campaigns that cannot appear together in one feed—fit the paper’s diversity motivation. The authors should recognize this as their gap-rule welfare problem with advertiser cohorts aggregated by full type. The \(1/N\) slot capacities are the inventory scaling that accompanies the population scaling; advertiser mass remains the continuous object.
I expect this mirror to be hardness-transferring (Class B): the reduction’s combinatorics live in the interaction graph on types, not in the number of individual advertisers. This case covers Theorem 4.1 and the gap-rule welfare problem only; it does not mirror Theorem 3.1’s no-gap allocation algorithm or the pricing results.
The weak point is the full-horizon gap: the construction requires a rule that excludes a pair of categories across the entire feed. That is plausible as categorical mutual exclusion, but it does not establish hardness for realistic fixed-length local gaps. If gaps stay fixed as \(N\) grows, their normalized length shrinks. That leaves natural follow-up questions about hardness with bounded normalized gaps, and about tractability under restrictions on the type-interaction graph.
Theorem 4.1 is the only anchor the proponent raises. Its scaled reduction is mathematically sound: with \(r\) advertisers of mass \(1/(rk)\) per type and \(rk\) ordered slots of capacity \(1/(rk)\), the optimum is \(\alpha(G)/k\). Fractional mass does not defeat the type conflicts, and the approximation hardness carries over. I would not reject the mirror just because its hardness comes from the type-interaction graph, or because the construction duplicates identical advertisers; the programme explicitly treats high multiplicity as supporting evidence.
The stronger objection is that the scaling changes what the slots mean. Keep the paper’s finite feed inventory while advertiser population grows, and each advertiser has mass \(1/P\) for population \(P\). At most \(n\) advertisers can be assigned, so allocated population mass is at most \(n/P\), which vanishes. Count welfare per winner instead, and once a type has positive mass it supplies arbitrarily many candidates for the finite slots: the masses cease to matter, leaving a support-only problem.
The proposed repair scales the ordered horizon with the advertiser population. That gives the reduction enough capacity, but it describes one feed whose length grows with the cohort. In a large publisher setting, increased inventory would more naturally mean many users seeing separate feeds. Gap rules apply within each feed; concatenating positions across feeds would create conflicts between ads that never share a sequence. With separate feeds, the reduction can place different types on different feeds, so its independent-set objective no longer follows. Preserving that objective across feeds would require a campaign-wide incompatibility rule, a different constraint from “after showing type \(i\), the next \(G_{ij}\) slots cannot show type \(j\).”
There is another pressure point in the proposed limit: a tiny positive allocation to a slot can trigger the same gap ban as filling it. The binary slot indicators preserve that event in the finite construction, but a mass-only limit has to explain why an arbitrarily small share of a cohort should exclude other types across a growing horizon.
So the best case against is that the theorem’s hardness survives the proposed arithmetic scaling, while the natural fixed-feed or many-feed interpretations do not preserve its model. That makes this a narrow, stipulated mirror rather than a robust one. The negative case is still weak against the universal claim: a single shared, growing slate with whole-horizon category exclusions is coherent, and the authors might recognize it as their problem. I cannot honestly rule out that scenario or claim that no worthwhile mirror exists.
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.