| paper | d4-conf-atal-2020-0214 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete, even for every fixed \(m>3\), equal masses, and \(W_{st}\in\{0,-1\}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.7
statement extracted from the paper’s text layer
Given \(k>3\) locations, rational masses \(\mu_t\), and a symmetric nonpositive influence kernel \(W\) with \(W_{tt}=0\), let \(x_{tj}\ge 0\) satisfy \(\sum_j x_{tj}=\mu_t\). Define \(u_t(j;x)=\sum_s W_{st}x_{sj}\); call \(x\) a population PSNE when \(x_{tj}>0\) only if \(j\) maximizes \(u_t(j;x)\). Is there a population PSNE with normalized welfare \(\sum_{t,j}x_{tj}u_t(j;x)\ge 0\)?
Each type is a cohort of indistinguishable agents with mass \(\mu_t\), the same location choices, and the same influence pattern toward every type. The decision variables \(x_{tj}\) are the mass of type \(t\) choosing location \(j\); capacities are nonbinding, and the payoff is \(u_t(j;x)=\sum_s W_{st}x_{sj}\). For rational masses, finite replicated cohorts with appropriately scaled per-agent influence weights have the same best-response condition because \(W_{tt}=0\).
The mirror covers Theorem 3.7, the hardness of selecting a total-welfare-maximizing PSNE. It leaves the existence and counting results, location-specific welfare hardness, the algorithmic results, and the experiments unaddressed.
The strongest mirror I see is the paper’s welfare-selection result, not its question of whether any equilibrium exists.
A plausible regime is a large school district or multi-site organization with many residents but relatively few recurring social-network roles. Everyone in a role has the same location choices and the same influence pattern toward each other role. Let \(T\) be those roles, with rational population masses \(\mu_t\), and let \(x_{tj}\) be the mass of role \(t\) choosing location \(j\). Each person still chooses one location; \(x_{tj}\) records the share of a continuum cohort assigned there. With nonbinding capacities and no location effect, define the payoff from location \(j\) by
\[
u_t(j;x)=\sum_{s\in T} W_{st}x_{sj},
\]
where \(W_{st}\) is the per-capita influence of role \(s\) on role \(t\). A population PSNE is an assignment satisfying \(\sum_j x_{tj}=\mu_t\) in which \(x_{tj}>0\) only if \(j\) maximizes \(u_t(j;x)\). Its social welfare is
\[
\mathrm{SW}(x)=\sum_{t\in T}\sum_j x_{tj}u_t(j;x).
\]
This is the paper’s localized-influence utility and welfare criterion applied to population masses; the population, rather than the locations or outcomes, is what becomes continuous.
My anchor is Theorem 3.7, proved in this paper: computing a PSNE that maximizes total social welfare is NP-hard even when the social network has only negative edges, there is no location effect, and there are more than three locations. The paper proves this by reduction from \(k\)-colorability. The corresponding continuous problem, Continuous Welfare-Maximum PSNE, takes \(T\), rational masses \(\mu_t\), a symmetric nonpositive influence kernel \(W\) with \(W_{tt}=0\), and \(k>3\) locations; it asks for a population PSNE maximizing \(\mathrm{SW}\). Its decision form asks whether there is a PSNE with welfare at least a given threshold.
The reduction survives fractional assignment, which is the main reason I believe this mirror. Given a graph \(G=(V,E)\), make one type per vertex, give each mass \(1/|V|\), and set \(W_{uv}=-|V|\) for edges and \(0\) otherwise. A whole neighboring type then contributes \(-1\), matching the discrete influence in the reduction. Welfare is never positive. It equals zero exactly when adjacent types have no mass in common locations. If that happens, choosing any occupied location for each type gives a proper \(k\)-coloring: adjacent types cannot share that location. Conversely, a proper coloring puts each type’s entire mass at its color, gives everyone payoff zero, and is an equilibrium because no location can give a positive payoff. Thus the maximum welfare is zero exactly when \(G\) is \(k\)-colorable.
Allowing types to split across locations does not undo this test. In this symmetric, negative-influence case, welfare is linear in each type’s allocation when the other types’ allocations are fixed, so an optimal assignment can be chosen with each type wholly at one location. More directly, the zero-welfare threshold already rules out fractional escape: zero requires disjoint location supports for every adjacent pair.
I expect Class B: hardness transfers. The coloring combinatorics live in the network of types and the set of locations, not in the number of people. A population can have \(N=M|T|\) residents for arbitrarily large \(M\) while retaining the same type support \(\tau=|T|\); the hard structure remains in that support. This mirror covers Theorem 3.7 only. I would not use Theorem 3.1 as an anchor: existence can behave very differently when a continuum cohort can divide across actions, and counting equilibria has no straightforward continuous counterpart. Further questions include how the complexity changes with bounded \(\tau\), network structure, or number of locations, and which other SG-LSI welfare results survive a formal finite-to-continuum dictionary.
The weakest point is the role-level network assumption. Repeated people with identical influence patterns toward every role are a strong idealization, and a referee could object that this changes individual-network PSNE into a nonatomic population equilibrium. Still, it is a recognizable high-multiplicity version of the paper’s model: the same agents choose among the same locations, face the same influence-based utilities, and are evaluated by the same welfare objective. The hardness argument also remains valid after allowing population mass to split.
The only anchor raised is Theorem 3.7, and I cannot honestly defeat its strongest continuous mirror. Replicate each graph vertex into a large cohort, give every member of one cohort influence \(-1/M\) toward every member of each adjacent cohort of size \(M\), and normalize the cohorts to masses \(1/|V|\). The resulting type-level payoff is the proposed kernel payoff. Since all weights are nonpositive, welfare is at most zero; welfare reaches zero exactly when adjacent types have disjoint location supports. Choosing one supported location for each type then gives a proper coloring. Fractional assignments do not evade the reduction.
The strongest objection is that the reduction uses one type per graph vertex, with an independently specified interaction pattern for each type. Its replicated version assumes a block network: everyone in a cohort has the same influence on every member of each neighboring cohort. That is a substantial restriction on the paper’s individually specified social networks, and the coloring reduction’s hardness is in the role graph, not in how many people occupy each role. A reader could therefore question how central this regime is to the paper’s motivating settings.
That objection does not rule out a worthwhile mirror. Large cohorts with uniform cross-group influence form a plausible high-multiplicity regime, and the paper explicitly studies network structure and equilibrium computation. The shift to population-level equilibrium and welfare also needs a careful finite-to-continuum dictionary, especially when types split across best-response locations, but it leaves a recognizable computational question. The negative case is therefore weak: it identifies a modeling restriction, yet the proposed mirror survives 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.