| paper | Schelling Games on Graphs |
| authors | Aishwarya Agarwal, Edith Elkind, Jiarui Gan, Ayumi Igarashi, Warut Suksompong, A. Voudouris |
| venue | IJCAI 2019 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard, even when \(m=3\), \(G=K_3\), and \(\sigma=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6.2
statement extracted from the paper’s text layer
Given a finite role-type set \(\Theta\), rational mass distribution \(\mu\in\mathbb{Q}_{\ge0}^{\Theta}\) with \(\sum_{\theta}\mu_\theta=1\), binary friendship matrix \(W_{\theta,\theta'}\), finite undirected topology \(G=(V,E)\), rational capacities \(b_v\), and threshold \(\sigma\), decide whether there exists \(x_{\theta,v}\ge0\) satisfying \(\sum_v x_{\theta,v}=\mu_\theta\) and \(\sum_\theta x_{\theta,v}\le b_v\), with total welfare \(\sum_{\theta,v}x_{\theta,v}u_{\theta,v}(x)\ge\sigma\), where \(u_{\theta,v}(x)\) is the neighboring friend-mass fraction.
A high-multiplicity social-Schelling welfare model in which finitely many complete social-role types \(\Theta\) carry mass \(\mu\), type mass \(x_{\theta,v}\) is assigned to capacitated graph locations, and welfare is total type mass weighted by its neighboring friend-mass fraction.
The opponent correctly leaves unresolved whether block-constant repeated roles and fractional placement preserve the reduction: the proponent acknowledges this need but supplies no purification or gap lemma.
fatal: False
It mirrors Theorem 6.2's NP-complete social-welfare threshold result; it leaves the equilibrium-existence, XP, potential-function, price-of-anarchy, and price-of-stability results unaddressed.
My strongest case is a single mirror anchored in Theorem 6.2.
Theorem 6.2, proved in this paper, states that given a social Schelling game \(I\) and a rational threshold \(s\), deciding whether \(I\) has an assignment with social welfare at least \(s\) is NP-complete. The hardness holds even when every agent is strategic and the topology \(G\) has maximum degree \(2\). The reduction is from Hamiltonian Cycle: for every vertex \(v\) of an input graph \(H\), the construction creates an agent \(p_v\), whose friends are precisely the agents corresponding to neighbours of \(v\) in \(H\). The topology is a cycle on \(|V(H)|\) locations plus one isolated location. Social welfare \(|V(H)|\) is achievable exactly when the agents can be arranged around the cycle so that each agent has two friends adjacent to it, which is exactly a Hamiltonian cycle in \(H\).
This is my lead anchor because it avoids the weakest feature of the paper’s typed reductions: stubborn agents with individually prescribed locations. It is also a genuine welfare-optimization result, rather than merely an equilibrium-existence statement.
The continuous mirror is the following.
A finite set \(\Theta\) consists of social-role types. A type \(\theta\) includes the complete social information relevant to the model: its friendship profile \(W_{\theta,\theta'}\in\{0,1\}\), where \(W_{\theta,\theta'}=1\) means that a member of type \(\theta\) regards a member of type \(\theta'\) as a friend. The population is a rational mass distribution \(\mu\in\mathbb{Q}_{\ge 0}^{\Theta}\) with \(\sum_{\theta}\mu_\theta=1\).
The topology is a finite undirected graph \(G=(V,E)\), with a rational capacity \(b_v\) for each location \(v\). The capacities represent scalable residential cells: each cell may contain a mass of residents, and adjacency between cells defines whose neighbourhoods interact. A mass assignment is a matrix \(x=(x_{\theta,v})\) satisfying
\[ \sum_{v\in V}x_{\theta,v}=\mu_\theta \]
for every type \(\theta\), and
\[ \sum_{\theta\in\Theta}x_{\theta,v}\le b_v \]
for every location \(v\). Thus \(x_{\theta,v}\) is the mass of type \(\theta\) placed at \(v\); individual agents still receive an integral location, but a population type may be distributed across several locations.
Let
\[ q_v=\sum_{\theta}x_{\theta,v} \]
be the mass at \(v\), and let
\[ D_v(x)=\sum_{w\in N(v)}q_w \]
be the total neighbouring mass. The utility of type \(\theta\) at \(v\) is
\[ u_{\theta,v}(x)= \begin{cases} \dfrac{\sum_{w\in N(v)}\sum_{\theta'}W_{\theta,\theta'}x_{\theta',w}} {D_v(x)}, & D_v(x)>0,\\[1.2ex] 0, & D_v(x)=0. \end{cases} \]
The continuous welfare is
\[ \operatorname{SW}_\infty(x) = \sum_{\theta\in\Theta}\sum_{v\in V} x_{\theta,v}u_{\theta,v}(x). \]
The problem is:
Continuous Social-Schelling Welfare Threshold. Given \((\Theta,\mu,W,G,b,\sigma)\), decide whether there exists a feasible mass assignment \(x\) with
\[ \operatorname{SW}_\infty(x)\ge \sigma. \]
A solution is the mass-assignment matrix \(x\), not a fractional outcome or lottery.
The intended regime is a large metropolitan population containing many copies of each of finitely many social roles: for example, thousands of residents per occupational, linguistic, or community role, with members of a role indistinguishable with respect to the friendship relation and the residential model. The number of agents \(N\) is therefore much larger than \(|\Theta|\). Residential capacities scale with population size, while the topology remains a discrete interaction structure. This is a genuine population continuization: the graph of locations and the friendship relation remain discrete; only the society becomes a distribution of mass over repeated types.
I expect this problem to belong to Class B: hardness should transfer. The obstruction in Theorem 6.2 is not primarily the identity of individual agents. It lies in the combinatorial interaction between the social-compatibility graph \(H\) and the cyclic ordering of locations. Replacing \(q\) copies of every role by mass should not automatically remove that ordering problem. A likely proof route is a purification or gap lemma showing that a solution above a suitable threshold can be converted into an essentially integral cyclic arrangement. If such a lemma holds, the Hamiltonian-Cycle reduction survives directly in the high-multiplicity setting.
The mirror is not claiming that Theorem 6.2 itself proves this continuous hardness result. It supplies the precise discrete problem whose high-multiplicity analogue should now be classified. The most interesting follow-up is whether the continuous problem is genuinely Class B, or whether fractional mixing turns the Hamiltonian-cycle obstruction into a tractable fractional cycle-cover problem. Other natural questions are the complexity for paths and cycles, fixed \(|\Theta|\), approximation algorithms, and quantitative rounding from a continuous solution to a large finite population.
The weakest point is that Theorem 6.2’s reduction gives every paper-agent a potentially unique social neighbourhood. In an arbitrary instance, the number of complete types may therefore grow with the population, weakening the high-multiplicity interpretation. The proposed mirror needs a role-repeated scenario in which many agents share each social profile, and its hardness needs a separate argument against advantageous fractional mixing. That is a real technical vulnerability. It does not, however, make the mirror artificial: the paper’s social-network model already defines welfare through friendship profiles and locations, and a dense population of repeated social roles is a credible application of exactly that model.
The strongest negative case is a typing collision in Theorem 6.2. Its reduction encodes an arbitrary graph \(H\) directly into the agents’ identities: agent \(p_v\)’s friends are exactly the agents corresponding to neighbours of \(v\). For a generic \(H\), these friendship profiles are distinct. Since a continuous type must contain every feature relevant to utility, preserving the original social-network model forces each such profile to remain a separate type. Then \(\tau\) grows with the number of agents, and the proposed “continuum” has not compressed the population in the relevant sense.
If instead we create \(r\) copies of each \(p_v\), we must choose how their friendships lift. Pairing copies preserves identity-specific relationships and again prevents type aggregation. Making every copy of \(v\) friends with every copy of \(u\) whenever \(\{u,v\}\in E(H)\) produces a blow-up of \(H\), but that is a new role-interaction model, not the social-network instance used in Theorem 6.2. The Hamiltonian-cycle reduction applies to one representative of each role; it does not automatically survive this change.
The proposed capacity formulation also changes the object carrying the theorem. In the paper, every agent occupies one distinct location, and welfare is generated by a cyclic ordering of named agents. In the mirror, a type may be split across many cells and cells may contain mixtures. If mixing is forbidden, one has essentially restored the original integral ordering and gained no meaningful continuization. If mixing is allowed, the question becomes a new fractional allocation problem over role masses. That may be interesting, but it is not yet a mirror justified by the theorem; it requires a separate model and a separate discrete-to-continuous dictionary.
This objection is strongest against the specific anchor as presented, but it does not defeat the best possible rescue. One can posit a credible society with many copies of each social role, define a block-constant friendship matrix \(W_{\theta,\theta'}\), scale residential capacities, and study the resulting fractional welfare problem. The programme explicitly allows \(\tau\) to be an input parameter, so \(\tau\) growing with the number of roles is not by itself disqualifying. Likewise, Theorem 4.2 offers an even cleaner rescue: all strategic agents already have one type, while the hard graph appears in the topology.
Thus I cannot honestly claim that no worthwhile mirror exists. The proponent has identified a genuine high-multiplicity research question; the missing purification or rounding theorem is a research obligation, not an objection. The defensible negative verdict is only that the proposed mirror has not yet shown itself to be a faithful continuization of Theorem 6.2. Under the programme’s rules, that is insufficient to defeat the anchor.
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.