| paper | On the Complexity of the Two-Stage Majority Rule |
| authors | — |
| venue | AAMAS 2023 |
| filed under | voting · bribery-control |
| judged by | gpt-5.6-terra / high (triple__gpt-5.6-terra__high__ctx2r8-rejudge1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), a rational society \(\mu\) over complete rankings of \(C\), and target \(p\), does an agenda \(\triangleright\) exist such that \(p\) is the TSMR winner under the strict pairwise-majority margins induced by \(\mu\)?
A society is a rational distribution \(\mu\) over complete ranking types; the discrete decision variable is an agenda \(\triangleright\), and the feasibility objective is to make \(p\) the TSMR winner using the majority graph induced by \(\mu\).
The mirror directly covers Agenda Control in Theorem 1 and Coalition Manipulation in Theorem 2; it leaves the voter/candidate-control and partial-information results unaddressed.
Yes—there is a clean continuous mirror for the paper’s agenda and manipulation results. My lead is the manipulation mirror, because its decision variable is literally a distribution of strategic voter mass rather than a disguised discrete choice.
Call it Continuous Coalition Manipulation for TSMR. An instance consists of candidates \(C\), a rational society \(\mu\) over complete rankings of \(C\), a target \(p\), a fixed agenda \(\triangleright\), and a rational mass \(\beta\geq 0\) of late/strategically coordinated ballots. The decision variable is a nonnegative distribution \(y\) over rankings with \(\sum_\sigma y_\sigma=\beta\). The resulting electorate is \((\mu+y)/(1+\beta)\); equivalently, one can use the unnormalised mass \(\mu+y\), since normalization does not change pairwise-majority signs. The question is whether some \(y\) makes \(p\) the TSMR winner. A solution is such a ballot-mass distribution \(y\). As in the paper’s discrete problem, the objective is feasibility—secure \(p\)’s victory with the stipulated coalition mass—rather than an artificial continuous objective.
This directly mirrors Theorem 2, “Coalition Manipulation for TSMR is in P,” proved in this paper. Its proof gives more than a discrete algorithm: if any strategic ballot multiset works, then the coalition can use the single canonical ballot
\[
p\;\triangleright[B]\;\triangleright[B'],
\]
where \(B\) and \(B'\) are respectively the candidates before and after \(p\) in the agenda. The ballot-swapping argument is monotone in pairwise-majority margins, not dependent on voters being indivisible. Thus in the continuous problem, if any \(y\) works, \(y=\beta e_{\sigma^\star}\) works for that same canonical ranking \(\sigma^\star\). We merely evaluate TSMR after adding mass \(\beta\) to that type. For rational inputs this is polynomial time. I would expect this to be Class A, and indeed it is unusually strong Class A: the continuum removes no essential part of the question, yet collapses the strategic choice to one canonical mass transfer.
The high-multiplicity regime is plausible for a large-membership organisation, union, party primary, or online policy referendum using a fixed sequential agenda: hundreds of thousands of members choose among perhaps 8–20 policy alternatives, while the number of actually occurring ranking types is orders of magnitude smaller than the membership. A coordinated bloc here is not a collection of named, idiosyncratic agents; it is a campaign, caucus, or late-participating constituency of known aggregate size. The paper itself assigns no individual prices, strengths, or private constraints to manipulators, so replacing \(k\) freely chosen added votes by a mass \(\beta\) of freely chosen added ballots preserves exactly the feature its Coalition Manipulation problem studies.
There is a second, even more immediate mirror: Continuous Agenda Control for TSMR. Its instance is a rational ranking distribution \(\mu\) and target \(p\); its decision variable and solution are an agenda \(\triangleright\) over \(C\); and it asks whether \(p\) wins TSMR under that agenda. Define the majority margin
\[
M_\mu(a,b)=\sum_\sigma\mu_\sigma\bigl(\mathbf1[a\succ_\sigma b]-\mathbf1[b\succ_\sigma a]\bigr).
\]
The TSMR majority graph has arc \(a\to b\) exactly when \(M_\mu(a,b)>0\), with ties treated exactly as in the paper. Once these margins are known, the paper’s construction of the agenda from the majority graph applies word for word.
This anchors on Theorem 1, “Agenda Control for TSMR is in P,” also proved here. It is a Class A continuous problem: form the majority graph from the type masses, run the reachability-style agenda construction in the theorem, and output the agenda if it succeeds. This is not a fractional-outcome reformulation; candidates and the agenda remain discrete, while the electorate—the object whose pairwise margins govern TSMR—is continuous.
The two mirrors cover only Theorems 1 and 2, not the paper’s many voter/candidate-control and partial-information hardness results. That is intentional. They are the results for which the paper’s own algorithms are most visibly functions of aggregate margins, so the continuous analogue is exact rather than aspirational. A useful next question is whether the paper’s W[2]-hard adding/deleting-voter results retain hardness when each available ballot class is a divisible supply. Their reductions select named blue-vertex ballots, so fractionalisation may destroy the set-cover combinatorics; that needs separate analysis rather than being claimed by this case.
The weak point is contextual rather than mathematical: the paper motivates TSMR partly by parliamentary procedure, and many legislatures are not high-multiplicity electorates—representatives may be too few and too heterogeneous. I would not sell the mirror for such a chamber. But the same rule and the same strategic questions are credible for large membership or public consultation settings with an agenda-setting authority and organised blocs. In that regime, individual identity is irrelevant by construction, pairwise margins are the operative data, and these two continuous questions are ones the authors should recognise as their own problems with voter counts replaced by population shares.
I cannot make the requested universal negative case honestly. Both anchors survive the standard objections, and Agenda Control in particular is an emphatic continuous-population mirror.
For Coalition Manipulation (Theorem 2), the strongest criticism is contextual: the paper’s parliamentary motivation often concerns small, named representatives, and “a mass of late manipulators” is not a faithful model of that setting. But that does not defeat the problem in every scenario. In a large membership ballot, referendum, union, or party consultation, a coordinated turnout bloc of size \(\beta\) is naturally aggregate rather than individual. No individual-specific eligibility, cost, or constraint appears in the theorem’s model. Its sole relevant feature is the aggregate ranking distribution of the added bloc. Replacing \(k\) ballots by \(\beta\) ballot mass therefore preserves, rather than erases, the object of study.
Nor is this merely an artefact of the proponent’s particular formalisation. A stronger version would let the bloc redistribute mass among existing preference types, or let a campaign induce a bounded amount of preference change rather than add turnout. Those are also meaningful continuous questions, although they become distinct manipulation/bribery models. The proponent’s simpler addition model is already legitimate: it is the high-multiplicity form of the paper’s own unpriced, unconstrained coalition model. The canonical-ballot argument then applies to mass just as it applies to copies of a ballot. Saying that the resulting feasibility problem is easy, or that the same canonical ballot remains optimal, is not a reason not to ask it; it is precisely a clean Class-A outcome.
Agenda Control (Theorem 1) is harder still to reject. TSMR depends on voters only through strict pairwise-majority relations. A population distribution over rankings supplies those relations directly through its pairwise margins, and an agenda setter’s action remains a discrete institutional choice over candidates. Nothing identity-sensitive is lost. In a large electorate using a fixed legislative or consultation agenda, “will candidate \(p\) win under some ordering of the issues?” is naturally a question about population shares, not a question requiring named voters.
One might object that this is an exact extension of the theorem’s majority-graph formulation: once the graph is known, the electorate disappears. But that is not a defect in continuization. It shows that the paper has identified a rule whose agenda-control problem genuinely factors through aggregate social data. The continuous input is still a society, and obtaining the graph from its type masses is the appropriate population-level winner computation. The strict-margin boundary and tie convention are also inherited cleanly from the paper.
The best residual negative point is therefore only one of research priority: these two mirrors are unusually straightforward, have no evident exponential pricing problem, and their continuous answers are likely immediate corollaries of the discrete structural proofs. They may make modest standalone projects compared with a continuous control or uncertainty model that requires new optimization machinery. But that does not establish that they are not worthwhile continuous mirrors. The programme expressly includes tractable continuizations, and neither anchor relies on a bad type space, an implausible limiting story, identity loss, nor degeneration.
So the honest verdict against is weak: the paper should be greenlit on Theorems 1 and 2.
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.