| paper | d4-journals-jair-2019-0059 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 2 supplies a computational result, but its only proposed population mirror makes each deviator infinitesimal and omits deviations into vanishing-mass coalitions. This changes the solution concept, so the stated threshold problem is a different game rather than a continuous version of Theorem 2.
fails bit b-changes — the continuum limit changes the question
The proposed mirror replaces atomic individual deviations with Wardrop-style stability and excludes moves to vanishing-mass coalitions; this changes the strategic question addressed by Theorem 2.
fatal: True
The proponent anchored only Theorem 2; the paper's convergence and price-of-anarchy and price-of-stability results are not mirrored.
The strongest anchor is Theorem 2: “Computing a best Nash equilibrium for SDGs is NP-hard.” The paper proves this result here by reduction from RXC3, whose NP-completeness it cites from Gonzalez (1985). In the paper’s problem, the input is an SDG on an undirected graph; the task is to find a Nash-stable partition maximizing the sum of agents’ harmonic-centrality utilities. The proof builds a graph with \(6m\) vertices from an RXC3 instance with \(m=3p\) elements. It shows that an exact cover exists if and only if the constructed game has a Nash equilibrium with social welfare at least \(\frac{257}{20}p\). That is a substantial hardness result, and the reduction’s combinatorics are in the graph structure.
I would mirror Theorem 2 with the following problem, the *Mass-SDG Best-Equilibrium Threshold*. Let \(H=(T,F)\) be a connected, unweighted graph of social roles, and let \(\mu\in\mathbb{Q}_{>0}^{T}\) be a population distribution with \(\sum_{t\in T}\mu_t=1\). Agents of type \(t\) have the same role and the same network relationships: agents of adjacent types are linked, agents of the same type are not directly linked, and their other relationships are identical. This is the high-multiplicity regime: the population can be very large compared with the number \(\tau=|T|\) of distinct roles.
A coalition is represented by its mass vector \(z\in\mathbb{R}_{\ge 0}^{T}\setminus\{0\}\), with support \(S=\operatorname{supp}(z)\). For a type-\(t\) agent considering that coalition, let \(d_S(t,s)\) be the shortest path in the role graph induced by \(S\cup\{t\}\), for \(s\ne t\); unreachable types have distance \(\infty\). Distinct members of type \(t\) have distance \(2\) when some neighboring type is present in the coalition, and otherwise are disconnected. The limiting utility is
\[ u_t(z)= \frac{ \mathbf{1}[N_H(t)\cap S\ne\varnothing]\,z_t/2 +\sum_{\substack{s\in S\\s\ne t}} z_s/d_S(t,s) }{ \|z\|_1 }, \]
where an unreachable type contributes zero. This is the per-capita limit of the paper’s harmonic-centrality-over-coalition-size utility in the corresponding replicated-role graphs.
A mass clustering is a finite or countable family of coalition vectors \((z^j)_j\) with \(\sum_j z^j=\mu\). Define macroscopic Nash stability by requiring that every type \(t\) used in coalition \(j\) weakly prefer it to every other positive-mass coalition, and to becoming a singleton with utility zero: \(u_t(z^j)\ge \max(0,\sup_{k\ne j}u_t(z^k))\). Its per-capita welfare is \(\mathrm{SW}_\mu=\sum_j\sum_t z^j_tu_t(z^j)\). Given \(H,\mu\), and a rational threshold \(\beta\), the question is whether there exists a stable mass clustering with \(\mathrm{SW}_\mu\ge\beta\); a solution is the family of coalition mass vectors witnessing this.
This is recognizable as the authors’ problem because it keeps the same network-based distances, the same centrality-based utility, coalition membership as the decision, unilateral stability, and welfare maximization over stable outcomes. The co-modification is that a type’s population can split across coalitions, as required by a mass model. For the paper’s reduction, the natural candidate role graph is its constructed graph \(G_I\), with \(\mu\) uniform over its \(6m\) roles. The corresponding normalized threshold would be \(\beta=\frac{257p}{120m}\). That identifies the precise transfer question; it does not establish that the reduction still works.
I would provisionally expect hardness to transfer (Class B): the exact-cover incidence pattern lives in the role graph, which remains an input even when each role has a large population. But the proof would need to show that allowing each type’s mass to split does not create high-welfare equilibria that bypass the cover structure. Theorem 2 alone says nothing about that. Natural follow-up questions are whether the threshold problem remains hard for uniform masses, whether it becomes tractable for restricted role graphs or fixed \(\tau\), and whether optimal mass equilibria admit finite, rational descriptions.
The main weakness is the stability notion at the continuum boundary. This formulation captures moves among positive-mass coalitions; a finite SDG also lets an agent move into a small coalition whose population share vanishes as the network grows. Such a coalition can still offer nonzero utility, and the mass profile does not record it. A two-scale model that retains these small coalitions may be needed if the authors regard them as essential to Nash stability. The blow-up also restricts the input to populations with shared role-level neighborhood patterns. These are real limits, but the proposed question still gives a concrete large-population version of the paper’s best-equilibrium problem. Its scope is only Theorem 2; it does not mirror the paper’s convergence or price-of-anarchy and price-of-stability results.
The strongest case against is that network position is the agent type in this paper. In an arbitrary SDG, an agent’s exact neighborhood affects shortest paths and possible deviations. Grouping agents by degree or by a coarse social label would lose information the game uses; grouping them by their full structural role usually leaves \(\tau\) close to \(n\). That makes the paper’s hard instances poor examples of high multiplicity.
The proposed role graph \(H\) is the best way around this: replicate each role and connect adjacent role classes as complete bipartite blocks. That gives a coherent family of large networks, but it changes the strategic question at the continuum boundary. An infinitesimal agent does not change a coalition’s mass or support when moving. Stability therefore becomes a Wardrop condition over occupied coalitions. The proposal also rules out moves to empty or vanishingly small coalitions by comparing only positive-mass coalitions; those moves are part of the paper’s individual-agent Nash condition. Keeping their effects would require retaining atomic agents or adding another scale to the model.
Theorem 2’s reduction also relies on indivisible agents: an element vertex is assigned to a triple gadget, and the welfare threshold detects an exact cover. In the mass model, each element type can split among its three incident triples. The regular RXC3 incidence structure even has a natural fractional assignment, giving each incident triple one third of that type’s mass. This does not prove that the mass game is easy, but it means the paper’s reduction supplies no hardness argument for the mirror; its key integrality step would need to be rebuilt.
A stronger version could study the limit of best equilibria in finite replicated role graphs. That is a plausible asymptotic question, but convergence of equilibria and welfare would itself need to be established. The role graph can support interesting computational questions, so these objections do not show that no worthwhile mirror exists in any scenario. They show that Theorem 2 does not transfer cleanly to the proposed atomless game, and that a mirror would need a new, convincing account of both its network regime and its stability concept. The negative case is therefore real but limited: block-structured networks are a plausible high-multiplicity setting, and their nonatomic SDG could still be worth studying on its own.
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.