Multimode Control Attacks on Elections (d4-conf-ijcai-2009-0266)

Given disjoint finite candidate sets \(C\) and \(A\), a target \(p\in C\), a budget \(k\), and a rational distribution \(\mu\) over complete rankings of \(C\cup A\), does there exist \(S\subseteq A\) with \(|S|\le k\) such that, after restricting every ranking to \(C\cup S\), \(p\) is the unique maximin winner, meaning \(\operatorname{mm}_{\mu,S}(p)>\operatorname{mm}_{\mu,S}(c)\) for every \(c\in(C\cup S)\setminus\{p\}\), where \(\operatorname{mm}_{\mu,S}(c)=\min_{d\ne c}\sum_t\mu_t\mathbf{1}[c\succ_t d]\)?

The input consists of disjoint finite candidate sets \(C\) and \(A\), a preferred candidate \(p\in C\), an integer budget \(k\), and an explicitly listed rational distribution \(\mu\) over complete rankings of \(C\cup A\). For \(S\subseteq A\), restrict each ranking to \(C\cup S\). A candidate \(c\) has maximin score \(\min_{d\in(C\cup S)\setminus\{c\}}\sum_t\mu_t\mathbf{1}[c\succ_t d]\); \(p\) is the unique winner if its score strictly exceeds every other score. If \(p\) is the sole candidate, it is the unique winner.

Is deciding whether some \(S\subseteq A\) with \(|S|\le k\) makes \(p\) the unique winner in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For a finite list of unweighted voters, this candidate-addition problem is NP-hard. No separately published result for the stated rational-distribution formulation was verified.

The problem is \(\mathrm{NP}\)-hard under the supplied premise. In fact, it is \(\mathrm{NP}\)-complete. Normalizing voter counts into a rational probability distribution gives a polynomial-time reduction that preserves every successful candidate addition.

Reduction from the stated unweighted problem.

Use the supplied premise that the same candidate-addition problem, with a unique-winner requirement and an upper-bound budget, is \(\mathrm{NP}\)-hard for an explicitly listed collection of unweighted voters.

Consider such an instance with candidate sets \(C,A\), preferred candidate \(p\), budget \(k\), and complete rankings \(R_1,\ldots,R_N\), where \(N\geq 1\). Construct a rational-distribution instance with the same \(C,A,p,k\). For each distinct ranking \(R\) occurring in the voter list, let \(m_R\) be its multiplicity and set
\[ \mu(R)=\frac{m_R}{N}. \]
These probabilities are nonnegative and sum to \(1\), so they form a valid explicitly listed rational distribution.

The construction takes polynomial time: one can group identical rankings by direct comparisons. There are at most \(N\) distinct rankings, and each numerator and denominator requires \(O(\log(N+1))\) bits. Thus the output length is polynomial in the explicit source-input length.

Preservation of the winner condition.

Fix any \(S\subseteq A\) and write \(B=C\cup S\). For distinct candidates \(c,d\in B\), let
\[ V(c,d)=\bigl|\{i\in\{1,\ldots,N\}:c\succ_{R_i}d\}\bigr|. \]
Restricting a ranking to \(B\) does not change the relative order of \(c\) and \(d\). Consequently, their pairwise support in the constructed distribution is
\[ \sum_R\mu(R)\mathbf{1}[c\succ_R d] =\sum_R\frac{m_R}{N}\mathbf{1}[c\succ_R d] =\frac{V(c,d)}{N}. \]

When \(|B|\geq 2\), denote the unweighted and distributional maximin scores by \(s_V(c;B)\) and \(s_\mu(c;B)\), respectively. Because \(N>0\),
\[ s_\mu(c;B) =\min_{d\in B\setminus\{c\}}\frac{V(c,d)}{N} =\frac{1}{N}\min_{d\in B\setminus\{c\}}V(c,d) =\frac{s_V(c;B)}{N}. \]
Multiplication by the same positive constant preserves all strict inequalities. Hence, for every \(c\in B\setminus\{p\}\),
\[ s_\mu(p;B)>s_\mu(c;B) \quad\Longleftrightarrow\quad s_V(p;B)>s_V(c;B). \]
If \(B=\{p\}\), then \(p\) is the unique winner in both formulations. Thus every feasible \(S\) succeeds in the source instance exactly when it succeeds in the constructed instance. Since the budget is unchanged, this proves a polynomial-time many-one reduction and establishes \(\mathrm{NP}\)-hardness.

