| paper | d4-conf-atal-2017-0224 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | unclear |
Theorem 9 proves semantic preservation but does not state a computational result of the kinds required here. The proposed population-game problem would introduce new mass-state and strategy semantics without a specified finite encoding, so it cannot supply the missing eligible anchor.
fails bit a — no named computational result to mirror
Theorem 9 is a semantic preservation result, while the proposed mass-flow model leaves its state, transition, and strategy-matching representation unspecified.
fatal: True
The proposed extension concerns ATL preservation and bisimulation checking over a population model; it does not cover the paper’s finite-model results or its ThreeBallot verification experiments as stated.
The strongest honest anchor is Theorem 9, proved in the paper. It says that if states \(q\) and \(q'\) in two iCGS are \(A\)-bisimilar, then they satisfy exactly the same \(A\)-formulas of ATL. The paper states this for both objective and subjective state-based semantics with imperfect information and imperfect recall. This is the theorem that makes the ThreeBallot abstractions useful: a property checked on a simpler model transfers to the related model.
The paper has no named theorem establishing a complexity class such as P or NP-hardness for its verification problem. Theorem 9 is a preservation result, not a complexity classification. My case is therefore for a continuous extension of the paper’s verification question, not for a complexity result already contained in it.
The lead mirror is mass-ATL bisimulation checking for a ThreeBallot electorate. Consider a large election with a fixed candidate set and a common ballot-generation protocol. A type records a voter’s intended candidate, legal ThreeBallot ribbon triple, current protocol status, and the other features the model uses. A society is a distribution \(\mu\) over these types. Its support size \(\tau\) can stay bounded as the number of voters grows: for fixed candidates and protocol, many voters can share the same complete type. The attacker and the protocol’s environment remain finite, distinguished components.
A population state has the form \((q,\mu)\), where \(q\) records those finite components and public bookkeeping, and \(\mu\) records the hidden electorate. At a transition, a variable \(x_{t,a}\) gives the mass of type \(t\) taking action \(a\), with \(\sum_a x_{t,a}=\mu_t\). Rational linear rules update the type masses and the published ballot histogram. Treating published counts as masses, and allowing the protocol to publish aggregate ballot data in a round, are co-modifications needed by the population limit.
An instance gives two such systems, rational initial states, a finite set of atomic propositions, and a proposed relation \(R\) between their states, described by rational linear constraints. The question is whether \(R\) is an attacker alternating bisimulation. That requires matching labels and the attacker’s indistinguishable states in both directions, and translating each partial uniform attacker strategy so that every permitted mass-flow transition has a related matching successor. A solution is a proof of those clauses, including the strategy translations; a negative answer identifies a failed clause and a counterexample. The continuous counterpart of Theorem 9 would then establish that every ATL formula involving the attacker has the same truth value at related states. Such formulas can ask, for example, whether the attacker can force eventual knowledge of a specified feature of the electorate’s vote distribution.
This is a plausible problem for these authors: their paper develops strategic verification, proves a preservation theorem, and uses abstraction to verify a voting protocol. The scenario is a large election whose voters share finitely many protocol-relevant types, rather than a small committee. The paper’s individual-voter coercion formula does not itself become a positive-mass property; the continuous question naturally concerns the population distribution, or keeps a particular target as a finite distinguished component.
My working prediction is Class C for the general symbolic problem. Although the transition rules can be linear in the masses, bisimulation must match strategies across continuum many population states and account for the attacker’s information. A restricted version with finite observation classes and polyhedral strategy translations might be tractable, but the paper gives no basis for claiming that. The grid cases \(\mu_t=n_t/n\) should remain available, so any discrete lower bound would carry over; this paper does not establish such a lower bound for bisimulation checking.
The weak point is substantial: the paper’s systems have finitely many named agents, and its experiments cover only small electorates. Its proof does not establish bisimulation for measure-valued states or strategies, and its ThreeBallot model does not retain every individual ballot feature. Extending the state space and the preservation argument is real new work. What survives that objection is the narrower claim: the continuous question directly extends the paper’s central problem—when a strategic property survives abstraction—to an election regime where population mass is a natural representation.
The strongest objection is that the paper does not give a complexity theorem for a computational problem in the programme’s usual sense. Theorem 9 is a semantic preservation result: related states satisfy the same ATL formulas. The experiments show that three finite models can be checked at different speeds. Remark 7 says that checking for an alternating bisimulation between finite iCGSs is in PSPACE, but the paper does not make that problem its main result. So the proposed mirror is not a high-multiplicity version of a theorem about, say, bribery or winner robustness. It would introduce a new symbolic population-game problem.
The proposed mass-flow version also needs more than rational masses to become a computational problem. In the paper, bisimulation quantifies over states, indistinguishability neighborhoods, and partial uniform strategies, and requires a strategy translation that works across those neighborhoods. A distribution-valued state space is infinite. The proposal does not specify a finite representation for its transition relation or for that strategy translation. Restricting both to polyhedral descriptions might make checking well-defined, but it would also choose a new strategy semantics whose relationship to Theorem 9 needs to be established.
A better mirror would use a finite attacker and a distinguished voter, with the remaining voters represented by a rational distribution over protocol-relevant types. It could ask whether ATL model checking, or bisimulation checking, is tractable as the electorate grows. That avoids the blunt objection that every voter is anonymous: the formula’s target stays individually represented, while the other voters supply the high-multiplicity population. It is a credible research question.
The reservation is that the paper’s security property depends on what the attacker can distinguish about a particular voter from the published ballots. The model publishes ribbons one at a time, while a mass state naturally records aggregate quantities. To preserve the property, the population model must encode enough of the public board and its correlation with the distinguished voter to reproduce the attacker’s indistinguishability relation. The authors might find such an encoding natural, but the paper does not provide one, and finding it may amount to designing a new voting-protocol semantics rather than extending the stated finite-model theorem.
That is the best case against: the anchor is semantic rather than algorithmic, and its proposed continuous version lacks a specified finite encoding for the central epistemic and strategy-matching conditions. It does not establish that no worthwhile mirror exists. The tagged-voter population model remains plausible, and the paper gives no basis for ruling it out across scenarios. On the material here, the universal negative case is weak.
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.