| paper | Variety-Seeking Jump Games on Graphs |
| authors | Lata Narayanan, Jaroslav Opatrny, Shanmukha Tummala, Alexandros A. Voudouris |
| venue | IJCAI 2025 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Bit \(a\) fails: the paper's numbered results concern equilibrium structure, existence, and welfare-quality ratios, but none asserts a computational problem's complexity or an algorithmic result. Theorem 9 therefore cannot anchor a ChoCo mirror, and the \(q\)-clone limit does not change that. The high-multiplicity housing story is plausible, but the proposed capacitated mass formulation also needs a spatial lift to avoid changing unit-capacity occupancy and support-based utilities.
fails bit a — no named computational result to mirror
The stated \(\rho_{v,t}\) model allows multiple types to share a vertex and makes any positive mass alter support; a canonical unit-capacity \(q\)-fold spatial lift and deviation semantics are needed before it is a faithful limit.
fatal: False
The proposed mirror covers only Theorem \(9\)'s social-welfare price-of-anarchy identity; it leaves Theorems \(1\)–\(8\), \(10\)–\(15\), and \(16\)—potentiality, existence, colorful-edge bounds, and price of stability—unmirrored.
The strongest honest positive case is narrow, and it depends on treating an exact price-of-anarchy theorem as an approximation/performance anchor. The paper contains no named theorem asserting NP-hardness, membership in \(P\), FPT, or a similar complexity classification. If ChoCo’s anchor gate requires that literal form, this paper has no qualifying anchor. Under the broader reading that a named worst-case approximation theorem qualifies, I would use only Theorem 9, proved in this paper.
The lead mirror is Mass-Variety-Jump Welfare. A type is a complete resident category relevant to utility—say, a demographic or lifestyle class whose members all value exactly the same neighboring types. The population is a rational mass vector \(\mu=(\mu_1,\ldots,\mu_k)\), with \(\sum_t\mu_t=1\). The graph represents a city’s location template. Each location \(v\) has rational capacity \(b_v\), with \(\sum_v b_v>1\), so some housing remains empty.
A state is a mass assignment \(\rho=(\rho_{v,t})\) satisfying \(\sum_t\rho_{v,t}\le b_v\) and \(\sum_v\rho_{v,t}=\mu_t\). Define \(\operatorname{supp}_\rho(v)=\{t:\rho_{v,t}>0\}\), and give type \(t\) at \(v\) utility
\(u_\rho(t,v)=\sum_{w\in N(v)}|\operatorname{supp}_\rho(w)\setminus\{t\}|\).
Thus utility still counts distinct neighboring types, exactly as in the paper; it is not replaced by entropy or by the fraction of unlike residents. A jump transfers some \(\varepsilon>0\) of type-\(t\) mass from \(v\) to a location \(w\) with spare capacity. The assignment is a mass equilibrium if no such transfer strictly improves the movers’ utility. Social welfare is
\(\operatorname{SW}(\rho)=\sum_{v,t}\rho_{v,t}u_\rho(t,v)\).
The continuous problem is:
Mass-SW-PoA. Given a rational type distribution \(\mu\), determine the worst equilibrium-to-optimum welfare ratio over all connected capacitated graph instances of this form,
\(\operatorname{PoA}^{\infty}_{\mathrm{SW}}(\mu)= \sup_{G,b} \frac{\max_{\rho}\operatorname{SW}(\rho)} {\inf_{\rho\in\operatorname{NE}_\infty(G,b,\mu)}\operatorname{SW}(\rho)}\),
with the usual promise that equilibria exist. A solution consists of the exact ratio together with an upper-bound proof and a family of graph/mass assignments attaining it, or approaching it arbitrarily closely.
The expected answer is the direct high-multiplicity limit of Theorem 9:
\(\operatorname{PoA}^{\infty}_{\mathrm{SW}}(\mu) =\frac{k-1}{1-\max_t\mu_t}\),
assuming every listed type has positive mass. The finite clone version makes the bridge explicit. If \(q\mu_t\) agents of each type are used, Theorem 9 gives
\(\frac{q(k-1)}{q-q\max_t\mu_t+1} =\frac{k-1}{1-\max_t\mu_t+1/q}\),
which converges to the mass formula as \(q\to\infty\).
The proof mechanism also survives. In any equilibrium, take an empty location adjacent to type \(R\). Every non-\(R\) type must obtain utility at least \(1\), or it could jump there. Hence equilibrium welfare is at least \(1-\mu_R\), and therefore at least \(1-\max_t\mu_t\). Optimum welfare is at most \(k-1\) per unit mass. The paper’s clique-plus-type-lines construction gives the matching lower bound: the clique assignment approaches welfare \(k-1\), while the segregated line assignment has welfare approaching \(1-\mu_R\). The finite exceptional \(+1\) agent disappears exactly as high multiplicity predicts.
The regime is plausible: a large housing development or school district contains many interchangeable residents of a small number of payoff-relevant types, while locations have repeated capacities and adjacency structure. The original authors should recognise the model: agents still occupy graph locations, may jump into empty capacity, and seek the number of distinct neighboring types. Only multiplicity and location capacity have been made continuous. Rational masses can be cleared to clones, recovering the finite game on the corresponding one-slot-per-location instances.
I would classify this envelope question as expected Class A: the worst-case ratio has a closed form and depends only on the type masses. The more ambitious fixed-instance problem—given \(G,b,\mu\), compute a minimum-welfare equilibrium or decide whether one below a threshold exists—is separate and may be Class B or Class C. Theorem 9 does not settle it.
The weakest point is the equilibrium semantics. A literal atomless individual has zero effect on type support, so unilateral deviations become vacuous or Wardrop-like. The formulation therefore uses positive-mass jumps, equivalently the limit of one-or-more clone moves. That is an extension rather than a completely literal atomless game. It is nevertheless a controlled one: on rational clone grids it preserves the original jump, vacancy, utility, and welfare semantics, rather than fractionalizing the outcome or changing the strategic objective.
I would not anchor on Theorems 1–8 or 16: they concern cycles, potentiality, existence, or price of stability, not named complexity results. Theorem 9 is enough for a positive case, but only as a narrow, qualified mirror rather than a claim that the whole paper belongs to the continuous computational programme.
The negative case is strongest at the anchor gate: this paper contains no named computational-complexity result. Its theorems concern potentiality, equilibrium existence, and prices of anarchy or stability. Theorem 9 is a worst-case welfare identity, not a complexity classification, algorithm, approximation scheme, or parameterized result. Under ChoCo’s stated remit, that is decisive.
Even under the proponent’s broader reading, Theorem 9 is a poor continuous-computational anchor. Their quantity
\[ \operatorname{PoA}^{\infty}_{\mathrm{SW}}(\mu) = \sup_{G,b} \frac{\max_\rho \operatorname{SW}(\rho)} {\inf_{\rho\in\operatorname{NE}_\infty(G,b,\mu)} \operatorname{SW}(\rho)} \]
has eliminated the graph and capacities from the input by taking the supremum over them. Its only input is the type-mass vector \(\mu\), and the claimed answer is obtained by normalizing Theorem 9:
\[ \frac{n(k-1)}{n-\max_T n_T+1} \longrightarrow \frac{k-1}{1-\max_t\mu_t}. \]
The \(q\)-clone calculation is a useful sanity check for high multiplicity, but it is not an algorithmic bridge: it neither computes an equilibrium for a given society nor exposes a separation problem, optimization problem, or complexity boundary. If \(G\) and \(b\) are retained as inputs, then Theorem 9 no longer answers the question; computing a minimum-welfare equilibrium becomes a new problem invented beyond the paper’s result.
The high-multiplicity premise itself is not the objection. A housing development with many interchangeable residents of each of a few variety-seeking types is perfectly plausible. Nor is the existence of a clone limit evidence against continuization; it is evidence that a high-multiplicity regime can be imagined.
The more serious problem is that the proposed mirror does not continuize only the population. In the paper, every graph node holds at most one agent, and a jump is to an empty node. The proposed \(\rho_{v,t}\) permits several types to occupy one location fractionally and permits mass to enter a merely partially occupied location. That changes the strategic primitive: a neighboring location can now contribute many types to utility, whereas in the paper it contributes at most one. Realizing this with clones requires replacing each vertex by a collection of vertices and specifying their adjacency—complete bipartite, matched, or some other lift. Those choices produce different games. A fixed capacitated graph is therefore not the high-multiplicity limit of the paper alone; it is a simultaneous fractionalization of locations and assignments, precisely the outcome-space continuity that ChoCo puts out of scope.
There is also a non-vanishing discontinuity in the utility. A mass of size \(\varepsilon>0\), however small, changes a neighboring support from “type absent” to “type present,” thereby changing utilities by one. In a genuine atomless game, an individual deviation has zero mass and cannot change support; the resulting Wardrop condition is different. If every positive transfer is allowed to change support, the proposed equilibrium is instead a block-deviation or invasion equilibrium, not the limit of the paper’s one-agent Nash condition. If transfers are required to have a fixed positive packet size, the granularity parameter has simply been reintroduced. This is not a technical issue about ties or strict inequalities: the support objective has no continuous population limit with a canonical equilibrium semantics.
A stronger rescue could use a graphon or a carefully specified \(q\)-fold spatial lift. That would be a legitimate new research direction, but it continuizes the location space and the interaction network as well as the population. Its equilibria and welfare bounds would no longer be a mirror of Theorem 9 in the programme’s population-only sense.
I therefore find the negative case strong under the programme’s actual criteria, but not logically airtight as a modelling claim. The proposed mass game is sensible enough that, if ChoCo accepts global price-of-anarchy identities as computational anchors and permits simultaneous fractionalization of locations, the proponent’s case survives. What cannot honestly be claimed is that this paper supplies a worthwhile population-continuation problem without those broadenings.
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.