| paper | Equilibria in Schelling Games: Computational Hardness and Robustness |
| authors | — |
| venue | AAMAS 2022 |
| filed under | coalition · hedonic |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.1
statement extracted from the paper’s text layer
Given a connected graph \(G=(V,E)\), rational capacities \(b_v>0\) with \(\sum_{v\in V}b_v=1\), and a two-type population distribution \(\mu=(\mu_1,\mu_2)\), decide whether there exists a mass assignment \(x_{\ell v}\ge0\) satisfying \(\sum_{\ell=1}^2x_{\ell v}=b_v\) and \(\sum_{v\in V}x_{\ell v}=\mu_\ell\), such that no pair of infinitesimal households of distinct types has a mutually profitable swap. Here \(u_\ell(v;x)=0\) when the neighbourhood has zero mass, and otherwise \(u_\ell(v;x)=\frac{\sum_{w\in N(v)}x_{\ell w}}{\sum_{k=1}^2\sum_{w\in N(v)}x_{kw}}\); a swap from \(u\) and \(v\) is profitable exactly when \(x_{\ell u}x_{kv}>0\), \(\ell\ne k\), and \(u_\ell(v;x)>u_\ell(u;x)\) and \(u_k(u;x)>u_k(v;x)\).
A repeated-cell Schelling game on finite \(G\), with agent types \(\{1,2\}\), population masses \(\mu\), cell masses \(x_{\ell v}\), anonymous same-type-neighbour utility, and feasibility as the decision objective; the proportional assignment \(x_{\ell v}=\mu_\ell b_v\) is an explicit Class A witness.
The mirror replaces unit-capacity sites and bilateral finite-agent deviations by repeated capacitated cells and nonatomic deviations, so it is not a canonical high-multiplicity relaxation of arbitrary \(S\)-Eq instances.
fatal: False
The mirror covers Theorem 3.1's \(S\)-Eq existence problem and the parallel jump problem of Theorem 3.5 in repeated-cell populations; it leaves the robustness theorems and graph-class bounds untreated.
My strongest positive case is narrow but genuine: the paper’s two NP-completeness results admit a natural high-multiplicity population mirror in which the hardness disappears completely. The lead anchor is Theorem 3.1, proved by the authors here: \(S\)-Eq is NP-complete. The secondary anchor is Theorem 3.5, also the authors’ result, with the proof supplied in the full version: \(J\)-Eq is NP-complete.
The regime is a large residential population divided into two genuinely interchangeable types, \(T_1\) and \(T_2\). A finite graph \(G=(V,E)\) describes neighbourhood cells rather than individual homes. Cell \(v\) contains many interchangeable housing units, all having the same neighbourhood relation: units in \(v\) see the units in cells adjacent to \(v\). The number of households \(N\) is very large, while the number of behavioural types is \(\tau=2\), and the number of distinct neighbourhood cells is much smaller than \(N\). This is a plausible high-multiplicity regime for apartment blocks, repeated housing developments, or coarse-grained social-network communities.
The mirror does not make the graph continuous. It keeps \(G\) as a finite combinatorial object and continuizes only the population occupying its repeated cells.
For Theorem 3.1, I would call the continuous problem \(\mathrm{CS\text{-}Eq}_\infty\). An instance consists of a connected graph \(G=(V,E)\), rational cell capacities \(b_v>0\) with \(\sum_v b_v=1\), and rational population masses \(\mu_1,\mu_2\ge 0\) with \(\mu_1+\mu_2=1\). A solution is a mass assignment \(x_{\ell v}\ge0\), where \(x_{\ell v}\) is the mass of type \(\ell\) placed in cell \(v\), satisfying \(\sum_\ell x_{\ell v}=b_v\) and \(\sum_v x_{\ell v}=\mu_\ell\).
Write \(z_v=\sum_\ell x_{\ell v}\), \(z(N(v))=\sum_{w\in N(v)}z_w\), and \(x_\ell(N(v))=\sum_{w\in N(v)}x_{\ell w}\). The utility of an infinitesimal type-\(\ell\) household at \(v\) is \(u_\ell(v;x)=0\) when \(z(N(v))=0\), and otherwise \(u_\ell(v;x)=x_\ell(N(v))/z(N(v))\). A pair of infinitesimal households, type \(\ell\) at \(u\) and type \(k\ne\ell\) at \(v\), is a profitable swap if both have positive mass and \(u_\ell(v;x)>u_\ell(u;x)\) and \(u_k(u;x)>u_k(v;x)\). The question is whether a mass assignment with no such pair exists; a solution is the assignment \(x\) itself.
This is recognisably the authors’ problem. Agents still choose locations, utility is still exactly the fraction of same-type neighbours, swaps are still the only deviations, and there are still no stubborn agents or location-specific preferences. The only change is that a cell represents many interchangeable copies of a position. For rational \(b_v\) and \(\mu_\ell\), clearing denominators gives a finite blow-up with many actual vertices and agents, so this is a genuine high-multiplicity interpretation rather than merely a probabilistic profile.
The continuous problem is Class A, in fact for a very simple reason. Set \(x_{\ell v}=\mu_\ell b_v\) for every \(\ell\) and \(v\). Every neighbourhood then has exactly the same type proportions as the whole population, so \(u_\ell(v;x)=\mu_\ell\) at every non-isolated cell. No swap can strictly improve either participant. Thus \(\mathrm{CS\text{-}Eq}_\infty\) is always feasible and has an explicit rational witness.
This gives a clean interpretation of what dissolves the discrete hardness in Theorem 3.1: the reduction forces indivisible agents into type-pure gadget positions. Once a neighbourhood cell contains a large population of interchangeable units, proportional mixing eliminates the integral colouring obstruction. The topology has not been erased; it is still present in every neighbourhood calculation. What disappears is the one-agent-per-vertex granularity.
The jump result has a parallel but distinct mirror, \(\mathrm{CJ\text{-}Eq}_\infty\), corresponding to Theorem 3.5. Here capacities satisfy \(\sum_v b_v=B>1\), while total population mass remains \(1\), so there is a positive vacancy fraction. An assignment satisfies \(\sum_\ell x_{\ell v}\le b_v\) and the same type-mass constraints. A type-\(\ell\) household at \(u\) may jump to any cell \(v\) with residual capacity \(b_v-\sum_\ell x_{\ell v}>0\). The assignment is a continuous jump-equilibrium if \(u_\ell(u;x)\ge u_\ell(v;x)\) for every occupied source and every cell with a vacant slot.
Again take \(\rho=1/B\) and set \(x_{\ell v}=\mu_\ell\rho b_v\). Every cell is partially occupied, every cell has the same type proportions, and every type-\(\ell\) household has utility \(\mu_\ell\) wherever it goes. Therefore no jump is profitable. The continuous analogue of the paper’s NP-complete \(J\)-Eq problem is also Class A.
The weakest point is clear: the mirror permits a neighbourhood cell to contain a mixture of types. If the authors regard every vertex in their model as an indivisible, unique location whose purity cannot be relaxed, they may reject this as a capacitated block model rather than a literal limit of their game. I think that objection is serious, but not fatal. The paper’s utility function is explicitly aggregate and anonymous, and repeated housing units with identical neighbourhood structure are a credible high-multiplicity scenario. The mirror should not be advertised as covering every finite Schelling instance; it covers the repeated-cell regime.
The natural follow-up questions are whether hardness returns when cells must be type-pure, when a minimum granularity is imposed, or when deviations must involve a positive mass rather than one infinitesimal household. One could also study continuous robustness under deletion of a positive mass of households, heterogeneous tolerance types, stubborn subpopulations, or vertex-specific preferences. Those variants may produce Class B or Class C behaviour. But for the simplest no-stubborn-agent model proved hard in Theorems 3.1 and 3.5, this is a precise, author-recognisable population mirror, and it gives a particularly clean Class A example of discrete equilibrium-existence hardness dissolving under high multiplicity.
The strongest objection is that the proposed mirror is not really a continuization of the paper’s game. It replaces the paper’s unit-capacity vertices by divisible bins. In the paper, an assignment is a bijection between agents and vertices, and \(u_i(v_i\leftrightarrow j)\) is evaluated after the two agents exchange their actual vertices. The proposed \(x_{\ell v}\) permits both types to occupy one “cell” and evaluates an infinitesimal mover against the unchanged aggregate state. That is a nonatomic capacitated Schelling game, not the game in Theorems 3.1 and 3.5.
Clearing denominators does not remove this change. It constructs a very special graph blow-up: every cell \(v\) is replaced by many vertices, with complete bipartite connections between cells corresponding to edges of \(G\). The quotient graph is therefore an additional repeated-neighbourhood promise. A different blow-up—matching copies, independent copies, or a graph with merely similar rather than identical neighbourhoods—gives a different game. The paper’s NP-complete problems are over arbitrary connected topologies, not over such quotientable topologies. Thus Theorem 3.1 has not been continuized in general; a restricted family of graph blow-ups has been introduced.
The proportional assignment also exposes the deeper problem. In that new model, every cell has the same type proportions, so the existence question is identically affirmative. The topology, the gadget structure, and the strategic interaction have disappeared from the predicate. This is not merely that the answer happens to be easy: the integral object whose existence Theorem 3.1 studies—a type assignment to unit-capacity sites—has been removed. Enforcing type-pure cells restores that object, but then \(x_{\ell v}\) is integral and the continuum has vanished.
The same objection defeats the proposed mirror of Theorem 3.5. A free vertex in the paper is a discrete target, whereas residual capacity in every cell is a new fractional-vacancy model. If agents remain indivisible, one has returned to the original jump game on a particular blow-up. If agents are infinitesimal, a jump has no aggregate effect, and the proportional state is automatically stable. Defining deviations as transfers of a positive mass could produce an interesting coalition or mass-exchange game, but that introduces a new deviation parameter and is no longer the paper’s jump-equilibrium problem.
A more faithful repair is therefore caught between two failures. With atomless deviations, the externality created by moving one agent disappears. With positive-mass deviations, one has added collective deviations absent from the paper. With type-pure sites, one has retained the discrete problem. Adding location-specific preferences, stubborn agents, or heterogeneous utilities might restore nontriviality, but those are new Schelling games rather than mirrors of the two named theorems.
The robustness results offer no clean escape. Vertex robustness counts deleted individual sites; after a \(q\)-fold blow-up, one site has mass \(1/q\), while deleting an entire cell is a topology modification. Normalizing by population makes single-site robustness collapse toward zero; keeping the original count makes it diverge with the arbitrary refinement factor. A positive-mass deletion notion could be studied, but it would not be inherited canonically from the paper.
This negative case is ultimately not airtight. The apartment-block interpretation is plausible, and the proportional assignment is a genuine equilibrium of the corresponding finite blow-up instances. If the programme admits such repeated-cell topology promises as legitimate high-multiplicity regimes, then the proponent has a real Class A mirror of both Theorem 3.1 and Theorem 3.5. The honest conclusion is therefore that the anti-case can show the proposed mirror is degenerate and model-changing, but it cannot establish the universal claim that no worthwhile continuous scenario exists.
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.