Universal Voting Protocol Tweaks to Make Manipulation Hard (d4-conf-ijcai-2003-0337)

Given a candidate set \(C\), target \(p\), protocol \(P\in\{\mathrm{Plurality},\mathrm{Borda},\mathrm{Maximin},\mathrm{STV}\}\), fixed announced pairing \(\mathcal M\), rational finite-support distribution \(\nu\) over complete rankings with \(\sum_t\nu_t=1-\alpha\), and a controlled \(p\)-top type of mass \(0<\alpha<1\), does some common bloc report \(r\) make \(p\) win under DPRE + \(P\) on \(\mu^r=\nu+\alpha e_r\)?

Given candidates \(C\) with \(m=|C|\geq2\), a target \(p\in C\), and a fixed protocol \(P\in\{\mathrm{Plurality},\mathrm{Borda},\mathrm{Maximin},\mathrm{STV}\}\), all ranking types are strict total orders of \(C\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) denotes support size, not the number of possible rankings. Here \(\tau=|\operatorname{supp}(\nu)|\) describes the fixed, uncontrolled society.
The input includes these known masses \(\nu_t>0\), a binary rational \(0<\alpha<1\) with \(\sum_t\nu_t=1-\alpha\), and a controlled bloc of mass \(\alpha\) whose true ranking places \(p\) first. The entire bloc must submit one common strict ranking \(r\), unrestricted by its true ranking; its mass cannot be split among reports. The reported society is \(\mu^r=\nu+\alpha e_r\), where \(e_r\) is unit mass on \(r\).
An announced pairing \(\mathcal M\) partitions \(C\) into pairs, with exactly one bye when \(m\) is odd. In DPRE, each pair retains the candidate preferred by greater total reported mass, and a bye survives automatically.
Delete all eliminated candidates from every reported ranking, retaining every type's mass, and apply \(P\) to the survivors using mass in place of voter counts. Borda uses the number of survivors; STV is the single-winner elimination rule. A sole survivor wins automatically.
Use a fixed public priority order on candidate labels: the highest-priority tied candidate wins a pairwise or final-score tie, and the lowest-priority tied candidate is eliminated in STV. Winning means being the resulting unique winner. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).

