| paper | d4-conf-ecai-2020-0379 |
| 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}\)-complete, even for \(\tau=1\), \(m=n\), and graphs of maximum degree \(3\), under standard explicit graph encoding. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 1
statement extracted from the paper’s text layer
Given a graph \(G=(V,E)\) with \(n=|V|\), rational \(\alpha\in[0,1]\), and rational threshold \(\theta\), decide whether there is a distribution \(p\) over subsets \(S\subseteq V\) such that \(\sum_S p_S=1\), \(\sum_S p_S|S|=n\alpha\), and \(\sum_S p_S e_G(S)\ge n\theta\), where \(e_G(S)=|\{v\in V\setminus S:N_G(v)\cap S\ne\varnothing\}|\). Interpret \(p\) as the mass of page copies using each integral placement, with high-valued items on \(S\), and maximize average externality across the continuous population of copies.
A continuum of slots across repeated copies of one page layout, with each position \(v\in V\) a type of mass \(1/n\). Each page receives an integral placement; a pooled supply provides a fraction \(\alpha\) of high-valued items, and the distribution over page configurations preserves adjacency-dependent externalities.
The opponent’s strongest residual concern is that type masses stay fixed at \(1/n\), while \(p_S\) carries the optimization; this bounds the mirror to repeated layouts with pooled stock, though the proponent explicitly models slots across page copies.
fatal: False
The mirror covers the binary-valued hardness result in Proposition 1 and the degree-two tractability result in Theorem 2. It leaves aside the two-valuation approximation guarantee, the general-valuation experiments, and the other special-graph results.
The strongest mirror I can defend is a publisher that uses the same page layout on a very large number of pages. Let one page’s regions and their adjacency graph be \(G=(V,E)\), with \(n=|V|\). Each region gets one indivisible content item, valued either \(0\) or \(1\); a low-valued item earns externality \(1\) exactly when an adjacent region has a high-valued item.
The population is the set of slots across all page copies. A type is a position \(v\in V\): slots in that position on different pages have the same neighbors and the same allocation role. Each type has mass \(1/n\). With \(M\) pages there are \(nM\) slots and \(n\) types, so the number of agents per type grows with \(M\). The publisher pools its inventory across pages, with a fraction \(\alpha\) of all items valued \(1\) and \(1-\alpha\) valued \(0\). A page still receives an integral allocation; only the average assignment to a type can be fractional.
Precisely, an instance gives \(G\), rational \(\alpha\), and a rational target \(\theta\). For each subset \(S\subseteq V\), let
\[
e_G(S)=|\{v\in V\setminus S:N_G(v)\cap S\ne\varnothing\}|.
\]
A solution is a distribution \(p\) over page configurations \(S\), with \(\sum_S p_S=1\) and \(\sum_S p_S|S|=n\alpha\). It represents the fraction of pages using each allocation, and is implementable by partitioning the continuum of pages. Its normalized externality is \(\frac1n\sum_S p_Se_G(S)\). The decision question is whether a solution with externality at least \(\theta\) exists; the optimization question is to maximize that quantity. The distribution matters: adjacency makes page positions’ assignments interdependent, so type marginals alone do not specify the externality.
My lead anchor is Proposition 1, proved in the paper. It says that, given \((G,O,\nu)\) and a threshold \(t\), deciding whether an allocation with \(\mathrm{Ext}_\pi(G)\ge t\) exists is NP-complete, even when valuations are only \(0\) and \(1\). Its reduction is from Dominating Set. The paper’s introduction also describes hardness at maximum degree \(3\), though that restriction is not printed in Proposition 1’s formal statement.
The pooled-continuum decision problem is NP-hard by the same reduction. Given a Dominating Set instance \((G,k)\), set \(\alpha=k/n\) and \(\theta=(n-k)/n\). For every configuration, \(e_G(S)\le n-|S|\), so the best possible average externality is at most \(1-\alpha\). Reaching that threshold forces every configuration used with positive mass to be a dominating set: each low-valued position must have a high-valued neighbor. Since the average size of those sets is \(k\), a dominating set of size at most \(k\) exists. Conversely, any such set can be enlarged to size \(k\) and placed on every page, meeting the threshold. Thus the continuum decision problem is NP-hard for a population of binary-valued items. For this finite-template model it is also in NP: an optimal mixture at a fixed mean size can be represented using at most two page configurations. I expect this unrestricted mirror to be hardness-transferring (Class B).
A second, useful anchor is Theorem 2, also proved in the paper: OPT-EXT is solvable in polynomial time when the graph has maximum degree at most \(2\), for general nonnegative valuations. For the binary-valued pooled mirror on such a graph, compute \(F(j)=\max_{|S|=j}e_G(S)\) for each \(j=0,\ldots,n\), using Theorem 2 on the instance with \(j\) high-valued items. Then solve the polynomial-size LP maximizing \(\frac1n\sum_j p_jF(j)\), subject to \(\sum_jp_j=1\), \(\sum_j jp_j=n\alpha\), and \(p_j\ge0\). This is a tractable (Class A) restriction of the mirror. Together, these anchors give a meaningful easy–hard boundary in the same continuous model.
I think the authors would recognize this as their problem: it keeps their page-layout motivation, their local graph, integral placement on each page, and their exact positive-externality objective. The continuous object is the population of slots across repeated pages, not fractional content, random perturbations, or a continuum of outcomes.
The soft spot is the pooled inventory across pages. The paper assigns a fixed set of objects to one graph; this mirror permits page-level inventories to vary as long as the publisher’s total stock is respected. That is plausible for a large publisher managing a common content inventory, and it is what makes mass the natural supply measure. But an author who regards each page’s inventory as fixed could reject that co-modification. Also, the number of position types is \(n\), so the strongest regime is where a layout is reused many times, rather than every instance having a constant-sized type set.
The mirror covers the binary-valued hardness result and the degree-\(2\) tractability boundary, not the paper’s approximation guarantees for two valuations or its experiments on general valuations. It raises further questions about approximation under pooled supply, the complexity for trees or bounded-treewidth layouts, and whether the configuration optimization can be handled by a useful pricing algorithm without enumerating all \(2^n\) page allocations.
The paper does have computational results to mirror: Proposition 1 is an NP-completeness result, and Theorem 2 gives a polynomial-time algorithm. So the negative case cannot rest on a lack of named results. It has to rest on whether the proposed mirrors continuize the population in ChoCo’s sense.
In the paper, the vertices are distinct locations in one graph, and the objects are placed among them. For a general graph, masses of position types do not determine externality: the objective depends on which locations are adjacent and which objects they receive. A faithful type description therefore has to preserve the graph’s structure; in the worst case, that leaves \(n\) distinct position types. There is no large population of interchangeable agents in the original instance.
The repeated-page construction makes the strongest case for a mirror, but its continuous variable is the distribution \(p_S\) over page allocations. The mass of each position type stays fixed at \(1/n\); the composition parameter \(\alpha\) describes pooled content stock. Since adjacency makes assignments interdependent, the distribution over configurations carries the information needed to calculate externality. Calling each configuration a type would make the type describe an allocation outcome, so the continuization has moved to outcomes. Calling positions the types leaves the population distribution fixed while the allocation mixture varies. Either way, this is a coherent convexification of repeated allocation instances, rather than a continuous society given by a distribution over agent types.
Pooling inventory may be a sensible extension, as the proponent argues, and it is permitted as a co-modification when population scaling requires it. But it is an additional modeling choice here. If every repeated page gets its own copy of the original inventory, the pages can be optimized independently. If pages share inventory, the problem gains a global supply constraint that the paper’s single-graph model does not have. That could motivate useful work on repeated allocation units, while leaving the central ChoCo question—what changes when the society itself is a type distribution—unanswered.
This applies to both anchors. The Proposition 1 reduction is valid for the pooled-page problem, but it certifies hardness through a dominating-set choice within a page configuration. It does not supply the missing population model. The proposed Theorem 2 mirror is also mathematically sound: compute \(F(j)\), then optimize over mixtures with the required mean number of high-valued items. Its LP is a convexification over page configurations, with a fixed graph as the computational core. It gives an easy–hard boundary for that repeated-template allocation problem, not for a society whose type masses vary.
A genuinely large network of sites would improve the population story, but the graph’s topology would still have to be represented to capture the externalities. A distribution over local site types alone would generally lose the adjacency pattern; preserving that pattern would require a richer network or configuration model. That may be a worthwhile research direction, but it is a further change of framework.
This negative case is strongest as a boundary argument: the proposed construction is plausible and its two computational questions are well posed, but the continuity is over mixtures of allocations to repeated graph copies. I cannot rule out an author recognizing that as a worthwhile adjacent project. The case against treating either result as a continuous-population mirror rests on the narrower scope ChoCo has set, and is weaker if ChoCo chooses to include repeated, networked allocation units as its population.
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.