Proof: **As demonstrated in the case of bribery, we represent the candidates as vertices and the voters by**
edges. The reduction is to Simple b**-Edge Matching of Multigraphs, in this case.**
Consider the case of control by adding at most q **unweighted voters in 3-approval elections. Without loss**
of generality, we will add exactly q voters, all of which approve p. The final score of p is thus s(p) + q**, where**
s(p) is the initial score of p. For each candidate c ∈ p, we may add at most s(p) + q − s(c**) voters approving**
c.

Each voter that is added also approves two other candidates. In this case, each voter corresponds to an edge between the two other candidates, and we must find q **edges such that each vertex corresponding to** the candidate c is covered by at most s(p) + q − s(c) edges, giving us q **voters that can be added without** exceeding this score. This corresponds to the problem of Simple b**-Edge Matching of Multigraphs, which is**
polynomial-time computable.

A similar reduction will also show that 3-veto elections are vulnerable to control by deleting voters.

Theorem 16 k**-approval elections are computationally resistant to constructive control by adding voters for**
k ≥ 4.

Proof: **We begin by showing that 4-approval control by adding voters is NP-hard and extend it to**
k-approval for k > 4.

Let S = {s1**, . . . , s**3m}
and T1 = {t1,1, t1,2, t1,3}, . . . , Tn = {tn,1, tn,2, tn,3}
be an instance of X3C.

Without loss of generality, we can assume that 4 divides 3m**, by adding at most 4 dummy sets to our**
instance. We define our candidate set C = {p} ∪ {s1**, . . . , s**3m}.

We assign votes to V such that initially p receives no approvals and si receives m − **1 approvals for each**
1 ≤ i ≤ 3m. Note that this construction is possible provided that 4 divides 3m. There are thus 3m + 1 candidates and 3m(m−1)
4**voters.**
For each set Ti = {ti,1, ti,2, ti,3} **in our instance of X3C, we add an unestablished voter** vi to V
′ **which**
approves of {p, ti,1, ti,2, ti,3}. We show that our instance of X3C has an exact covering if and only if **there**
exists a control of this election by adding m **new voters.**
Consider an exact 3-set covering. Adding the votes that correspond to the m **3-sets of this covering would**
add one approval to each of si and m approvals to p, giving each candidate exactly m **approvals. Thus,** p becomes a winner. Conversely, consider a successful control that adds at most m **new voters and makes** p a winner. Since each si candidate currently has m − **1 approvals and all votes approve of at least one such**
candidate, we see that we must add exactly m new voters to potentially make p **a winner. However, in such**
a case, p will end up with m approvals, so none of the si **candidates can receive two new approvals, as this**
would give that candidate m **+ 1 approvals. This corresponds to a solution to the X3C instance.**