| paper | d4-conf-sagt-2023-0012 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | unclear |
Theorem 3.1 is a computational hardness result, and the proposed district model is a plausible related variant. But scaling vertex capacities and replacing individual jumps with infinitesimal deviations changes the equilibrium concept to a nonatomic or Wardrop one. That leaves no surviving continuous analogue of the anchored result.
fails bit b-changes — the continuum limit changes the question
The proposed model changes unit vacancies and individual jumps into macroscopic district capacity and infinitesimal deviations, changing the equilibrium concept.
fatal: True
The proposal targets only Theorem 3.1; it does not mirror the tree existence, potential-game, or welfare results.
The strongest case is a single anchor: Lead — Mass Diversity-Jump Equilibrium Existence, mirroring Theorem 3.1.
Theorem 3.1, proved in this paper, states that for every \(k\ge2\), deciding whether a diversity-seeking jump game \(I=(R,S,T,G,\lambda)\) has a pure Nash equilibrium is NP-complete. The hardness construction already uses two agent types and includes stubborn agents; membership in NP follows by checking a proposed assignment. This is the paper’s direct computational anchor. I would mirror its equilibrium-existence question, not its Independent Set reduction as though that reduction automatically survived the continuum.
A plausible regime is a city with many residents spread across a modest number of housing districts. A vertex represents a district, and an edge means that residents in the two districts count one another as neighbors. Residents have one of \(k\) diversity-seeking types. Some are mobile; others are fixed in place, as with entrenched residents. Within each type and mobility class, residents have the same preferences and constraints. A fixed cohort’s type also records its pinned district. Thus the number of residents can greatly exceed the number of supported types, even though the number of pinned cohorts may grow with the number of districts. District capacities scale with the population. This is a high-multiplicity regime, with the explicit modeling choice that residents in adjacent districts mix at the district level.
Here is the continuous problem. The input is a finite graph \(G=(V,E)\), rational district capacities \(q_v\), rational stubborn masses \(p_{v,c}\) of each type \(c\) pinned at each vertex, and rational supplies \(\sigma_c\) of mobile mass by type. Normalize total population mass to one, require \(\sum_v q_v>1\), and give all rational data in binary. A solution is a real allocation \(x_{v,c}\ge0\) of mobile mass satisfying
\[
\sum_v x_{v,c}=\sigma_c,\qquad
\sum_c\bigl(p_{v,c}+x_{v,c}\bigr)\le q_v.
\]
Write \(\rho_{v,c}=p_{v,c}+x_{v,c}\) and \(h_v=q_v-\sum_c\rho_{v,c}\). The utility for a mobile resident of type \(c\) at district \(v\) is
\[
u_c(v;x)=
\frac{\sum_{w\in N(v)}\sum_{d\ne c}\rho_{w,d}}
{\sum_{w\in N(v)}\sum_d\rho_{w,d}},
\]
with utility \(0\) when the denominator is zero. The question is whether there is a feasible allocation \(x\) such that, whenever \(x_{v,c}>0\), \(u_c(v;x)\ge u_c(w;x)\) for every district \(w\) with \(h_w>0\). In other words, no infinitesimal amount of mobile mass can jump to a district with spare capacity and improve its utility. The decision problem is existence over the reals; an equilibrium allocation is the solution. Its natural size parameters are \(|V|\), the number \(\tau\) of supported cohorts, and the bit length \(L\). The utility comparisons are finite-dimensional real constraints, with separate cases for zero neighboring mass and zero spare capacity.
The authors would, I think, recognize this as a continuous-population version of their problem: agents still occupy locations on a graph, seek a higher fraction of different-type neighbors, and can move only where capacity is available; fixed residents still constrain the game. The anchor concerns equilibrium existence, and this mirror asks the same question. The paper’s cited continuous-type variant [7] is adjacent but distinct: it makes the types continuous, whereas this proposal makes the population continuous.
My tentative expectation is Class A, with low confidence: splitting cohorts into mass may make the existence question tractable even where indivisible placements are hard. The Independent Set combinatorics in Theorem 3.1 is tied to which whole strategic agents occupy which vertices. Fractional allocation may defeat that encoding. The useful next questions are whether mass equilibria always exist, whether one can find one in time polynomial in \(|V|,\tau,L\), and whether a finite-population approximation preserves equilibria.
The soft spot is substantial: this is a district-level mean-field model, not a literal limit of the paper’s one-agent-per-vertex instances. It changes both vertex capacity and unilateral deviations. In particular, Theorem 3.1’s NP-hardness does not establish hardness here; the fractional model may admit equilibria in instances where the discrete construction has none. So this is a credible mirror of the paper’s central computational question, but its complexity is an open target, not a transferred result. The proposed scope is only Theorem 3.1’s equilibrium-existence problem; it does not claim to continuize the paper’s tree, potential-game, or welfare results.
Theorem 3.1 is the paper’s strongest anchor, and the best objection is that its hardness lives in a unit-capacity, atom-by-atom model. Every stubborn agent is pinned to a distinct vertex, and every jump uses a distinct empty vertex. With the graph fixed, the population cannot grow past its number of vertices. Replicating the whole graph preserves unit capacities but gives independent copies of the original game; it does not produce a mass relaxation of the hard choices.
To obtain the proposed district model, one must instead give each vertex macroscopic capacity and let many agents share it. That yields a coherent nonatomic game, but changes what a move means: a district can have a positive fraction of spare capacity, and an infinitesimal mover does not change anyone’s neighborhood. The paper’s finite game has unit vacancies and individual moves that can change local counts. So the proposed question is not a direct high-multiplicity version of Theorem 3.1; it depends on a substantive choice of spatial aggregation.
That is the strongest case against this anchor, but it does not establish that the mirror is unworthy. The paper itself motivates the model with residential neighborhoods, and treating districts as locations with capacity for many residents is plausible. The programme also permits capacity scaling when continuization requires it. Under that reading, the authors could reasonably recognize the resulting equilibrium problem as theirs. The cited continuous-types work does not already answer it, and the discrete hardness failing to transfer would be a possible result, not an objection.
So the honest negative case is weak: the mirror needs a clear district-level interpretation, but I cannot rule out a worthwhile scenario for it.
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.