Complexity of Strategic Behavior in Multi-Winner Elections (d4-journals-jair-2008-0007)

Given candidates \(C\), committee size \(k\), distinguished candidate \(p\), rational type masses \(\mu_t\), integral Bloc ballots \(B_t\subseteq C\) with \(|B_t|=k\), and rational budget \(\rho\), does there exist \(x_t\) with \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le\rho\) such that \(S_x(c)=\sum_t(\mu_t-x_t)\mathbf{1}[c\in B_t]\) makes \(p\) one of the \(k\) winners under adversarial tie-breaking?

Let \(C\) be a candidate set, \(1\le k\le |C|\), and \(p\in C\). Each explicitly listed type \(t\) has a nonnegative rational mass \(\mu_t\) and a Bloc ballot \(B_t\subseteq C\) with \(|B_t|=k\). A controller may remove mass \(x_t\) from each type, where \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le\rho\). The remaining score of \(c\) is \(S_x(c)=\sum_t(\mu_t-x_t)\mathbf{1}[c\in B_t]\). Ties are broken against \(p\): it wins exactly when fewer than \(k\) other candidates have score at least \(S_x(p)\). All rational inputs are binary encoded.

Is deciding whether such a removal makes \(p\) a winner in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?

For indivisible voters, constructive control by removing voters under Bloc is \(\mathrm{NP}\)-complete. That result does not classify removal of divisible type masses.

Result

The problem is \(\mathrm{NP}\)-complete. The reduction below explicitly allows arbitrary fractional removals.

1. Removing mass from ballots containing the preferred candidate is unnecessary

For any removal vector \(x\), define \(\widehat{x}\) by restoring all removed mass from types whose ballots contain \(p\), while leaving other removals unchanged. This decreases the total removed mass.

For every candidate \(c\ne p\),
\[ S_{\widehat{x}}(c)-S_{\widehat{x}}(p) = S_x(c)-S_x(p) - \sum_{t:p\in B_t}x_t\bigl(1-\mathbf{1}[c\in B_t]\bigr). \]
Every summand is nonnegative. Consequently, every candidate strictly below \(p\) under \(x\) remains strictly below \(p\) under \(\widehat{x}\).

Thus, if a successful removal exists, one exists that removes mass only from ballots not containing \(p\).

2. Reduction from Clique

We use the following standard \(\mathrm{NP}\)-complete problem: given a finite simple graph \(G\) and an integer \(\ell\), determine whether \(G\) contains a clique of size \(\ell\). We may restrict to \(3\le\ell\le |V(G)|\): excluded cases are polynomial-time decidable and can be mapped to fixed yes- or no-instances satisfying this restriction.

Write \(m=|E(G)|\), and set
\[ q=\binom{\ell}{2}, \qquad R=2q(\ell+1)+q. \]
Form \(H\) by adding \(R\) disjoint edges to \(G\), using new vertices and no other new edges. Let
\[ n=|E(H)|=m+R, \qquad k=n-q+1, \qquad \varepsilon=\frac{2q}{n}. \]
Since \(n>2q(\ell+1)\), we have
\[ 0<\varepsilon<\frac{1}{\ell+1}. \]

Every original vertex has degree at most \(m\), and every new vertex has degree one. Moreover,
\[ k=m+2q(\ell+1)+1, \]
so every vertex of \(H\) has degree at most \(k\).

Because \(\ell\ge3\), none of the added isolated edges can participate in a clique of size \(\ell\). Hence \(H\) has such a clique exactly when \(G\) does.

Election construction

The candidates are:

• the preferred candidate \(p\);
• one candidate \(a_e\) for each edge \(e\in E(H)\);
• private filler candidates introduced below.

There are two families of types.

Vertex types. For each vertex \(v\in V(H)\), create a type of mass \(1\). Its ballot contains all edge candidates corresponding to edges incident with \(v\), together with \(k-\deg_H(v)\) private filler candidates.

Each filler candidate appears in exactly this one ballot. Every vertex ballot has size \(k\) and excludes \(p\).

Types containing \(p\). Enumerate the edges cyclically as \(e_0,\ldots,e_{n-1}\). For each index \(i\), create a type of mass \(2/n\) with ballot
\[ B_i=\{p\}\cup \{a_{e_j}:j\notin\{i,i+1,\ldots,i+q-1\}\pmod n\}. \]
Here the omitted indices are taken modulo \(n\). Since \(q<n\), this ballot contains exactly \(1+n-q=k\) candidates.

Set the removal budget to \(\rho=\ell\).