Empty voter lists do not affect this argument: with no voters, every score in a field of at least two candidates is zero, so those source instances are directly decidable and can be mapped to fixed yes- or no-instances.

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

A certificate is a subset \(S\subseteq A\). Check \(|S|\leq k\), compute all pairwise supports among \(C\cup S\), take each candidate’s minimum, and check that \(p\)’s score strictly exceeds every other score. Handle \(C\cup S=\{p\}\) using the stated convention.

These computations take polynomial time with exact rational arithmetic. Explicitly, write each listed weight as \(a_t/b_t\), with \(b_t>0\), and use the common denominator
\[ Q=\prod_t b_t. \]
Its binary length is at most \(1+\sum_t\log_2 b_t\), which is polynomial in the input length. Each pairwise support has integer numerator
\[ \sum_t a_t(Q/b_t)\mathbf{1}[c\succ_t d]. \]
All these integers have polynomial bit length, so their computation and comparison take polynomial time.

Therefore the stated problem is \(\mathrm{NP}\)-complete. The hardness conclusion uses the supplied unweighted hardness result; it does not require a separately published theorem for rational distributions.

⟨structured verdict parsed — rendered above⟩

The argument is correct under the supplied unweighted hardness premise. It establishes \(\mathrm{NP}\)-hardness by a polynomial-time reduction and establishes membership in \(\mathrm{NP}\), hence \(\mathrm{NP}\)-completeness. No repair is needed.

• Use of the supplied premise. The prover explicitly identifies the source problem as the same candidate-addition problem with a unique-winner requirement and an upper-bound budget. This matches the premise in USER_TASK. The hardness conclusion is appropriately conditional on that supplied premise; no separately published result about rational distributions is needed.

• Validity and size of the construction. For a nonempty voter list, each multiplicity satisfies \(m_R>0\), and the multiplicities sum to \(N\). Thus the weights \(m_R/N\) define a probability distribution. There are at most \(N\) listed rankings, and every numerator and denominator has \(O(\log(N+1))\) bits. Grouping identical explicitly listed rankings by comparisons takes polynomial time. Both construction time and output size are therefore polynomial in the source-input length.

• Preservation of pairwise supports. For any fixed addition set \(S\), restricting rankings preserves the relative order of every pair of retained candidates. Grouping voters by their complete rankings therefore gives exactly the asserted pairwise support \(V(c,d)/N\). This identity applies to all distinct retained candidates and every choice of \(S\).

• Preservation of maximin scores and unique winners. When \(|C\cup S|\geq 2\), each minimum is over a nonempty finite set. Since \(N>0\), division by \(N\) commutes with taking that minimum and preserves every strict score comparison. Consequently, \(p\) is the unique winner for precisely the same addition sets in both instances. The singleton case is explicitly handled using the stated convention.

• Budgets and reduction correctness. The construction leaves \(C,A,p,k\) unchanged, so the feasible addition sets coincide. Together with winner preservation, this proves both directions of the required yes-instance equivalence. If negative integer budgets are admitted, neither instance has a feasible addition set, so the equivalence still holds.

• Empty voter lists. The separate treatment is valid. With no voters, all scores in any field containing at least two candidates are zero. Under the singleton convention, success is possible exactly when \(C=\{p\}\) and \(k\geq 0\). These cases are directly decidable. Mapping them to fixed yes- or no-instances is a routine valid completion of the reduction; the omission of explicit fixed instances is not a substantive gap.

• Certificate and verification. A subset of \(A\) has a polynomial-length encoding. Its budget feasibility can be checked in polynomial time, as can all pairwise supports, minima, and strict comparisons. The singleton case is handled separately, avoiding an undefined minimum.

• Exact arithmetic complexity. The proposed denominator \(Q=\prod_t b_t\) is a positive integer whose binary length is at most \(1+\sum_t\log_2 b_t\). Each quotient \(Q/b_t\) is integral. The products and sums defining the support numerators have polynomial bit length, and their number is polynomial because both candidates and distribution entries are explicitly listed. Standard integer arithmetic therefore performs the verification in polynomial time. The argument does not confuse a potentially large numerical denominator with a large binary encoding.

The output resolves the assigned complexity question and justifies its stronger completeness claim. There are no blocking issues or required clarifications.

⟨structured verdict parsed — rendered above⟩