| paper | d4-conf-wine-2019-0031 |
| 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}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 14
statement extracted from the paper’s text layer
Given a connected graph \(G=(V,E)\) with \(|V|\ge 2\), maximum degree \(\Delta_G\), and \(\tau>3\Delta_G/(3\Delta_G+1)\), choose masses \(x_{v,i}\ge 0\) for \(v\in V\) and \(i\in\{R,B\}\), with \(x_{v,R}+x_{v,B}=1/|V|\) for each \(v\) and \(\sum_v x_{v,i}=1/2\) for each type. Define \(r_{v,i}(x)=\frac{\sum_{u\in N(v)}x_{u,i}}{\sum_{u\in N(v)}(x_{u,R}+x_{u,B})}\). Find a feasible allocation maximizing \(\sum_{v,i}x_{v,i}\mathbf{1}[r_{v,i}(x)\ge\tau]\), the mass of content residents, where each district's residents see the type mixture across all adjacent districts.
Treat each \(v\in V\) as a district of capacity \(1/|V|\), with complete mixing between adjacent districts. The decision variables are the masses \(x_{v,i}\); the objective is to maximize content mass under the paper's threshold rule.
Complete mixing between adjacent districts is a particular mean-field assumption; sparse individual-level neighborhoods may require local correlations that district masses do not capture.
fatal: False
The mirror covers Theorem 14's optimal-placement hardness question for two types on arbitrary graphs at high \(\tau\). It leaves the dynamics results in Theorems 1–12, the other placement results, and the simulations untouched.
My lead is a high-multiplicity version of Theorem 14. As printed, it says that finding an optimal placement in the SSG on an arbitrary network \(G\), with maximum degree \(\Delta_G\), is NP-hard for \(\tau>3\Delta_G/(3\Delta_G+1)\). Here “optimal” means minimizing the number of discontent agents; the result concerns two agent types and a fully occupied network. The authors prove it by reduction from Minimum Cut Into Equal Size, whose NP-hardness they cite from reference [19].
Continuous Mass-Optimal Schelling Placement. Take a finite connected graph \(G=(V,E)\) as a network of residential districts. There are two agent types, red and blue, each with total population mass \(1/2\), and a common threshold \(\tau>3\Delta_G/(3\Delta_G+1)\). Each district has capacity \(1/|V|\). Choose nonnegative masses \(x_{v,i}\) to assign to district \(v\) and type \(i\in\{\mathrm{red},\mathrm{blue}\}\), subject to
\[
x_{v,\mathrm{red}}+x_{v,\mathrm{blue}}=\frac1{|V|}
\quad\text{for every }v,\qquad
\sum_v x_{v,i}=\frac12
\quad\text{for each type }i.
\]
For a resident of type \(i\) in district \(v\), define their same-type neighborhood ratio by
\[
r_{v,i}(x)=
\frac{\sum_{u\in N(v)}x_{u,i}}
{\sum_{u\in N(v)}\bigl(x_{u,\mathrm{red}}+x_{u,\mathrm{blue}}\bigr)}.
\]
The question is to find an allocation \(x\) maximizing the mass of content residents:
\[
\sum_{v\in V}\sum_i x_{v,i}\,
\mathbf 1\!\left[r_{v,i}(x)\ge\tau\right].
\]
An allocation attaining that maximum is a solution. The graph stays finite and the strategic choice is still a district; the population is the continuous object.
The regime is a city with many residents in each of a fixed set of district-neighborhood roles. More precisely, replace each district by \(q\) equivalent residential slots and connect every slot in one district to every slot in an adjacent district. With \(q\) residents per district, total population is \(q|V|\) while the type support remains two. As \(q\) grows, the fractions of red and blue residents in each district give the variables \(x_{v,i}\). This makes the mass model a limit of fully occupied, discrete placements on the replicated network. Residents of the same type have the same threshold and neighborhood preferences, so the types are complete for the purposes of this problem.
The objective keeps the paper’s central placement question: how much of the population can be content under the same local threshold rule? It does not ask whether improving-response dynamics converge, or whether an equilibrium exists. Those questions, and the paper’s Theorems 1–12, are outside this mirror.
There is a concrete computational question here. For any proposed set \(S\subseteq V\times\{\mathrm{red},\mathrm{blue}\}\) of district-type pairs whose residents are to count as content, the requirements
\[
\sum_{u\in N(v)}x_{u,i}\ \ge\
\tau\sum_{u\in N(v)}(x_{u,\mathrm{red}}+x_{u,\mathrm{blue}})
\qquad ((v,i)\in S)
\]
are linear. Maximizing the mass assigned to those pairs is therefore an LP; maximizing over possible \(S\) gives the stated problem. The hard choice may lie in which district-type pairs can be made content together, rather than in the mass variables themselves.
I would expect hardness to transfer: Theorem 14’s reduction exploits graph partition structure and threshold neighborhoods, not a large number of distinct agent types. The continuous question is whether fractional allocation across districts can defeat the reduction’s gadgets. A proof would need to rule that out or establish a suitable gap; Theorem 14 alone does not do so. This also generates useful follow-ups: does the hardness survive the replicated-network limit, and what approximation or parameterized algorithms are possible in \(|V|\), \(\Delta_G\), and the number of types?
The weak point is the district replication. The paper gives one agent per vertex; this mirror treats a vertex as a neighborhood role with growing capacity. That is a plausible model of residents grouped by district, but it changes the placement space, and fractional mixing might make the discrete NP-hardness disappear. I think the question is still one the authors could recognize: it preserves their graph-based neighborhoods, threshold utility, and maximum-content objective while making population mass the decision variable.
Theorem 14 is a real computational anchor: it proves NP-hardness of finding a placement with the fewest discontent agents, so the “no computational result to mirror” objection does not apply. The negative case is that its population is inseparable from its location graph. Every vertex is one occupied location, and every agent’s content depends on the exact agents at adjacent vertices. The theorem gives no repeated agent roles within that graph.
The proposed replication supplies those roles by turning each vertex into a district of many slots and connecting every slot in one district to every slot in each adjacent district. Then every resident of a district sees the same mixture of neighboring populations. That is coherent, but it assumes complete mixing between adjacent districts. If instead the replicated graph preserves sparse, individual-level neighborhoods, aggregate district masses no longer determine who is content: local correlations matter. So the mass model is not forced by the paper’s graph sequence; it is a particular mean-field closure.
One can make the model more compelling by treating vertices as districts from the outset, with capacities and utilities defined by neighboring districts’ population shares. That is the strongest version of the mirror. But it changes the interpretation from assigning residents to individual locations to assigning mass to neighborhood roles. Whether that is a paper-specific continuation depends on the authors accepting zone-level mixing as part of their Schelling model. Without that, the connection to Theorem 14 is an analogy, not a limit of its placement problem.
That objection does not establish that the district model is uninteresting. Urban populations do have repeated demographic types, and the maximum-content-mass objective preserves the paper’s central optimization question. Nor can I use the possibility that fractional mixing defeats the reduction against the mirror: determining whether it does is precisely a computational question, and the answer could be valuable either way.
So the honest negative case is weak. The replication makes the model less canonical than the proponent suggests, but a district-level version is plausible and computationally well-posed. I cannot defend the stronger claim that no worthwhile continuous mirror exists in any scenario.
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.