| paper | d4-conf-atal-2017-0272 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions; polynomial-time solvable iff \(\mathrm{P}=\mathrm{NP}\). NP-hard under polynomial-time Turing reductions, and many-one NP-hard iff \(\mathrm{NP}=\mathrm{coNP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite variable set \(V\), a goalbase \(G^0\), and an explicitly listed profile \((I,x_I)\) of Boolean interpretations \(I\in\{0,1\}^V\) with positive rational masses \(x_I\) summing to \(1\), decide whether every interpretation with positive mass maximizes \(G^0\)'s utility over all interpretations in \(\{0,1\}^V\).
An atomless population of total mass \(1\) consisting of one autonomous type, fully specified by its shared goalbase \(G^0\) and Boolean action domain \(\{0,1\}^V\). A profile is a distribution of population mass over interpretations; each individual receives utility \(G^0(I)\), independent of the other agents. Stability means the distribution's support is contained in the set of utility-maximizing interpretations.
The society's type distribution is fixed at a single type, while the varying distribution is over actions, so the population aspect contributes little beyond replicating the paper's one-agent check.
fatal: False
This mirrors Theorem 3's autonomous stability-verification result, including its one-agent hardness case; it leaves the networked stability results, exists-NASH results, and dynamics results unaddressed.
The strongest case I see is narrow: mirror Theorem 3, the paper’s result that IS-NASH is coNP-complete, with hardness even for \(n=1\) and \(d_1=0\). The theorem and its hardness proof are given in the paper. IS-NASH asks whether a specified profile is Nash stable—whether every agent is already choosing a utility-maximizing interpretation. The one-agent, degree-zero restriction matters here: this mirror uses a subproblem the authors themselves analyze, rather than assuming their network hardness survives aggregation.
Call the mirror Mass-IS-NASH. Its instance is a single autonomous type \(t\) of mass \(1\), with Boolean variable set \(V\) and goalbase \(G^0\). Every individual chooses a discrete interpretation \(I\in\{0,1\}^V\), with utility
\[
G^0(I)=\sum_{(\varphi,w)\in G^0:\ I\models\varphi} w.
\]
The proposed population profile is a finite list of interpretations and binary-rational masses \(x_I>0\), with \(\sum_I x_I=1\). The question is whether that profile is stable: for every \(I\) with \(x_I>0\), does \(G^0(I)\ge G^0(J)\) hold for every \(J\in\{0,1\}^V\)? A “yes” solution certifies stability; a “no” instance has an occupied interpretation and a more profitable deviation. There is no social-welfare objective: each individual maximizes their own goalbase utility. The population alone is continuous; every individual’s action remains Boolean.
A plausible regime is a large, isolated cohort of autonomous decision makers applying the same weighted policy template to the same set of issues. The type includes the complete goalbase and action domain, so its members are indistinguishable for this problem. There may be arbitrarily many individuals but just one type; \(x_I\) records what fraction chooses each interpretation. Since the cohort is atomless, those fractions are actual population masses, not lotteries over an individual’s action. This is narrow, but it is precisely the autonomous case covered by the anchor.
The mirror’s expected classification is Class B: hardness transfers. A discrete one-agent IS-NASH instance embeds by putting all mass on its given interpretation. More concretely, for an unsatisfiable formula \(\phi\), take \(G^0=\{(x_0\land\phi,1)\}\) and put all mass on the interpretation setting every variable false. Its utility is \(0\), and the profile is stable exactly when \(\phi\) is unsatisfiable. Conversely, a certificate of instability is a positive-mass interpretation \(I\) and a better interpretation \(J\), so the continuous verification problem is in coNP as well. The paper’s coNP-completeness therefore carries over to this mass-profile problem.
This covers Theorem 3’s stability-verification result; it does not claim to mirror the paper’s \(\exists\)-NASH result or its network dynamics. Natural follow-up questions are whether the hardness persists with nontrivial interactions or bounded variable domains, and how hard it is to *find* a stable profile rather than verify one.
The weak point is that the mass adds little computational structure here: the hardness comes from searching the logical action space, not from population multiplicity, and the anchor has no social influence. That limits the scope of the claim. But it is also why the mirror is credible: the authors’ own theorem isolates exactly this autonomous best-response problem, and the continuum retains its central stability question without making agents’ actions fractional.
The best objection is that Mass-IS-NASH continuizes the profile more clearly than the society. Its society is always the point mass on one autonomous type; the proposed \(x_I\) records what fraction chooses each interpretation. Since those agents’ utilities do not depend on anyone else, stability depends only on which interpretations have positive mass. The mass values do no work in the stability question. That makes this look like a distribution over actions, rather than a computational question created by making the population continuous—the wrong axis under ChoCo’s stated scope.
Allowing several autonomous types does not fix that concern: each type’s stability check remains independent, and type masses do not affect incentives. The obvious route to a population-level question is to restore social influence. But the paper’s utilities depend on a particular network’s neighbor sets and compatibility relations. A continuum version would need an interaction kernel or a restricted block-network model; arbitrary finite networks do not automatically collapse to a small set of interchangeable types. Such a model may be worth studying, but it is a substantial modeling choice rather than a direct population mirror of Theorem 3.
That is the strongest negative case, and it is not decisive. The proponent can reasonably answer that an atomless cohort of identical, isolated decision makers is itself a continuous population, and that the distribution over interpretations is the natural profile for that population. The one-agent reduction then gives a clean, authors-recognizable question. I cannot honestly rule out that mirror in every plausible scenario; the case against is weak precisely at this anchor.
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.