d4-conf-aaai-2012-0190 (d4-conf-aaai-2012-0190)

Given a candidate set \(C\), a fixed tie-breaking order, target \(p\), rational strategic mass \(\epsilon>0\), truthful ranking \(t^\star\), and a rational nonstrategic mass profile \(\nu\) over complete rankings with total mass \(1-\epsilon\), is there a ranking \(r\) such that \(p\) wins when \(\operatorname{eliminate}(\mathrm{veto})\) is run on \(\nu+\epsilon\delta_r\)? Each round eliminates the remaining candidate with the greatest mass ranked last, using the given tie-breaker. The initial society is \(\nu+\epsilon\delta_{t^\star}\); the strategic cohort of mass \(\epsilon\) submits one common report.

Let \(C\) contain \(m\geq2\) candidates, with target \(p\in C\) and a supplied strict total order for breaking elimination ties. Types are strict complete rankings of \(C\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible rankings.
The input supplies a nonnegative nonstrategic profile \(\nu\), rational \(0<\epsilon\leq1\) with \(\sum_t\nu(t)=1-\epsilon\), and a truthful ranking \(t^\star\). The initial society is \(\nu+\epsilon\delta_{t^\star}\), where \(\delta_t\) places unit mass on ranking \(t\); let \(\tau\) denote this society's support size and \(L\) the total input bit length.
The strategic cohort replaces its entire mass by one strict complete report \(r\), producing \(\nu+\epsilon\delta_r\). This report is fixed throughout the election; \(r=t^\star\) is allowed, and no improvement over the truthful outcome is required.
Under \(\operatorname{eliminate}(\mathrm{veto})\), restrict every ranking to the remaining candidates in each round and eliminate the candidate with greatest total mass ranking it last; among tied candidates eliminate the earliest in the supplied order. Continue until one candidate remains, who wins.

Is deciding whether some report \(r\) makes \(p\) win solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finite unweighted electorates, deciding whether one manipulator can make a designated candidate win under this elimination rule is NP-complete. [Source](https://arxiv.org/pdf/1204.3918).
No result explicitly treating this rational-mass, common-report formulation was located in the literature search.

Result

The decision problem is \(\mathrm{NP}\)-complete. The finite one-manipulator problem embeds into the stated rational-mass model by normalization. This embedding preserves the entire elimination sequence, including ties, and has polynomial output size.

1. The finite hardness theorem applies

We use the following known result:

Finite one-manipulator theorem. Given strict complete rankings of finitely many nonstrategic, unweighted voters and a designated candidate \(p\), deciding whether one additional voter can submit a strict complete ranking making \(p\) win under \(\operatorname{eliminate}(\mathrm{veto})\) is \(\mathrm{NP}\)-complete.

This is Theorem 3 of Davies, Narodytska, and Walsh. Their rule uses one fixed ballot per voter and eliminates until one candidate remains. Their hardness construction explicitly specifies a fixed tie-breaking priority, which can be supplied as the order in our instance. Thus neither adaptive reporting nor strategic selection among tied eliminations is needed. [Source: definitions and Theorem 3](https://arxiv.org/pdf/1204.3918#page=2), [fixed tie-breaking priority in the proof](https://arxiv.org/pdf/1204.3918#page=4).

We now give the reduction from this finite problem.

2. Constructing the rational-mass instance

Let the source instance have candidate set \(C\), target \(p\), nonstrategic rankings \(v_1,\ldots,v_n\), and fixed elimination tie order \(\prec\). We may restrict to the hard instances with \(n\geq1\).

For every ranking \(t\), define its multiplicity by \(a_t=|\{i:v_i=t\}|\). Construct the target instance using the same candidates, target, and tie order, and set

\( \epsilon=\frac{1}{n+1},\qquad \nu(t)=\frac{a_t}{n+1}. \)

Only rankings with \(a_t>0\) are listed in the support of \(\nu\). Choose any strict complete truthful ranking \(t^\star\), for example \(v_1\).

All required conditions hold:

• Every listed nonstrategic mass is positive and rational.
• The strategic mass satisfies \(0<\epsilon\leq1\).
• Since \(\sum_t a_t=n\), we have \(\sum_t\nu(t)=n/(n+1)=1-\epsilon\).
• The truthful ranking is supplied, and the strategic cohort may replace it by any strict complete ranking.

The truthful ranking imposes no additional restriction on the decision problem: the task explicitly allows every report, including \(t^\star\), and requires no improvement over the truthful outcome.

3. Every report preserves the elimination sequence

Fix any report \(r\). For a nonempty remaining candidate set \(S\subseteq C\), let \(\operatorname{last}_S(t)\) denote the candidate ranked last in the restriction of \(t\) to \(S\).

In the finite election, the last-place count of \(c\in S\), including the manipulator’s report, is

\( V_S(c;r)=\sum_{i=1}^{n}\mathbf{1}\{\operatorname{last}_S(v_i)=c\}+\mathbf{1}\{\operatorname{last}_S(r)=c\}. \)

In the constructed rational-mass election, its last-place mass is

\( M_S(c;r)=\sum_t\nu(t)\mathbf{1}\{\operatorname{last}_S(t)=c\}+\epsilon\mathbf{1}\{\operatorname{last}_S(r)=c\}=\frac{V_S(c;r)}{n+1}. \)

Multiplication by the positive constant \(1/(n+1)\) preserves every strict comparison and equality. Consequently, the candidates with greatest last-place mass are exactly those with greatest last-place count. Because both elections use the same tie order, they eliminate the same candidate whenever their remaining sets coincide.

Initially, both remaining sets equal \(C\). Induction over the rounds therefore shows that their complete elimination sequences coincide. In particular, for every report \(r\),

\( p\text{ wins in the finite election with }r\quad\Longleftrightarrow\quad p\text{ wins under }\nu+\epsilon\delta_r. \)

Taking the existential quantifier over all strict complete reports proves that the reduction preserves both yes-instances and no-instances.

4. Support and encoding bounds

Let \(s\) be the number of distinct nonstrategic rankings in the source instance. Aggregating identical rankings can be done in polynomial time.

Because we chose \(t^\star=v_1\), the initial society has exactly these \(s\) supported rankings. Thus \(\tau=s\leq n\); the construction does not enumerate the \(m!\) possible rankings.

Every mass has numerator at most \(n\) and denominator \(n+1\), each representable with \(O(\log(n+1))\) binary bits. Using candidate indices, the constructed input length is

\( L=O\!\left((s+1)m\log m+(s+1)\log(n+1)\right). \)

This is polynomial in the length of the explicitly listed finite source instance. Hence a polynomial-time algorithm in \(m,\tau,L\) for the target problem would solve the finite \(\mathrm{NP}\)-complete problem in polynomial time. The target problem is therefore \(\mathrm{NP}\)-hard.

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

A certificate is a strict complete report \(r\), encoded as a permutation of the \(m\) candidates. Its length is \(O(m\log m)\).

To verify it, first check that it is a permutation, then simulate the election exactly. There are \(m-1\) elimination rounds. In each round, scan each supported nonstrategic ranking and \(r\) to identify its last remaining candidate, add the corresponding masses, and apply the supplied tie order.

Exact rational arithmetic has polynomial bit complexity here. Write the nonstrategic masses and \(\epsilon\) as \(a_j/b_j\), and let \(Q=\prod_j b_j\). The binary length of \(Q\) is at most the sum of the binary lengths of the denominators, hence \(O(L)\). Replace each mass by the integer weight \(a_j(Q/b_j)\).

These weights sum to \(Q\), because the election’s total mass is one. Every last-place score is therefore an integer between zero and \(Q\), requiring \(O(L)\) bits. Integer comparisons preserve the rational comparisons and ties exactly. A straightforward simulation uses \(O(m^2(\tau+1))\) ranking-inspection operations and polynomially many bit operations.

Thus a winning report can be verified in polynomial time, proving membership in \(\mathrm{NP}\).

Conclusion

The rational-mass, common-report problem is \(\mathrm{NP}\)-complete, even on instances obtained by assigning the same mass \(1/(n+1)\) to each of \(n\) nonstrategic voters and the strategic cohort. A polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The normalization reduction establishes hardness for the exact common-report model in the task, and the certificate verification establishes membership in \(\mathrm{NP}\). No major or minor mathematical issues were found.

• The cited hardness theorem matches the required source problem.

Theorem 3 of Davies, Narodytska, and Walsh states that deciding whether a single manipulator can make a designated candidate win under \(\operatorname{eliminate}(\mathrm{veto})\) is \(\mathrm{NP}\)-complete. The paper distinguishes fixed ballots from voting afresh in each round. Its hardness construction specifies a tie priority with \(s_2\) preceding \(d_0\), then \(p\), then the item candidates; its subsequent tie arguments use that priority for elimination. Thus the citation supports fixed reporting and a supplied elimination tie order, rather than adaptive reports or discretionary tie resolution. [Definitions and Theorem 3, pages 2–4](https://arxiv.org/pdf/1204.3918).

The remaining candidates can be included in the source instance’s fixed total tie order. The target permits that order as input. The prover does not need hardness for every possible prescribed order.

• The constructed instance satisfies the task’s input conditions.

For explicitly listed nonstrategic voters, the multiplicities \(a_t\) are nonnegative integers summing to \(n\). Consequently,
\[ \epsilon=\frac{1}{n+1},\qquad \nu(t)=\frac{a_t}{n+1} \]
gives positive masses on exactly the listed supported rankings and satisfies
\[ \sum_t\nu(t)=\frac{n}{n+1}=1-\epsilon. \]

The restriction to source hardness instances with \(n\geq1\) is legitimate: the cited construction has nonstrategic voters. Hence choosing \(t^\star=v_1\) is well-defined. The construction also retains the source’s candidate set, designated candidate, complete rankings, and tie order.

The truthful ranking introduces no further winning or improvement condition under the stated task. Therefore its arbitrary choice within the nonstrategic support does not affect the reduction’s existential question.

• The score identity and elimination-sequence equivalence are correct.

For every fixed complete report \(r\), every nonempty remaining set \(S\), and every \(c\in S\), aggregation by ranking gives exactly
\[ M_S(c;r)=\frac{V_S(c;r)}{n+1}. \]

This identity includes the strategic contribution even when \(r\) coincides with an existing supported ranking. It also accounts correctly for restriction of every ballot to \(S\).

The factor is positive, so it preserves both strict comparisons and equalities. Thus the maximizing candidates coincide, and the shared tie order selects the same eliminated candidate. Starting from the same candidate set, the stated induction establishes identical remaining sets after every elimination and the same final survivor.

The equivalence holds separately for every report. Both problems quantify over the same complete rankings, so taking the existential quantifier preserves yes-instances and no-instances. There is no quantifier mismatch or change to the common-report requirement.

• The support and encoding bounds are valid.

Because \(t^\star=v_1\), adding the truthful strategic mass introduces no new ranking into the initial support. Hence \(\tau=s\leq n\), exactly as claimed.

Each constructed mass has numerator at most \(n\) and denominator \(n+1\). Reducing fractions, if required by the encoding, cannot increase their lengths. The stated bound
\[ L=O\bigl((s+1)m\log m+(s+1)\log(n+1)\bigr) \]
accommodates the supported rankings, their masses, the truthful ranking, the strategic mass, and the candidate and tie-order data.

Aggregation is polynomial in the explicitly listed source input. Neither the construction nor its size bound enumerates all possible rankings. Therefore the reduction is polynomial, and polynomial dependence on \(m,\tau,L\) would give polynomial time on the source instances.

• The membership argument uses polynomial-size exact arithmetic.

A permutation report has polynomial certificate length and can be checked for completeness and uniqueness.

Taking the product \(Q\) of the positive denominators produces a common denominator whose binary length is bounded by their total encoding length. Each scaled weight \(a_j(Q/b_j)\) is an integer. Nonnegativity and total mass one imply that the weights sum to \(Q\), so each round’s score lies between zero and \(Q\).

Thus all scores have \(O(L)\) bits, and integer comparisons preserve rational comparisons and ties exactly. Computing the weights and performing the simulation require polynomially many bit operations. The stated ranking-inspection bound is sufficient.

This reasoning also covers an empty nonstrategic profile when \(\epsilon=1\), and the election simulation correctly stops after \(m-1\) rounds, including when \(m=2\).

• The conclusion follows.

The reduction proves \(\mathrm{NP}\)-hardness, and the verifier proves membership in \(\mathrm{NP}\). Their combination establishes the claimed \(\mathrm{NP}\)-completeness. No additional lemma or clarification is needed.

⟨structured verdict parsed — rendered above⟩