
## 13 Weighted And Priced Cases Of Election Misuse

We examine the problem of manipulation, bribery, and control for the case of weighted elections and voters with price tags for bribery. In weighted elections, each voters is given a weight and the points assigned to each voter is scaled by that weight. In some bribery problems, there is a cost associated with bribing each voter, and we would like to find the cheapest bribery. We would like to determine the effect on the complexity of manipulation.

In [11] it is shown that a scoring protocol α = (α1, . . . , αm) is computationally vulnerable to manipulation by weighted voters if and only if α2 = . . . = αm **(i.e., basically, only for elections with behavior**
similar to plurality and the trivial system in which each candidate receives the same score). Thus, f(m)- approval weighted elections can be computationally vulnerable to manipulation if and only if f(m**) = 1 for** all m ≥ **1. We conclude that 1-approval (i.e., plurality) is the only approval-based scoring protocol that is**
computationally vulnerable to manipulation.

In bribery problems, voters can have both weights and prices. In this case, we pay a price for bribing each voter, and we have a budget q**. We may bribe as many votes as we want so long as this budget is not**
exceeded.

In [21] it is seen that weighted scoring protocols elections are computationally vulnerable to bribery iff α2 = . . . = αm, and vulnerable to $bribery iff α1 = . . . = αm**. Thus, 1-approval is also the only**
weighted approval-based scoring protocol that is computationally **vulnerable to bribery. No nontrivial** weighted approval-based scoring protocol are computationally vulnerable to $bribery.

Theorem 24 1-approval and 1**-veto (i.e., plurality and veto) elections are computationally vulnerable to**
constructive $**bribery.**
Proof: The case of $bribery for 1-approval is shown in [21]. In 1-veto, as **in the unweighted case, we**
must bribe voters vetoing p and give the vetoes to the candidate with the fewest vetoes. Since **the voters**
are indistinguishable by weight, we simply bribe the cheapest voters available.

Theorem 25 Simple Weighted b-Edge Cover of Multigraphs is polynomial-time many-one reducible to $**bribery**
in 2**-veto elections.**
Proof: Consider an instance of Simple Weighted b-Edge Cover of Multigraphs: Let G = (V, E**) be a** multigraph, and let b(v) denote the multiplicity that v ∈ V is to be covered, and w(e**) denote the weight of** edge e ∈ E. We wish to find a b-edge cover of G **with edges of total weight at most** q.

We construct a 2-veto election as follows. The voter set will be given by V ∪ {p, p′, b, b′}**. We will be**
bribing to elect p. Note that the voter set also includes each vertex of G **and three buffer candidates,** p
′, b, and b
′.

Initially, there are ||E|| voters of price q + 1 who veto {p, p′} and ||E|| voters of price q **+ 1 who veto**
{b, b′}. For each edge e = {v1, v2} ∈ E of weight w(e), let there be one voter of price w(e**) who vetoes**
{v1, v2}. Finally, for each vertex v ∈ V **, let there be** ||E|| + b(v) − deg(v) voters of price q **+ 1 who veto**
{**v, b**}. deg(v**) is the degree of vertex** v in G.