| paper | d4-conf-sagt-2020-0017 |
| 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}\), already with \(\tau=1\) and \(N=2\). The restriction to \(N=2\) is \(\mathrm{NP}\text{-complete}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6.
statement extracted from the paper’s text layer
Given a connected graph \(G=(V,E)\), an integer \(N\geq 2\) with \(|V|>N\), and a rational threshold \(\xi\), does there exist a real mass allocation \((\mu_v)_{v\in V}\) with \(0\leq\mu_v\leq 1/N\) and \(\sum_{v\in V}\mu_v=1\) such that \(F_N(\mu)\geq\xi\), where \(z_v=\sum_{w\in N(v)}\mu_w\) and \(F_N(\mu)=\sum_{v\in V}\mu_v z_v/(1/N+z_v)\)?
A one-social-type population of total mass \(1\) placed on a connected location graph \(G\), with site capacity \(1/N\). The decision variables are the site masses \(\mu_v\); maximize \(F_N(\mu)=\sum_{v\in V}\mu_v z_v/(1/N+z_v)\), where \(z_v\) is neighboring mass and \(1/N\) retains the paper's self-in-the-denominator scale.
A site holding less than \(1/N\) mass still gives each resident the full \(1/N\) self baseline, and preserving sparse neighborhoods also forces \(G\) to grow with \(N\); the proponent explains the scaling choice but does not establish an atomless limit.
fatal: False
The mirror covers only Theorem 6's one-type maximum-welfare decision problem; it leaves the equilibrium existence, price-of-anarchy, and price-of-stability results unmirrored.
The strongest mirror is Continuous One-Type Schelling Welfare (C-1SW), anchored only on Theorem 6, proved in this paper. Theorem 6 says that, for a modified one-type Schelling game and rational \(\xi\), deciding whether some assignment has social welfare at least \(\xi\) is NP-complete. The paper proves membership in NP and reduces from Clique: given \((G,\lambda)\), use \(\lambda\) agents, topology \(G\), and threshold \(\lambda-1\). A \(\lambda\)-clique lets every agent have utility \((\lambda-1)/\lambda\), attaining welfare \(\lambda-1\), the maximum possible. Without such a clique, at least two agents have utility at most \((\lambda-2)/(\lambda-1)\), while every other agent gets at most \((\lambda-1)/\lambda\), so the threshold cannot be reached. This is a result about maximizing welfare over all assignments, not about finding an equilibrium.
For C-1SW, an instance is a connected location graph \(G=(V,E)\), an integer population scale \(N\geq 2\) with \(|V|>N\), and a rational threshold \(\xi\). There is one social type: all residents have the same preferences, utility rule, and options. A society is a mass allocation \(\mu_v\) over locations, with \(0\leq\mu_v\leq 1/N\) and \(\sum_{v\in V}\mu_v=1\). Write \(z_v=\sum_{w\in N(v)}\mu_w\) for the mass adjacent to \(v\), and define per-resident utility there as \(z_v/(1/N+z_v)\). The welfare to maximize is \(F_N(\mu)=\sum_{v\in V}\mu_v z_v/(1/N+z_v)\). The decision question is whether a feasible real mass allocation \(\mu\) exists with \(F_N(\mu)\geq\xi\); a solution is that allocation. Equivalently, the optimization version asks for a maximizing allocation.
The scale \(1/N\) preserves the paper’s self-in-the-denominator term. When every occupied location has mass exactly \(1/N\), \(\mu\) describes an ordinary assignment of \(N\) agents and \(F_N(\mu)\) is exactly its social welfare divided by \(N\). C-1SW therefore gives a concrete continuous relaxation of the underlying welfare problem, rather than a continuous encoding of the paper’s proof. A plausible regime is a large group of otherwise identical residents assigned to adjacent one-person sites, with many residents but only one social type. The graph may grow with \(N\); the type support remains one. The paper’s one-type setting makes this regime especially credible: its agents are already indistinguishable in the respects relevant to the model.
I expect C-1SW to be continuum-specifically hard (Class C), but with low confidence. The graph still carries the combinatorics, and the mass objective couples choices across adjacent locations through a nonlinear rational utility. That suggests a hard global optimization problem. However, Theorem 6 does not establish this: its reduction uses indivisible placements, while C-1SW allows fractional mass. The discrete assignments are feasible continuous allocations, but a discrete no-instance might gain enough from fractional placement to cross the threshold. So I would not call this a hardness transfer without a gap-preserving reduction. The main follow-up questions are whether the exact decision problem is NP-hard or \(\exists\mathbb{R}\)-hard, whether additive approximation is efficient, and how the continuous optimum compares with the discrete one—particularly whether fractional mass creates a large integrality gap.
My weakest point is the mass interpretation itself. Sites hold fractions of a normalized population, while utility retains a reference mass \(1/N\) corresponding to one resident. This is a deliberate co-scaling of site capacity and the paper’s \(+1\), and it keeps the utility meaningful in sparse neighborhoods; it is not the unique possible continuum limit. Still, the mirror preserves the paper’s location choices, adjacency-based friendship, utility shape, and welfare objective. I think the authors would recognize it as their one-type welfare-maximization problem with population mass substituted for indivisible residents. The case covers Theorem 6 only; it makes no claim about the paper’s equilibrium or price-of-anarchy results.
The strongest objection is that the proposed C-1SW is not yet a population continuum with a well-defined limit. In an atomless population, an individual contributes zero mass, so the paper’s self term \(+1\) disappears. With one type, the resulting utility is \(1\) wherever an agent has positive neighboring mass; the welfare objective no longer distinguishes a small monochromatic neighborhood from a large one, which is the feature this paper introduced its modified utility to capture.
C-1SW preserves that feature by assigning each site capacity \(1/N\) and retaining \(1/N\) in the utility denominator. But a site holding less than \(1/N\) mass is then scored as though each resident still had a full \(1/N\) self mass. That is a fractional placement relaxation with an imposed atomic scale, rather than a clear model of an atomless society. And because the paper requires \(|V|>N\), increasing the population also requires growing the location graph. Theorem 6’s arbitrary graph topology—and thus its site-specific combinatorics—remains in the problem. The proposed mirror does not show how to aggregate that structure into a stable continuous population model.
A graph-limit story could make a better candidate: residents on a repeated family of local topologies, for example. But a dense limit risks washing out the self term; a sparse limit retains local, vertex-level structure and needs a separate account of how the growing graph is represented. Restricting to repeated motifs may produce a sensible new question, but it does not establish that the arbitrary-topology welfare problem in Theorem 6 has a natural continuous mirror.
This weakens the claim that C-1SW is already a strong ChoCo mirror. It does not defeat every version of the idea. Theorem 6 is a genuine computational result, all agents are interchangeable, and a location-mass relaxation is mathematically coherent enough to investigate. I cannot honestly argue that no plausible scenario exists; the negative case is strongest against the proposed mirror’s population interpretation, and the anchor remains a real candidate if the authors accept fractional occupancy with a finite self-mass scale.
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.