| paper | Strategic Voting with Incomplete Information |
| authors | U. Endriss, S. Obraztsova, M. Polukarov, J. Rosenschein |
| venue | IJCAI 2016 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Neither anchored theorem is a named computational result under the stated gate: Theorem 2 is an existential susceptibility result, and Theorem 8 is a convergence property without an algorithm or complexity claim. The proposed positive-mass dynamics and coalition manipulation questions are substantial re-modelings rather than computational mirrors of those results.
fails bit a — no named computational result to mirror
The case discusses Theorem 8’s convergence and Theorem 2’s susceptibility, but no eligible mirror covers them or the paper’s remaining results.
The strongest positive case is a continuous-population version of the paper’s iterative-voting problem. The paper does not contain a conventional NP-hardness, P-membership, or FPT theorem; its named computational results concern manipulability, immunity, and convergence. I therefore use those as behavioral-computation anchors rather than pretending that the paper proves a standard complexity classification.
The natural regime is a large electorate on a fixed candidate slate: millions of users of a polling platform, party members, or participants in repeated electronic consultations, with only finitely many recurring preference profiles. The immutable voter type is a complete ranking \(r\in L(C)\). For the iterative process, the state records \(\mu_{r,b}\), the fraction with true preference \(r\) currently submitting ballot \(b\). Initially the society is truthful, so mass lies only on \((r,r)\). Candidates and ballots remain discrete; only the population is continuous.
For a ballot distribution \(\mu\), scores and majority margins are normalized population quantities. For example, \(M_\mu(c,d)\) is the fraction preferring \(c\) to \(d\) minus the fraction preferring \(d\) to \(c\). Winner information is still exactly the paper’s \(W\)-IF: voters observe only \(F(\mu)\). A population action transfers a positive rational mass \(\delta\) of agents with state \((r,b)\) to \((r,b')\), preserving their true preference \(r\). This is the necessary high-multiplicity analogue of one voter changing their ballot: a repeated type or cohort acts together.
My lead anchor is Theorem 8, proved in this paper: under the winner information function \(W\)-IF, both Copeland and Maximin converge to a stable outcome for every kind of improvement dynamics. Here “converge” means that every safe-improvement path, starting from truthful voting and with arbitrary voter-update order, eventually terminates or enters a cycle in which the winner remains fixed. The theorem covers the unrestricted set of safe winner-information manipulations, not merely first-place swaps or best responses.
The corresponding problem is Continuous Winner-Only Cohort Convergence. An instance consists of \(C\), either Copeland or Maximin with the paper’s lexicographic tie-breaking, a rational finite-support initial distribution \(\mu^0\) over \((r,b)\), and the rule that a move may transfer any positive rational mass \(\delta\) from \((r,b)\) to \((r,b')\). A move is safe exactly when, among all alternative societies with the same observed winner and with the acting cohort present, it never produces an outcome worse than the current winner according to \(r\), while in at least one such society it produces a strictly better outcome. The question is whether every legal sequence of such mass updates eventually reaches a state whose winner cannot be changed by any subsequent legal safe update. A negative solution is an infinite legal path with infinitely many winner changes; a positive solution should provide a convergence certificate or potential.
The original authors should recognise this as their problem. The observable information is still only the winner, the strategic object is still a ballot, the preference used to evaluate outcomes is still an individual ranking, and the path is still a sequence of myopic safe updates. The only change is that one repeated population type can have positive mass. This is not outcome-space continuity and not a noise model.
I would expect the unrestricted version to be hard for continuum-specific reasons. The paper’s proof uses the potential \(G\), consisting of the winner’s score plus a tie-breaking bonus. In the continuous model, the same potential is naturally defined using normalized scores and remains a promising monotonicity certificate. But monotonicity alone no longer implies finite stabilization: arbitrarily small mass updates can produce infinitely many distinct rational states while \(G\) increases toward a limit. That is precisely a new question created by continuization. A fixed cohort quantum \(\delta\) would likely yield a tractable finite-grid subcase, but the genuinely divisible-mass version should test whether the paper’s finite convergence theorem survives the loss of atomicity.
A second, static anchor is Theorem 2, also proved here. It states that \(k\)-approval for \(k\le m-2\), Copeland, and Maximin are all susceptible to \(W\)-manipulation: for each rule there is a truthful profile and a voter who, knowing only the current winner, can change their ballot so that the change is beneficial in at least one compatible profile and never harmful in any compatible profile. This is an existence result, not a complexity classification.
Its mirror is Continuous Winner-Signal Mass Manipulability. Given a rational truthful distribution \(\mu\), a rule \(F\), and the winner signal \(F(\mu)\), ask whether there exist a true ranking \(r\), a new ballot \(b'\), and a positive mass \(\delta\) of type \(r\) such that transferring that mass from ballot \(r\) to ballot \(b'\) is safe under the paper’s definition and strictly beneficial in at least one society consistent with the same winner signal. A solution is the tuple \((r,b',\delta)\); a negative answer certifies that no positive-mass cohort can safely manipulate.
For \(k\)-approval, I would expect a Class A treatment when the ranking-type set is explicit: the winner regions and post-manipulation constraints are linear, so the question reduces to a finite collection of linear feasibility problems. Copeland and Maximin are more likely to expose a continuum-specific boundary, since their winner regions depend on majority orientations and maximin bottlenecks. With all \(m!\) rankings implicit, the relevant pricing problem may become genuinely difficult. The paper’s finite susceptibility theorem therefore becomes a useful starting point for asking whether the continuous version is tractable, inherits hardness, or is hard because it quantifies over mass distributions rather than named voters.
The weakest point is substantial: a positive-mass cohort is not literally one voter, and the paper’s convergence theorem may fail once mass can be split arbitrarily finely. That is also why I would not claim that Theorem 8 automatically transfers. The claim is narrower: the population-level question is faithful enough that the authors and a referee should recognise it as their strategic-voting problem in a high-multiplicity regime, and it opens a real computational boundary—whether winner-only convergence survives when individual voters become divisible population mass.
The strongest negative case is that neither anchor is actually a computational result about a population problem. Theorem 2 is an existential susceptibility statement, and Theorem 8 is a convergence statement for a finite, sequential, individual-agent process. The paper never defines an input problem, an algorithm, a complexity measure, or even a decision problem about convergence. A continuous version would therefore require inventing the computational question rather than continuizing one from the paper.
Theorem 8 depends essentially on the identity of the acting voter. In the paper, voter \(i\) changes one ballot while \(b_{-i}\) remains the uncertain object. In a society represented by a probability measure, changing one individual’s ballot changes the measure by zero. Scores, majority relations, the winner, and the winner-only information signal all remain unchanged, so there is no strictly beneficial manipulation—even at a tie, because the lexicographic tie-break is unaffected by a measure-zero change. The literal population limit therefore eliminates the strategic action that drives Theorem 8.
The proposed repair—transferring a positive mass \(\delta\) of voters of type \((r,b)\) to ballot \(b'\)—is not a high-multiplicity version of the paper’s move. It is coordinated coalition manipulation. The paper gives no canonical value of \(\delta\): taking \(\delta=1/N\) gives the vanishing unilateral limit, while fixing \(\delta>0\) lets a bloc act jointly and changes the game. Allowing an entire type to move is an even stronger coalition model. The distinction is substantive, not a technicality: the information set, the strategic incentives, and the quantifier over update orders all change.
One could instead study a tagged individual against a continuous background, or take a time-rescaled limit of \(1/N\)-sized asynchronous updates. The tagged individual has no effect in the limit; the rescaled limit requires newly specified rates, timing, and possibly a differential inclusion. That would be a mean-field dynamics paper, not a continuous-population mirror of the theorem’s individual safe-improvement paths. With arbitrary divisible \(\delta\), the paper’s finite-profile notion of cycling also disappears: one can split cohorts indefinitely, so “eventually cycles among profiles” must be replaced by a new eventual-winner or limit-set definition.
Theorem 2 has the same defect. Its \(W\)-manipulation is unilateral and therefore becomes vacuous for a measure-zero agent. The proposed positive-mass version asks whether a coalition of identical voters can safely change the winner. That may be a legitimate new problem—perhaps minimum safe coalition mass—but it is coalition manipulation, not the paper’s susceptibility result. The fact that all members share a ranking does not repair this: the paper’s theorem is about one voter exploiting uncertainty about the others, whereas the mass action requires many voters to coordinate and act simultaneously.
For an explicit type space, the proposed static question is merely a finite robust-feasibility test over winner regions in the profile simplex. The ranking coordinates may be numerous, but the theorem itself contains no computational claim whose high-multiplicity analogue is being exposed. If one hides the rankings and creates a difficult permutation-search problem, that difficulty has been introduced by the new encoding, not inherited from Theorem 2.
There is a genuine weak point in this negative case: a large electorate with recurring preference rankings is a sensible high-multiplicity regime, and minimum-mass coalition manipulation could be worthwhile research. But that would be a new population-game or coalition-control problem. Neither of the paper’s named results survives as a faithful, computational continuous mirror: unilateral actions disappear, while nontrivial mass actions replace the paper’s agents by coordinated blocs.
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.