The complexity of manipulative attacks in nearly single-peaked electorates (d4-journals-ai-2014-0016)

Given disjoint finite candidate sets \(C\) and \(A\), preferred candidate \(p\in C\), bound \(K\), societal axis \(L\), and a finite-support rational distribution \(\mu\) over complete rankings of \(C\cup A\), with every supported ranking swoon-SP with respect to \(L\), does there exist \(A'\subseteq A\) with \(|A'|\le K\) such that \(p\) is a plurality winner after restricting every ranking to \(C\cup A'\)?

Let \(C\) and \(A\) be disjoint finite candidate sets, \(p\in C\), \(K\) a nonnegative integer, and \(L\) a linear order on \(C\cup A\). The input also lists a finite-support distribution \(\mu\) over complete rankings of \(C\cup A\), with rational masses encoded in binary. A ranking is swoon-SP with respect to \(L\) if, after removing its top-ranked candidate from both the ranking and \(L\), the remaining ranking is single-peaked with respect to the restricted axis. Every ranking in the support must be swoon-SP.
For \(A'\subseteq A\), restrict each ranking to \(C\cup A'\). A candidate’s plurality score is the total \(\mu\)-mass of rankings that place it first after restriction; ties for the highest score count as wins.

Is deciding whether some \(A'\subseteq A\) with \(|A'|\le K\) makes \(p\) a plurality winner NP-hard or in \(\mathrm{P}\)?

For finite voter lists, this candidate-addition problem under swoon-SP preferences is NP-complete ([Faliszewski et al.](https://arxiv.org/pdf/1105.5032)). No classification of the stated rational-mass formulation was verified.

Classification

The problem is \(\mathrm{NP}\)-complete. The finite-voter hardness result transfers by assigning each distinct ranking its relative frequency. This preserves every plurality comparison after every permitted candidate addition.

1. The known hardness result applies

Theorem 4.7 of [Faliszewski, Hemaspaandra, and Hemaspaandra](https://arxiv.org/pdf/1105.5032) establishes \(\mathrm{NP}\)-completeness of constructive control by adding candidates for plurality in swoon-SP societies. Its conventions match the present problem:

• Voters are explicitly listed and rank all registered and additional candidates.
• The common axis is supplied as input.
• Deleting each voter’s first-ranked candidate leaves a ranking single-peaked on the restricted axis.
• At most the specified number of candidates may be added.
• Ties for highest plurality score count as wins.

These conventions appear in Section 2; the hardness proof appears in Appendix C.2. Thus we may use that finite-voter problem as the source of a polynomial-time many-one reduction.

2. Reduction to rational masses

Let a source instance have candidate sets \(C,A\), distinguished candidate \(p\), budget \(K\), axis \(L\), and an explicit list of \(n>0\) rankings
\[ R_1,\ldots,R_n. \]
Keep \(C,A,p,K,L\) unchanged. For each distinct ranking \(R\) appearing in the list, let
\[ m_R=\left|\{i\in\{1,\ldots,n\}:R_i=R\}\right|, \qquad \mu(R)=\frac{m_R}{n}. \]
Here and below, displayed formulas denote the same mathematics as their inline versions.

The masses are positive rationals and sum to \(1\), since every voter contributes to exactly one multiplicity. Each support ranking is an original ranking, so it remains swoon-SP with respect to \(L\).

There are at most \(n\) support rankings. Each numerator and denominator requires \(O(\log(n+1))\) bits. Grouping identical rankings and computing their multiplicities takes polynomial time in the explicit source input size. Hence this construction has polynomial running time and output length.

To verify correctness, fix any \(A'\subseteq A\), and put \(S=C\cup A'\). For \(c\in S\), let \(v_S(c)\) be its plurality score in the source election restricted to \(S\). Let \(\operatorname{top}_S(R)\) denote the highest-ranked member of \(S\) in \(R\). Its score in the constructed instance is
\[ s^\mu_S(c) =\sum_{\substack{R\in\operatorname{supp}(\mu)\\ \operatorname{top}_S(R)=c}}\frac{m_R}{n} =\frac{v_S(c)}{n}. \]
The last equality holds because \(m_R\) counts exactly the source voters with ranking \(R\).

Consequently, for every \(c\in S\),
\[ s^\mu_S(p)\ge s^\mu_S(c) \quad\Longleftrightarrow\quad v_S(p)\ge v_S(c), \]
because \(n>0\). Thus \(p\) wins for exactly the same subsets \(A'\). The budget is unchanged, proving equivalence of the two decision instances.

For completeness, if the source permits an empty voter list, every candidate has score \(0\), so that source instance is affirmative. Map it to the fixed affirmative instance \(C=\{p\}\), \(A=\varnothing\), \(K=0\), with mass \(1\) on the sole ranking. This ranking is swoon-SP because its remainder is empty.

The reduction proves \(\mathrm{NP}\)-hardness.

3. Membership in \(\mathrm{NP}\)

A certificate is a subset \(A'\subseteq A\), represented by a bit vector of length \(|A|\). Verify \(|A'|\le K\), then scan each support ranking to find its highest-ranked candidate in \(C\cup A'\).

Exact score comparisons require only polynomial-time integer arithmetic. Write the input masses as \(a_i/b_i\), with \(b_i>0\), and define
\[ D=\prod_{i=1}^{t}b_i, \qquad w_i=a_i(D/b_i). \]
The bit length of \(D\) is at most \(1+\sum_i\log_2 b_i\), hence polynomial in the input length. Each \(w_i\), and each sum of at most \(t\) such integers, also has polynomial bit length.

For each candidate, sum the \(w_i\) belonging to rankings that select it after restriction. These integer scores equal its rational plurality score multiplied by the same positive number \(D\). Comparing them therefore verifies precisely whether \(p\) is a winner, in polynomial time.

If malformed inputs must be rejected rather than excluded by a promise, validity is also polynomial-time checkable. In particular, after removing a ranking’s top candidate, single-peakedness on the supplied axis is equivalent to the absence of a triple \(x<_L y<_L z\) for which both \(x\) and \(z\) are ranked above \(y\). Enumerating all triples verifies this condition.

Combining membership with the reduction establishes \(\mathrm{NP}\)-completeness.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The output establishes \(\mathrm{NP}\)-completeness for the stated finite-support, binary-encoded rational-mass formulation. No major or minor mathematical issues were found.

• The cited hardness theorem applies.

Theorem 4.7 establishes \(\mathrm{NP}\)-completeness of constructive control by adding candidates for plurality over swoon-SP societies. Section 2 confirms all five conventions asserted by the prover: explicitly listed complete rankings, a supplied axis, the specified top-deletion definition, an upper bound on additions, and nonunique-winner semantics. Appendix C.2 contains the claimed hardness proof. Thus there is no mismatch in the source problem or its hypotheses. [Verified source](https://arxiv.org/pdf/1105.5032)

• The constructed distribution is valid.

For \(\,n>0\,\), every multiplicity satisfies \(\,1\le m_R\le n\,\), and the multiplicities sum to \(\,n\,\). Consequently, the masses \(\,\mu(R)=m_R/n\,\) are positive and sum to one. The support contains only original rankings, and the axis is unchanged, so the required swoon-SP property is preserved.

• The reduction has polynomial size and running time.

The source lists voters explicitly, so using at most \(\,n\,\) support rankings is polynomial in the source input length. Numerators and denominators have the stated \(\,O(\log(n+1))\,\) bit bound. Grouping identical rankings and computing multiplicities are polynomial-time operations. No expansion of binary-encoded multiplicities is involved.

• The score identity is correct for every allowed restriction.

For every \(\,A'\subseteq A\,\) and every \(\,c\in C\cup A'\,\), the stated identity \(\,s^\mu_{C\cup A'}(c)=v_{C\cup A'}(c)/n\,\) follows exactly from grouping voters with identical complete rankings. The highest-ranked surviving candidate is well-defined because \(\,p\in C\,\), so the restricted candidate set is nonempty.

Multiplication by the same positive factor preserves all weak score comparisons, including ties and comparisons against added candidates. Since the candidate sets and budget are unchanged, the equivalence holds for precisely the feasible subsets required by the task.

• The empty-voter edge case is handled correctly.

An empty source electorate makes every registered candidate a winner. The specified fixed affirmative target instance is valid; deleting its sole candidate leaves an empty ranking and axis, satisfying single-peakedness vacuously.

• The certificate and arithmetic establish membership in \(\mathrm{NP}\).

The subset certificate has polynomial length, and its budget and induced top choices can be checked in polynomial time. The common denominator \(\,D=\prod_i b_i\,\) has polynomial bit length, despite potentially having large numerical value. Each division \(\,D/b_i\,\) is exact, and the resulting weights and score sums also have polynomial bit length. Therefore exact winner verification uses polynomial-time arithmetic.

• The validity-checking claim is sound.

For strict complete rankings, the stated forbidden-triple condition correctly characterizes single-peakedness on a fixed axis. Applying it after deleting the top candidate checks the required property, including cases with fewer than three remaining candidates. The other input-validity checks are routine finite-list and rational-arithmetic checks; their omission as explicit algorithms is not a substantive gap.

No additional clarification or repair is needed. The conclusion concerns exactly the explicitly listed rational distribution in the task; it does not depend on expanding that distribution into a voter list.

⟨structured verdict parsed — rendered above⟩