| paper | Intelligence in Strategic Games (Extended Abstract) |
| authors | Pavel Naumov, Yuan Yuan |
| venue | IJCAI 2022 |
| filed under | frontier · ja |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | no |
Bit (a) fails: none of Theorems \(1\)–\(3\) classifies a computational problem. The proposed mass-synthesis problem changes the paper's arbitrary named-agent mechanism into an anonymous aggregate-action model, so it is a re-modeling rather than a continuous analogue of a named result. The opponent's case is decisive even if that independent model could be worthwhile.
fails bit a — no named computational result to mirror
The anonymous mechanism \(\widehat M\) and aggregate policies \(\Gamma\) replace the paper's arbitrary relation \(M\subseteq W\times\Delta^A\times W\) and exact agent-action profiles, making the proposal a new robust-synthesis problem.
fatal: True
None of the paper's named results has a computational mirror. The proposal only recasts the semantics behind Theorems \(1\)–\(3\) under new aggregate assumptions.
The honest starting point is that this paper contains no qualifying computational anchor. Theorem 1 is an undefinability result, and Theorems 2 and 3 are soundness and completeness results; all three are proved by the authors, with proofs placed in the full version [Naumov and Yuan, 2021]. None asserts NP-hardness, membership in P, parameterized tractability, or any other complexity classification. The conclusion explicitly leaves decidability open. I would therefore not mislabel Theorem 1 as a complexity anchor.
The strongest positive case is consequently prospective: the paper nevertheless identifies a very natural continuous-population problem. I would call it Mass-Intelligence Strategy Synthesis, with the following as the lead candidate.
An instance contains a finite state set \(W\), a finite action domain \(\Delta\), and finitely many complete agent types \(T\). A type records everything relevant to the game: its action set, its indistinguishability relation over \(W\), its role, and its effect on the transition mechanism. The society is a rational distribution \(\mu\) over \(T\). A type of mass \(\mu_t\) represents a large cohort of agents who are indistinguishable for every purpose used by the game. The natural regime is a fleet, security network, or autonomous-vehicle population with millions of agents but only a small number of roles, information profiles, and action capabilities, so \(\tau\ll N\).
Partition the types into coalition, intelligence-source, and neutral types. Replace the named action profile of the original game by type-action masses. Thus \(\beta_{t,a}\) records how much mass of intelligence-source type \(t\) chooses action \(a\), while \(\gamma_{t,a}\) records the coalition’s response. The coalition’s decision variable is a policy \(\Gamma\) mapping every intelligence profile \(\beta\) to a feasible response \(\gamma=\Gamma(\beta)\), subject to the requirement that \(\Gamma\) be constant on states indistinguishable to the coalition. The mechanism is an anonymous relation \(\widehat M(w,z)\) from a state and aggregate type-action vector \(z\) to possible successor states, retaining the paper’s nondeterminism.
The decision problem is:
\[ \textsc{Mass-Intelligence-Synthesis} \]
Given \(W,T,\mu\), the information relations, an anonymous mechanism \(\widehat M\), a state \(w\), and a target formula \(\varphi\), does there exist a finite-description policy \(\Gamma\) such that, for every feasible opponent mass profile \(\beta\), every state \(w'\) indistinguishable from \(w\) to the coalition, every neutral completion, and every \(u\in\widehat M(w',\Gamma(\beta),\beta,\eta)\), we have \(u\models\varphi\)?
For a computational version, \(\widehat M\) could be given by rational polyhedral constraints and \(\Gamma\) by a finite polyhedral partition of the opponent-profile polytope, with a rational response on each cell. A solution is such a policy; the objective is robust achievement of \(\varphi\) against every opponent action distribution and every relevant uncertainty state. This is a direct population analogue of item 5 in Definition 4: “for every opponent action profile, there exists a coalition response,” with individual profiles replaced by type-action masses.
The mirror is plausible because it preserves the paper’s central ingredients: imperfect information, distributed coalition knowledge, intelligence about opponents’ future actions, nondeterministic aggregation, and a one-step robust guarantee. It does not make actions, time, or outcomes continuous. Only the population is continuized. Rational distributions \(\mu_t=k_t/N\) give the high-multiplicity bridge to finite populations, while singleton types recover the named-agent setting.
For finite \(T\), finite \(W\), and polyhedral anonymous mechanisms, I would expect a Class A result in substantial fragments: the response problem is a robust feasibility problem over mass polytopes, potentially reducible to linear programming and duality. The general version may instead be continuum-specifically hard, because the policy quantifies over a continuum of opponent profiles and may require a nontrivial finite representation. Theorem 1 suggests an additional structural question: does the strict expressive separation between \([C]_B\) and ordinary know-how survive after agents are aggregated into types and masses? Theorems 2 and 3 suggest the corresponding axiomatization question: which soundness and completeness principles remain valid for the mass semantics?
The weakest point is substantial. The original paper allows an arbitrary relation \(M\) on named complete action profiles, whereas the mirror requires an anonymous, type-level mechanism. It also replaces finite coalitions by positive-mass coalitions. Those are sensible high-multiplicity assumptions, but they are not consequences of any theorem in the paper. More importantly, because the paper has no named computational result, this cannot yet support the programme’s central hardness-dissolution trichotomy. It is a credible continuous research problem suggested by the paper, but not an anchor-based positive verdict under the programme’s strict rules.
The proponent’s opening concession is decisive under the programme’s rules: this paper has no qualifying computational anchor. Theorem 1 is an undefinability result; Theorems 2 and 3 are soundness and completeness theorems. None classifies a computational problem, and the conclusion explicitly leaves even decidability open. The paper also has no population parameter: \(A\) is a fixed, possibly infinite set of agents, while every coalition \(B,C\) in the semantics is finite. This is not a high-multiplicity problem awaiting relaxation.
The proposed Mass-Intelligence-Synthesis does not repair that absence. The central semantic clause is
\[ w\models [C]_B\varphi \]
iff for every exact opponent action profile \(\beta\in\Delta^B\), there is an exact coalition profile \(\gamma\in\Delta^C\) that succeeds uniformly over compatible complete profiles \(\delta\in\Delta^A\) and indistinguishable states. This is inherently about which individual controls which action, and about correlations among named actions. The paper permits an arbitrary relation \(M\subseteq W\times\Delta^A\times W\), so it may distinguish coordinates, identities, and action correlations.
There are only two ways to aggregate those agents. If the exact profile is preserved, then the type description must retain enough information to distinguish all relevant individual action assignments. The number of effective types then grows with the population, defeating the fixed-\(\tau\) high-multiplicity regime. A “singleton type” does not recover the original game: one type of positive mass represents a cohort of clones, not one named agent.
If instead \(\beta\) and \(\gamma\) become quantities such as \(\beta_{t,a}\) and \(\gamma_{t,a}\), the modality no longer expresses intelligence about each opponent’s move. It expresses intelligence about an aggregate action distribution and permits an aggregate response. The new \(\widehat M\) is an anonymity assumption absent from the paper, and the policy \(\Gamma\) is a mean-field or mixed-action object. The problem has become a new robust synthesis problem over continuous action distributions, not the high-multiplicity version of the paper’s game. It also violates the programme’s “population only” discipline by continuizing strategic actions and the transition mechanism as well.
The proposed polyhedral mechanism and finite polyhedral policy partition make this gap larger. They introduce the entire geometric input model needed for the prospective optimization problem; nothing in the paper motivates that representation or supplies a finite-type family whose high-multiplicity limit produces it. Such a model could be worthwhile as mean-field game theory or robust policy synthesis, but it is not a computational mirror of this paper.
Mass also degenerates in the epistemic component. Distributed knowledge depends on the intersection
\[ \sim_C=\bigcap_{a\in C}\sim_a, \]
not on how much mass each information type has. Repeating identical agents does not strengthen that intersection. If a type has positive mass, one representative already supplies the same information; changing its mass has no effect unless one adds capacities, aggregate transitions, or voting-like power that the original semantics does not contain. Thus the original logic either ignores the masses or must be replaced by a different aggregate-information logic.
The same defeats the proposed continuizations of the named theorems. A mass version of Theorem 1 would be an axiomatic expressiveness question, explicitly outside the programme’s scope. If exact finite-game structure is retained, the undefinability result can simply be replicated in a weighted model and says nothing about continuous computational complexity. If aggregate structure is adopted, there is no reason for the old separation between \([C]_B\) and ordinary know-how to survive in the same form. Theorems 2 and 3 face the identical dilemma: with mass ignored, they are inherited discrete axioms; with mass made semantically relevant, one needs a new measure-theoretic logic rather than a computational mirror.
The honest qualification is that one can invent an anonymous fleet or swarm scenario in which aggregate action distributions are meaningful. That may support an independent research programme. But it does not supply the required bridge from this paper to computational social choice: there is no computational theorem to mirror, no natural multiplicity parameter, and no population mass that remains both semantically faithful and non-degenerate. I would therefore reject this paper as a source of a worthwhile continuous mirror under ChoCo’s definition.
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.