The construction is polynomial in the input size. Indeed, \(R=O(\ell^3)\), and \(\ell\le |V(G)|\). There are \(n+|V(H)|\) explicitly listed types, each with \(k\) approvals, and at most \(|V(H)|k\) filler candidates. All masses and the budget have polynomial binary encoding length.

3. What a fractional removal can accomplish

By Section 1, we may restrict attention to removals from vertex types. Denote the mass removed from vertex \(v\)'s type by \(x_v\). The constraints are
\[ 0\le x_v\le1, \qquad \sum_{v\in V(H)}x_v\le\ell. \]

The score of \(p\) is exactly \(2\). Every filler candidate has score at most \(1\), and therefore is strictly below \(p\).

Each edge candidate appears in exactly \(n-q\) of the types containing \(p\). For an edge \(e=\{u,v\}\), its remaining score is consequently
\[ S_x(a_e) = \frac{2(n-q)}{n}+(1-x_u)+(1-x_v) = 4-\varepsilon-x_u-x_v. \]
It is strictly below \(p\) exactly when
\[ x_u+x_v>2-\varepsilon. \tag{1} \]

Let \(b\) be the number of edge candidates strictly below \(p\). The only candidates that can tie or exceed \(p\) are the other \(n-b\) edge candidates. Therefore,
\[ p\text{ wins} \quad\Longleftrightarrow\quad n-b<k=n-q+1 \quad\Longleftrightarrow\quad b\ge q. \tag{2} \]

A bound that applies to arbitrary fractional removals

Define
\[ U=\{v\in V(H):x_v>1-\varepsilon\}. \]

If an edge satisfies (1), both its endpoints belong to \(U\). For example, since \(x_v\le1\),
\[ x_u>2-\varepsilon-x_v\ge1-\varepsilon, \]
and the same argument applies to \(x_v\).

Furthermore, \(|U|\le\ell\). Otherwise, the budget would satisfy
\[ \sum_v x_v > (\ell+1)(1-\varepsilon) > \ell, \]
where the last strict inequality follows from \(\varepsilon<1/(\ell+1)\). This contradicts feasibility.

Thus every edge candidate strictly below \(p\) corresponds to an edge induced by a set of at most \(\ell\) vertices. This conclusion does not assume that removals are integral.

4. Correctness of the reduction

A clique gives a successful removal

Suppose \(H\) contains a clique \(K\) of size \(\ell\). Remove the full unit mass from each vertex type corresponding to \(K\), using total budget \(\ell\).

For each of the \(q\) edges inside \(K\), both endpoint removals equal \(1\), so its candidate's score is
\[ 4-\varepsilon-2=2-\varepsilon<2=S_x(p). \]
Hence at least \(q\) edge candidates are strictly below \(p\), and (2) implies that \(p\) wins.

A successful fractional removal gives a clique

Suppose a successful removal exists. Restore all removals from types containing \(p\), as justified in Section 1.

By (2), at least \(q\) edge candidates are strictly below \(p\). All corresponding edges have both endpoints in the set \(U\) defined above, with \(|U|\le\ell\). Since \(H\) is simple,
\[ q \le |E(H[U])| \le \binom{|U|}{2} \le \binom{\ell}{2} =q. \]
All inequalities must therefore be equalities. Because \(\ell\ge3\), equality forces \(|U|=\ell\), and the induced graph \(H[U]\) contains every possible edge. Thus \(U\) is a clique of size \(\ell\).

As observed earlier, such a clique lies in \(G\). This proves \(\mathrm{NP}\)-hardness.

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

Let \(M=|C|\). The winning condition is equivalent to having at least \(M-k\) other candidates strictly below \(p\).

Guess a subset \(D\subseteq C\setminus\{p\}\) of size \(M-k\). For this choice, consider the rational linear program that maximizes \(\delta\), subject to
\[ 0\le x_t\le\mu_t,\qquad \sum_t x_t\le\rho,\qquad 0\le\delta\le1, \]
and
\[ S_x(p)-S_x(c)\ge\delta \qquad\text{for every }c\in D. \]

For a nonempty \(D\), all its candidates can be placed strictly below \(p\) exactly when this program is feasible with positive optimum: finitely many positive score gaps have a positive minimum, which can be capped at \(1\). If \(D\) is empty, the score constraints are vacuous, and any feasible removal allows \(\delta=1\).

We use the standard polynomial-time solvability theorem for rational linear programming. Its hypotheses hold here: the constraints and objective have rational coefficients of polynomial encoding length, there are polynomially many variables and constraints, and every variable is bounded. Thus infeasibility or positivity of the exact optimum can be decided in polynomial time.

