| paper | Schelling Games with Continuous Types |
| authors | Davide Bilò, Vittorio Bilò, Michelle Döring, Pascal Lenzner, Louise Molitor, Jonas Schmidt |
| venue | IJCAI 2023 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given a connected graph \(G=(V,E)\), rational block capacities \(b_v>0\), a finite ordered type set \(T\) with rational values \(\theta_t\in[0,1]\), and rational masses \(\mu_t\ge0\) satisfying \(\sum_t\mu_t=\sum_v b_v\), find a matrix \(\rho\in\mathbb{Q}_{\ge0}^{V\times T}\) with \(\sum_t\rho_{v,t}=b_v\) and \(\sum_v\rho_{v,t}=\mu_t\) such that no exchange of any \(0<\varepsilon\le\min\{\rho_{v,t},\rho_{w,s}\}\) between blocks \(v,w\) and types \(t,s\) strictly lowers both participants' costs. Here \(D_t(v;\rho)=\max\{|\theta_t-\theta_r|:\exists u\in N(v),\rho_{u,r}>0\}\), with both post-exchange costs evaluated in the resulting arrangement \(\rho'\).
A finite set of anonymous cohort types with values \(\theta_t\), distributed as mass \(\mu_t\) across capacitated graph blocks through decision variables \(\rho_{v,t}\). The objective is to find a stable arrangement under bilateral positive-mass swaps, with maximum neighboring type-distance as the cost; continuity lies in population mass, not merely in the type values.
The block blow-up changes one-agent-per-vertex neighborhoods, and positive-mass exchanges are cohort deviations; the two-block example shows that the paper's BFS proof does not transfer.
fatal: False
The mirror targets Theorem 1's S-MDG equilibrium-computation result and motivates the proposed Theorem 6 jump analogue; it leaves the other equilibrium results, FIP propositions, PoA/PoS bounds, simulations, and Conjecture 1 alone.
The strongest positive case is a single Class-A mirror anchored by Theorem 1, which is proved in this paper: “A SE for the S-MDG can be computed in \(O(|E|)\).” The paper’s real-valued types are not themselves population continuization: it still has \(n\) named agents and one agent per vertex. But its strategic interaction depends only on type value and local graph position, with no identity, history, or agent-specific parameter. That makes it unusually suitable for a high-multiplicity extension.
The plausible regime is a city represented by a fixed connected graph of residential blocks. Each block contains many interchangeable apartments, and residents fall into finitely many complete types \(T=\{\theta_1,\ldots,\theta_\tau\}\), where \(\theta_t\in[0,1]\) might represent an income or ideological band. The population is given by rational masses \(\mu_t\), with \(\sum_t\mu_t=1\), and \(\tau\ll N\). Population and residential capacity scale together: at scale \(q\), every macro-vertex \(v\) is replaced by \(q b_v\) interchangeable micro-locations, and \(q\mu_t\) is the mass of type \(t\). For an edge \(\{v,w\}\), every apartment in \(v\) is adjacent to every apartment in \(w\). This is the natural repeated-block version of the paper’s graph model, not merely a weighted objective.
My lead problem is Mass Swap-MDG Equilibrium, denoted \(\mathsf{S\mbox{-}MDG}_\infty\).
An instance consists of a connected graph \(G=(V,E)\), rational block capacities \(b_v>0\), a finite ordered type set \(T\), rational type masses \(\mu_t\ge 0\) satisfying \(\sum_t\mu_t=\sum_v b_v\), and the type-distance function \(d(t,s)=|\theta_t-\theta_s|\).
A feasible population arrangement is a mass matrix \(\rho=(\rho_{v,t})\), where \(\rho_{v,t}\ge0\), \(\sum_t\rho_{v,t}=b_v\), and \(\sum_v\rho_{v,t}=\mu_t\). Thus \(\rho_{v,t}\) is the mass of type \(t\) living in block \(v\). For a type-\(t\) resident in \(v\), define \(D_t(v;\rho)\) as the maximum value of \(d(t,s)\) over all types \(s\) having positive mass in a neighboring block of \(v\). The social cost, if desired, is \(\mathrm{SC}(\rho)=\sum_{v,t}\rho_{v,t}D_t(v;\rho)\), but the computational objective is to find a stable arrangement, not to minimize social cost.
A mass swap chooses \(v\ne w\), types \(t,s\), and \(\varepsilon>0\) with \(\varepsilon\le\rho_{v,t}\) and \(\varepsilon\le\rho_{w,s}\), and exchanges \(\varepsilon\) mass of type \(t\) at \(v\) with \(\varepsilon\) mass of type \(s\) at \(w\). The swap is profitable if, in the resulting arrangement \(\rho'\), \(D_t(w;\rho')<D_t(v;\rho)\) and \(D_s(v;\rho')<D_s(w;\rho)\). The problem asks for any feasible \(\rho\) admitting no profitable mass swap.
This is recognisably the paper’s S-MDG: the cost is still maximum neighboring type-distance, the action is still a swap, and the solution is still a swap equilibrium. The only extension is that interchangeable clones are represented by mass. For rational data, clearing denominators gives a finite repeated-agent instance; conversely, the aggregate of any such clone instance gives a feasible \(\rho\). The block capacities are essential: population and locations grow together, so the model does not put arbitrarily many residents into a fixed one-agent vertex.
I expect this problem to be Class A. The natural candidate is the paper’s BFS construction. Let \(v_1,\ldots,v_{|V|}\) be the BFS order used in the proof of Theorem 1, and let \(Q_\mu\) be the nondecreasing type-quantile function whose level \(\theta_t\) occupies mass \(\mu_t\). Assign consecutive quantile intervals to the BFS-ordered blocks, setting \(\rho_{v_i,t}\) equal to the amount of type-\(t\) quantile mass assigned to \(v_i\). The proof of Theorem 1 is based on monotonicity of leftmost neighbors and on the fact that an agent’s maximum cost is determined by extreme neighboring types. Those arguments appear to lift from agent indices to quantile positions. The expected algorithm would therefore run in time polynomial in \(|V|\), \(|E|\), \(\tau\), and the encoding length \(L\), without expanding the denominator of \(\mu\).
The remaining theorem to prove is precisely the continuous analogue of the BFS lemma: fractional blocks may contain two adjacent pieces of the quantile order, and one must show that no positive mass exchange between such pieces creates a profitable swap. That is a real proof obligation, but it is structural and local rather than a change to the authors’ question.
A good secondary anchor is Theorem 6, also proved here: “A JE for both the J-HIS-ADG and J-HIS-CG on paths can be computed in \(O(n\log n)\) time.” The corresponding problem, \(\mathsf{J\mbox{-}HIS\mbox{-}ADG}_\infty\), uses a path \(P\), capacities \(b_v\), type masses \(\mu_t\) with \(\sum_t\mu_t\le\sum_vb_v\), and a mass arrangement \(\rho\) with vacancies \(z_v=b_v-\sum_t\rho_{v,t}\). A type-\(t\) mass \(\varepsilon\) may jump from \(v\) to \(w\) whenever \(\varepsilon\le\rho_{v,t}\) and \(\varepsilon\le z_w\). Its cost is \(0\) when it has no occupied neighbors, preserving the paper’s HIS convention; otherwise it is \(A_t(v;\rho)=\frac{\sum_s q_{v,s}|\theta_t-\theta_s|}{\sum_s q_{v,s}}\), where \(q_{v,s}\) is neighboring type-\(s\) mass. The question is to output an arrangement with no profitable positive-mass jump.
Here the paper’s sorted-agent construction has an especially direct interpretation: arrange type mass monotonically along the path and place vacancy mass at the largest gaps in the type quantile function. I again expect Class A, with a compact algorithm depending on \(\tau\), the path size, and \(L\), rather than on the number of cloned residents. This mirrors Theorem 6’s actual path, jump, HIS, and average-distance semantics. I would not extend the claim to UIS games, unrestricted graphs, or the paper’s welfare bounds without separate proofs.
My weakest point is the deviation semantics. A literal atomless individual has zero effect on the surrounding mass distribution, so unilateral deviations can become vacuous, especially for the maximum-distance cost. I therefore define deviations as positive-\(\varepsilon\) exchanges or jumps of a homogeneous cohort. That is an extension, not a purely formal replacement. The defence is that it is exactly the limit of swaps or jumps among repeated clones, and this paper has no identity-dependent incentive, history, or endpoint structure that aggregation destroys. If a referee insists on one agent per original vertex with no repeated residential blocks, the proposal should be downgraded from a direct mirror to an author-recognisable capacitated extension. The core positive case nevertheless survives: the paper supplies a named polynomial equilibrium algorithm whose ordering argument is naturally expressed in terms of a population quantile distribution.
The negative case is strongest against the claim that Theorem 1 lifts directly. In the paper, \(n=|V|\): every location contains exactly one agent, and a swap is a permutation of the vertices. There is therefore no population-multiplicity parameter independent of the topology. To create many copies of each type, one must either allow several agents per vertex or replace every vertex by a block of vertices. Both choices change the game.
The proponent’s complete-bipartite block construction is a plausible new model, but it is not a rational-clone preservation of the paper’s model. It changes a bounded-degree graph game into a capacitated population game in which a resident sees the entire mass of every neighboring block. The BFS proof relies on one agent occupying each vertex and on the ordering of individual neighbors. That ordering does not survive fractional occupancy within a block.
There is a concrete failure even for the proposed S-MDG. Take two adjacent blocks, each of capacity \(3\), and assign the sorted types
\[ (0,0.2,0.25) \]
to the first block and
\[ (0.75,0.85,1) \]
to the second. This is exactly the proposed BFS/quantile arrangement. The agent of type \(0.2\) has cost \(0.8\), while the agent of type \(0.75\) has cost \(0.75\). Swapping them gives block contents
\[ (0,0.75,0.25) \quad\text{and}\quad (0.2,0.85,1), \]
after which both agents have cost \(0.55\). Thus the claimed structural lift is false even in a finite clone instance of the block model.
The deviation semantics also change. A paper swap exchanges two individual agents. The proposed continuum permits an arbitrary positive mass \(\varepsilon\) to exchange. If arbitrary \(\varepsilon\) is allowed, this is a cohort or coalition deviation absent from the paper. If only the finite clone quantum is allowed, the model must retain a hidden denominator and is no longer genuinely atomless. For MDG specifically, infinitesimal exchanges are often invisible until they remove the last positive mass of a type from a neighboring block, so the limiting game has discontinuous support effects rather than the paper’s ordinary permutation semantics.
The alternative of preserving one agent per vertex does not rescue the mirror. A \(q\)-fold graph blow-up must either use complete-bipartite twin blocks, which gives the altered game above, or give the copies different neighborhoods. In the latter case the copy or spatial position becomes part of the complete type, so aggregating by ordinary type loses information. Disconnected copies merely produce \(q\) independent repetitions of the original game and provide no meaningful population object.
Theorem 6 has the same problem, more sharply because vacancies are strategic objects. In the proposed capacitated path, let two adjacent blocks each have capacity \(2\). Put two agents of type \(0.05\) in the first block, one agent of type \(1\) in the second, and leave one unit of vacancy in the second. This is the proposed sorted arrangement with vacancy placed at the largest type gap. A type-\(0.05\) agent in the first block has ADG cost \(0.95\). Jumping into the vacancy in the second block gives it two neighboring agents of type \(0.05\), hence cost \(0\). The arrangement is therefore not a J-HIS-ADG equilibrium. The paper’s proof works because an empty *vertex* lies between two consecutive agents; a vacancy inside a capacitated block has entirely different neighbors.
One can restore the original Theorem 6 by expanding the path into microscopic vertices and putting vacancies on those vertices. But then the theorem is simply being applied to the expanded finite path. Any compact mass formulation must either change the neighborhood semantics, as above, or retain enough spatial detail to eliminate the benefit of type aggregation.
This is a substantial case against treating either theorem as an established continuous mirror: the natural population scaling is an extension to capacitated block games, while the exact clone-preserving scaling retains the paper’s microscopic spatial structure. The proposed constructions therefore do not yet identify a worthwhile ChoCo problem; they identify two new spatial population games whose relation to the paper remains to be proved.
The universal negative is nevertheless not airtight. The paper is unusually amenable to an author-recognisable extension: types are anonymous, and there is no identity- or history-dependent payoff. A carefully defined block-population Schelling game could itself be worthwhile. What the objections defeat is the proponent’s direct Class-A case and both claimed theorem lifts—not every conceivable continuous reinterpretation.
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.