For each fixed \(P\in\{\mathrm{Plurality},\mathrm{Borda},\mathrm{Maximin},\mathrm{STV}\}\), is deciding whether some common report \(r\) makes \(p\) win under \(\mathrm{DPRE}+P\) on \(\mu^r\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?

Discrete constructive manipulation is \(\mathrm{NP}\)-complete for each of these four preround protocols, even with one unweighted manipulator and all other votes known ([Conitzer–Sandholm](https://www.cs.cmu.edu/~sandholm/voting_tweaks.ijcai03.pdf)).
No separate result for exactly the rational-mass, common-report formulation was verified.

Classification

For each fixed \(P\in\{\mathrm{Plurality},\mathrm{Borda},\mathrm{Maximin},\mathrm{STV}\}\), the stated common-report manipulation problem is \(\mathrm{NP}\)-complete.

The reduction normalizes an election with one unweighted manipulator. Aggregating identical uncontrolled votes into support types preserves every outcome, so neither rational masses nor support representation obstructs the transfer.

1. The discrete hardness theorem applies

Theorem 6 of [Conitzer–Sandholm, *Universal Voting Protocol Tweaks to Make Manipulation Hard*](https://www.cs.cmu.edu/~sandholm/voting_tweaks.ijcai03.pdf) establishes \(\mathrm{NP}\)-completeness of constructive manipulation for each of the four deterministic-preround protocols.

The source’s definitions and conventions supply the required hypotheses:

• Every vote is a strict total order.
• There is one unweighted manipulator, and all other votes are known.
• The pairing is announced before the manipulator reports.
• Eliminated candidates are deleted from every ranking before applying the underlying protocol.
• The results hold for any tie-breaking rule.

Thus we may use its hardness theorem with exactly the public priority convention in the question, including elimination of the lowest-priority tied candidate in STV.

2. A polynomial normalization reduction

Fix one of the four protocols \(P\). Consider a discrete instance with candidate set \(C\), target \(p\), announced pairing \(\mathcal M\), and \(N\) explicitly listed uncontrolled votes.

We first treat \(N\geq1\) and \(m\geq2\). Let \(t_1,\ldots,t_\tau\) be the distinct uncontrolled rankings, and let \(k_i\) be the number of occurrences of \(t_i\). Hence

\[ k_i\geq1,\qquad \sum_{i=1}^{\tau}k_i=N. \]

Construct the rational-mass instance by keeping \(C,p,\mathcal M\) and setting

\[ \alpha=\frac{1}{N+1}, \qquad \nu_{t_i}=\frac{k_i}{N+1}. \]

Here and below, the displayed formulas are:
\(k_i\geq1,\ \sum_{i=1}^{\tau}k_i=N\), and
\(\alpha=1/(N+1),\ \nu_{t_i}=k_i/(N+1)\).

These masses satisfy all input requirements:

\[ 0<\alpha<1,\qquad \nu_{t_i}>0,\qquad \sum_{i=1}^{\tau}\nu_{t_i} =\frac{N}{N+1}=1-\alpha. \]

Equivalently,
\(0<\alpha<1\), \(\nu_{t_i}>0\), and
\(\sum_{i=1}^{\tau}\nu_{t_i}=N/(N+1)=1-\alpha\).

Choose any true ranking of the controlled bloc with \(p\) first. Its true ranking imposes no restriction on its report, so the permitted reports are exactly the discrete manipulator’s possible votes.

Grouping identical votes takes polynomial time in the explicitly listed discrete input. Each numerator and denominator has \(O(\log(N+1))\) bits. The output contains \(\tau\leq N\) rankings, so its length is polynomial in the source input length.

For completeness, instances with \(N=0\) or \(m=1\) are always yes-instances: a sole manipulator can put \(p\) first, making it survive the preround and win under each of the four protocols. Map these cases to the fixed valid yes-instance with two candidates, pairing them together, uncontrolled mass \(1/2\) on \(p\) above its opponent, and controlled mass \(\alpha=1/2\).

3. Outcome preservation for every report

Fix an arbitrary common report \(r\). Compare the discrete election consisting of the \(N\) uncontrolled votes and the manipulator’s vote \(r\) with the constructed rational society \(\mu^r\).

For every candidate pair \(a,b\), the mass preferring \(a\) to \(b\) is exactly the corresponding discrete voter count divided by \(N+1\). Consequently, every preround comparison has the same direction and the same equality status. Because priorities are unchanged, pairwise ties are resolved identically. Both elections therefore produce exactly the same survivor set \(S\).

Deleting candidates outside \(S\) also preserves this relationship: the mass of each restricted ranking equals its discrete multiplicity divided by \(N+1\), including the contribution of \(r\). We now verify each final protocol.

Plurality. Each candidate’s first-place mass is its discrete first-place count divided by \(N+1\). Scores and ties therefore agree.

Borda. Both elections have the same number \(|S|\) of survivors and use the same Borda coefficients. Each candidate’s total mass-based Borda score is its discrete Borda score divided by \(N+1\). Scores and ties agree.

Maximin. Every pairwise support is divided by \(N+1\). Since this factor is positive, taking the minimum over opponents commutes with scaling. Thus every maximin score is its discrete counterpart divided by \(N+1\), with identical ties. If there is only one survivor, both elections declare it the winner automatically.

STV. Induct on elimination rounds. Initially the remaining sets agree. If they agree at the start of a round, each candidate’s first-place mass among the remaining candidates equals its discrete first-place count divided by \(N+1\). The candidates of minimum score are therefore identical. The same priority rule eliminates the same candidate, proving that the remaining sets agree in the next round. Hence the eventual winners agree.

We have proved, for every strict report \(r\),

\[ r\text{ makes }p\text{ win in the discrete instance} \quad\Longleftrightarrow\quad r\text{ makes }p\text{ win in the rational instance}. \]

That is, \(r\) makes \(p\) win in the discrete instance if and only if it makes \(p\) win in the rational instance.

Taking existence over all \(r\) proves correctness of the many-one reduction. The discrete hardness theorem therefore gives \(\mathrm{NP}\)-hardness for every fixed \(P\).

4. Exact verification and running times

A certificate is one strict ranking \(r\), encoded using \(O(m\log m)\) bits. It remains to show that its outcome can be verified in polynomial bit complexity.

Let \(D\) be the product of the input denominators of \(\alpha\) and the \(\tau\) uncontrolled masses. The binary length of \(D\) is \(O(L)\), because the denominator lengths together are bounded by the input length. Multiplying every mass by \(D\) gives integer weights and preserves all outcomes by the same scaling argument used above.

Computing \(D\) and these integer weights takes \(O((\tau+1)L^2)\) bit operations using schoolbook arithmetic. Individual weights, accumulated supports, and Borda scores have \(O(L+\log m)=O(L)\) bits.

After preprocessing ranking positions:

• The preround and final plurality or Borda computation require \(O((\tau+1)m)\) arithmetic operations.
• Computing all pairwise supports for maximin requires \(O((\tau+1)m^2)\) operations.
• STV can be simulated by rescanning every ranking in each elimination round, using \(O((\tau+1)m^2)\) operations.

Thus a uniform, conservative verification bound for all four protocols is

\[ O\bigl((\tau+1)m^2L^2\bigr). \]

In inline notation, this bound is \(O((\tau+1)m^2L^2)\) bit operations. This proves membership in \(\mathrm{NP}\). Exhaustive enumeration also gives a deterministic decision algorithm taking \(O(m!(\tau+1)m^2L^2)\) bit operations, which is polynomial when \(m\) is fixed.

5. Conclusion

All four problems are \(\mathrm{NP}\)-complete, already on the restricted family with
\(\alpha=1/(N+1)\) and \(\nu_{t_i}=k_i/(N+1)\).
The controlled bloc submits precisely one common report throughout the reduction; its mass is never split.

⟨structured verdict parsed — rendered above⟩

The prover’s classification is correct and rigorous: the common-report problem is \(\mathrm{NP}\)-complete for each of the four fixed protocols. The normalization reduction preserves outcomes for every report, and the verification algorithm has polynomial bit complexity. No major or minor mathematical issues were found.

1. Applicability of the cited hardness theorem

The citation is accurate. Theorem 6 establishes the stated discrete \(\mathrm{NP}\)-completeness result. The source defines manipulation using one unweighted manipulator with all other votes known, defines DPRE using a preannounced pairing and deletion of eliminated candidates from rankings, and explicitly states that its results hold for any tie-breaking rule. Its definitions of the four underlying protocols agree with those used here. Thus the fixed public priority convention satisfies the cited theorem’s hypotheses. [Conitzer–Sandholm, Sections 2 and 4, Theorem 6](https://www.cs.cmu.edu/~sandholm/voting_tweaks.ijcai03.pdf).

The prover invokes an established theorem with the required hypotheses; it does not rely merely on similarity between the discrete and rational formulations.

Finding: Valid application of the cited theorem.

2. Construction and validity of the normalization

For \(N\geq1\), the assignments
\(\alpha=1/(N+1)\) and \(\nu_{t_i}=k_i/(N+1)\) satisfy all required constraints:

• \(0<\alpha<1\).
• Every listed uncontrolled mass is positive because \(k_i\geq1\).
• Their sum is \(N/(N+1)=1-\alpha\).
• The support contains precisely the distinct uncontrolled ranking types.

Each rational has a numerator and denominator of \(O(\log(N+1))\) bits. Aggregation and output construction are polynomial in the explicitly listed source input. The reduction requires no expansion into all possible rankings.

Choosing the bloc’s true ranking with \(p\) first satisfies the target formulation. Because reports are unrestricted, this introduces no additional constraint on the discrete manipulator’s vote.

The exceptional cases are also handled correctly. With \(N=0\), placing \(p\) first makes it survive and win under each protocol. With \(m=1\), it wins automatically. The proposed two-candidate replacement is a valid yes-instance.

Finding: The reduction produces valid instances in polynomial time, including the stated edge cases.

3. Preservation of the preround

For every fixed report \(r\), every pairwise support is the corresponding discrete count multiplied by the same positive factor \(1/(N+1)\). This preserves strict comparisons and equalities.

The pairing and priorities remain unchanged, so every pair produces the same survivor. Any bye also remains unchanged. Hence the survivor sets agree exactly.

Deletion preserves the scaling relationship between restricted rankings. This remains valid when several original types collapse to the same restricted ranking, or when the report coincides with an uncontrolled type: their contributions add in both representations.

Finding: Preround outcomes and restricted profiles are preserved for every report.

4. Preservation of each final protocol

Plurality. First-place scores scale uniformly by \(1/(N+1)\). Winners and ties agree.

Borda. The survivor sets have the same size, so both elections use identical positional coefficients. Every score scales uniformly, preserving winners and ties.

Maximin. Every pairwise support scales uniformly. Taking the minimum over opponents commutes with multiplication by a positive constant. The separate sole-survivor convention correctly avoids an undefined minimum over an empty opponent set.

STV. The induction is complete. Equal remaining sets give uniformly scaled first-place scores, hence identical minimum-score sets. The fixed elimination priority selects the same candidate, maintaining equal remaining sets through termination.

Consequently, the stated equivalence holds for every strict report \(r\). Taking existence over the same report domain establishes the many-one reduction.

Finding: Outcome preservation is correct for all four protocols, including ties and singleton survivor sets.

5. Exact arithmetic and verification bounds

A report has polynomial certificate length, \(O(m\log m)\).

The denominator product \(D\) has \(O(L)\) bits because its logarithm is bounded by the sum of the input denominator lengths. All masses become exact integer weights after multiplication by \(D\), and this common positive scaling preserves outcomes.

The claimed arithmetic bounds are sound:

• Computing \(D\) and the integer weights within \(O((\tau+1)L^2)\) bit operations is a valid conservative schoolbook bound.
• Total integer weight equals \(D\), so weights and accumulated supports have \(O(L)\) bits.
• Borda scores have \(O(L+\log m)=O(L)\) bits under the explicit ranking encoding.
• Preround, plurality, and Borda calculations require \(O((\tau+1)m)\) arithmetic operations after position preprocessing.
• Pairwise support computation requires \(O((\tau+1)m^2)\) operations.
• STV rescanning costs \(O(m)\) per ranking per round over at most \(O(m)\) rounds, giving \(O((\tau+1)m^2)\) operations.

Thus \(O((\tau+1)m^2L^2)\) bit operations is a valid uniform verification bound. This proves membership in \(\mathrm{NP}\).

The enumeration bound \(O(m!(\tau+1)m^2L^2)\) is also valid and is polynomial when \(m\) is fixed.

Finding: The bit-complexity argument establishes the claimed membership and running times.

6. Assignment resolution and repair feedback

The output resolves the assignment for every listed protocol. Hardness already holds on the restricted normalized family, with the controlled bloc submitting exactly one common report. The support representation and rational masses do not invalidate the transfer.

No additional mathematical clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