The guessed subset has polynomial size, and its verification is polynomial-time. Therefore the problem belongs to \(\mathrm{NP}\), completing the proof of \(\mathrm{NP}\)-completeness.

⟨structured verdict parsed — rendered above⟩

The output correctly proves that the problem is \(\mathrm{NP}\)-complete, including when arbitrary fractional removals are allowed. I found no major or minor issues.

• Restoring mass on ballots containing \(p\). The score-difference identity is correct: restoring mass on such a ballot increases \(p\)'s score and increases another candidate's score only if that candidate also appears on the ballot. Consequently, every previously strict score advantage of \(p\) is preserved. Restoration also preserves the removal bounds and cannot increase the budget used. The restriction to removals from ballots excluding \(p\) is therefore justified.

• Graph construction and parameter bounds. Restricting Clique to \(3\le\ell\le |V(G)|\) preserves NP-hardness as stated. The added components contain only two vertices each, so they cannot contribute to an \(\ell\)-clique.

The arithmetic is correct: \(n=m+2q(\ell+1)+q\), hence \(k=m+2q(\ell+1)+1\). In particular, \(q>0\), \(q<n\), and \(0<\varepsilon<1/(\ell+1)\). Original vertex degrees are at most \(m\), and added vertex degrees are one, so all required filler counts are nonnegative.

• Validity and size of the election. Every vertex ballot has exactly \(k\) candidates. Every ballot containing \(p\) omits exactly \(q\) distinct edge candidates and therefore also has exactly \(k\) candidates. Private fillers introduce no unintended score contributions. There are already \(n+1\) candidates before adding fillers, so the required condition \(1\le k\le |C|\) holds.

The construction is polynomial in size: \(\ell\le |V(G)|\) bounds the number of added edges polynomially, and the explicitly listed ballots and private fillers also have polynomial total size. The masses \(1\) and \(2/n\), and budget \(\ell\), have polynomial binary encoding length.

• Scores and the winning threshold. After the justified restoration, \(p\)'s score is exactly \(2\), and each filler has score at most \(1\). Each edge candidate is omitted from exactly \(q\) cyclic ballots and included in exactly two vertex ballots. Thus its score is correctly computed as \(4-\varepsilon-x_u-x_v\).

The strict comparison \(x_u+x_v>2-\varepsilon\) correctly implements ties being broken against \(p\). Since only edge candidates can tie or exceed \(p\), the winning condition is exactly \(n-b<n-q+1\), equivalently \(b\ge q\). The integer threshold is handled correctly.

• The bound for fractional removals. If an edge candidate is strictly below \(p\), the bound \(x_v\le1\) forces \(x_u>1-\varepsilon\), and symmetrically for the other endpoint. Therefore both endpoints belong to \(U\).

If \(U\) had at least \(\ell+1\) vertices, their removals alone would sum to more than \((\ell+1)(1-\varepsilon)>\ell\). Both strict inequalities are justified. Hence \(|U|\le\ell\). This argument applies to arbitrary real feasible removals and does not silently assume integrality.

• Both directions of the reduction. An \(\ell\)-clique supplies a feasible removal of total mass \(\ell\), placing its \(q\) edge candidates strictly below \(p\).

Conversely, success supplies at least \(q\) edges induced by \(U\). The displayed chain bounding their number by \(\binom{|U|}{2}\le\binom{\ell}{2}=q\) is valid because the graph is simple. Equality forces \(|U|=\ell\) and all possible edges within \(U\). The restriction \(\ell\ge3\) then excludes every added two-vertex component. The extracted clique therefore lies in \(G\).

• Membership in NP. The required number of other candidates strictly below \(p\) is correctly stated as \(M-k\). Guessing such a subset has polynomial certificate size.

For nonempty \(D\), simultaneous strict score inequalities are equivalent to feasibility with a positive common margin \(\delta\); finiteness of \(D\) justifies taking the minimum positive gap. The cap \(\delta\le1\) does not affect this equivalence. The empty case, including \(k=M\), is explicitly and correctly handled.

The invoked rational linear-programming theorem provides polynomial-time feasibility and exact optimization for explicitly encoded rational programs. Its application is justified: the score expressions are affine with polynomial-length rational coefficients, the program has polynomially many variables and constraints, and all variables are bounded. Thus testing whether the optimum is positive is a valid polynomial-time verification procedure. No assumption about a numerical tolerance or an unencoded real certificate is needed.

No additional clarification or repair is required.

⟨structured verdict parsed — rendered above⟩