| paper | d4-conf-aaai-2021-1989 |
| 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, even for \(\tau=2\) on trees with strictly positive integer capacities and \(R+B=\sum_v q_v\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.3
statement extracted from the paper’s text layer
Given a finite graph \(G=(V,E)\), rational capacities \(q_v\ge 0\), rational total masses \(R,B\), and a rational threshold \(s\), does there exist a real allocation \(x_{v,c}\ge 0\) with \(x_{v,R}+x_{v,B}\le q_v\), \(\sum_v x_{v,R}=R\), and \(\sum_v x_{v,B}=B\), such that \(W(x)\ge s\)? For each \(v\) and \(c\in\{R,B\}\), define \(u_{v,c}(x)=\frac{\sum_{w\in N(v)}x_{w,c}}{\sum_{w\in N(v)}(x_{w,R}+x_{w,B})}\), with value \(0\) when the denominator is \(0\), and let \(W(x)=\sum_{v,c}x_{v,c}u_{v,c}(x)\).
A finite graph of block classes, with two population types carrying masses and rational capacity at each class. Each site in a class is adjacent to all sites in neighboring classes; allocation variables give each type's mass at each class, and the objective is total mass-weighted neighborhood utility.
The block interpretation makes every resident of an adjacent class count as a neighbor, equivalent to a complete bipartite blow-up; this is a substantive restriction on the paper's arbitrary topology model and confines the mirror to that regime.
fatal: False
It mirrors Theorem 3.3's welfare-threshold problem and Theorem 5.3's perfect-placement question in the block model. It leaves the welfare-price bounds, optimality characterizations, equilibrium dynamics, and tree-specific positivity algorithms unmirrored.
The strongest mirror is the paper’s social-welfare maximization problem. It has a natural large-population setting: a city has many households, divided into two preference groups, living in repeated housing blocks. Each block stands for many equivalent dwellings with the same neighboring blocks. A household’s utility remains its share of neighboring residents who belong to its group. This is a Schelling welfare question over a population distribution, not a continuum of outcomes or a model of dynamics.
The agent type is red or blue: within a type, residents have the same friends, enemies, and utility. Let \(G=(V,E)\) be the graph of block classes, and let \(q_v\) be the capacity of class \(v\). For each \(v\) and \(c\in\{R,B\}\), let \(x_{v,c}\) be the mass of type \(c\) assigned there. The instance gives rational capacities \(q_v\), total masses \(R,B\), and a rational threshold \(s\); feasible allocations satisfy
\[
x_{v,R}+x_{v,B}\le q_v,\qquad
\sum_v x_{v,R}=R,\qquad
\sum_v x_{v,B}=B.
\]
Define
\[
u_{v,c}(x)=
\frac{\sum_{w\in N(v)}x_{w,c}}
{\sum_{w\in N(v)}(x_{w,R}+x_{w,B})},
\]
with utility \(0\) when the denominator is \(0\), and define welfare by
\[
W(x)=\sum_{v\in V}\sum_{c\in\{R,B\}}x_{v,c}u_{v,c}(x).
\]
The continuous problem is Mass Schelling Welfare Threshold: does a feasible real allocation \(x\) with \(W(x)\ge s\) exist? The allocation is the solution. This is an exact decision question over rational input; its inequalities can be expressed as an existential formula over the reals. Complexity should be measured in \(|V|,|E|\), and the input bit length, with the agent-type support fixed at two.
My lead anchor is Theorem 3.3, proved in this paper. It says that deciding whether a Schelling instance has an assignment with social welfare at least a given rational \(s\) is NP-complete, even when the topology is regular and the number of agents equals the number of nodes. The reduction is from Maximum Clique on regular graphs. The restricted family has \(n=|V|\), capacity one per vertex, and masses \(R=k\), \(B=n-k\); its threshold is \(s=n-2k+4\binom{k}{2}/\rho\), where \(\rho\) is the graph degree.
This is a credible high-multiplicity regime: the actual population can be scaled to \(Hn\) households across these block classes, with \(Hk\) red and \(H(n-k)\) blue, while the number of complete agent types remains two. The graph records the neighborhood structure; it need not be interpreted as one unique home per person. Under the program’s heuristic, I would expect hardness to transfer (Class B): the reduction’s combinatorics lie in the topology, not in the number of individually named residents. But that is a prediction, not a consequence of Theorem 3.3. The continuous allocation permits fractional color masses, so a discrete no-instance might become a continuous yes-instance. The key follow-up is whether one can prove a rounding or gap-preservation result for this regular-graph family. If not, the continuous problem might have a different complexity.
A second, related anchor is Theorem 5.3, also proved here by reduction from Exact 3-Cover. It says that deciding whether a Schelling instance admits a perfect assignment—one in which every agent has utility \(1\)—is NP-complete. Its construction has more nodes than agents, leaving vacancies. The corresponding question in the same mass model is Perfect Mass Placement: does there exist a feasible allocation such that every positive-mass type at every vertex has utility \(1\)? Equivalently, whenever \(x_{v,c}>0\), there must be positive neighboring mass of type \(c\) and zero neighboring mass of type \(\bar c\). This models a housing authority asking whether every resident can have only same-type neighbors, when some capacity may remain vacant. I expect hardness to transfer (Class B) here as well: the hard choice appears to be which graph regions receive each type. This anchor is weaker than Theorem 3.3, since fractional placement may let tiny masses satisfy local utility conditions that the discrete reduction was designed to control. A prover should test whether the Exact 3-Cover construction survives that freedom.
These mirrors cover the paper’s global welfare optimization and its perfect-assignment feasibility result. They do not claim a continuous model of the paper’s equilibrium or relocation dynamics. The authors could plausibly recognize both as their questions: the utility formula and objective are preserved, while capacities and masses express a city whose blocks each contain many interchangeable residents.
The weakest point is the location aggregation. The mirror assumes that dwellings within one block class have identical neighborhoods, and that the graph’s adjacency represents interactions between those classes. That is a real modeling choice; it does not follow from replacing a finite set of people with a continuum. Its defense is that a block class can be a literal group of replicated dwellings in a stylized residential network, with the same friend/enemy relation and utility definition as the paper. The mirror is strongest when that repeated-neighborhood regime is the intended application.
The paper does have named computational results, so the strongest available objection is not that there is nothing to mirror. Theorem 3.3 proves NP-completeness for social-welfare threshold, and Theorem 5.3 proves NP-completeness for perfect-assignment existence. Nor can I object that agents are individuated or that the objective tracks identities: agents of the same color are interchangeable in the model.
The strongest case against both mirrors is about what must scale with the population. In the paper, every agent occupies a distinct vertex, and utility depends on the agents at adjacent vertices. Keeping the topology fixed while taking more agents therefore requires changing the one-agent-per-vertex constraint. The proposed mass allocation does so. A discrete approximation would replace each vertex by many locations and, to preserve its utility formula, connect every location in one block to every location in each adjacent block. That is a coherent block-level Schelling model, but its residents have a different neighborhood structure from residents of the paper’s graph. In a bounded-degree housing network, copying residents instead creates more distinct locations and a growing graph; it does not yield a fixed finite set of neighborhood classes.
This is a real limitation on Theorem 3.3 as a mirror: its reduction’s graph is not incidental context around a population distribution. It is the assignment space, and the hard choice is where to place each color on that graph. The block model preserves that graph as a set of classes, so it remains a plausible mirror, but it relies on the substantive assumption that residents of an adjacent block class all count as neighbors. If the authors would accept that assumption as their problem, the mirror survives. If they require the paper’s individual-vertex neighborhood semantics, the proposed finite-support limit does not preserve the model.
Theorem 5.3 inherits the same issue and adds a sensitivity to arbitrarily small masses. Its reduction uses unit agents and vacancies to encode Exact 3-Cover. In the continuous version, perfectness is a condition on the support: any positive mass at a vertex must have same-color neighboring mass and no opposite-color neighboring mass. A tiny mass can therefore represent a color’s presence at a strategically important location. That makes the discrete reduction a poor guide to the continuous question, though it does not make the support-based question meaningless or rule out a recognized continuous variant.
So the negative case is conditional, not decisive. A finite block graph with growing capacities is a genuine high-multiplicity regime, and both welfare maximization and perfect placement remain well-posed computational questions there. Their nonlinear, occupancy-dependent objectives also do not obviously expose the LP and pricing structure that motivates much of ChoCo, which weakens the claim that these are especially good targets for its optimization toolbox. But neither that mismatch nor the modeling caveat defeats the strongest block-based versions of the anchors. I cannot honestly support the universal claim that no worthwhile mirror exists in any scenario; the case against is weakest precisely for the stated repeated-block setting.
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.