Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty

1 Introduction

Two interesting voting rules are used in many parliamentary chambers to amend and decide upon new legislation: the successive procedure and the amendment procedure [Apesteguia et al., 2014]. Both are sequential voting procedures: the alternatives are ordered (thus forming an agenda) and they are considered step by step, making a binary decision based on majority voting in each step. In a nutshell, the successive procedure considers in every step the current alternative and decides whether to accept it-then the procedure stops and the winner is determined-or to reject it-then the procedure continues with the remaining alternatives in the given order. The amendment procedure in each step jointly considers two current alternatives and decides by majority voting which one of the two is eliminated-the other one then will be confronted with the next alternative given by the agenda.

There are many reasons for a study of the computational properties of parliamentary voting procedures.

First, parliamentary voting procedures are used very frequently in practice. For example, the recent 112th Congress of the US Senate and House of Representatives had 1030 votes to amend and approve bills. This does not take into account the hundreds of committees that also amended and voted on these bills.

∗RB was supported by the DFG project PAWS (NI 369/10) and TW was supported by the Alexander von Humboldt Foundation.

Second, parliamentary voting procedures are used to make some of the most important decisions in society. We decide to reduce carbon emissions, provide universal health care, or raise taxes based on the outcome of such voting procedures. When rallying support for new legislation, it is vital to know what amendments can and cannot be passed. Third, Enelow and Koehler [1980] give evidence that parliamentary voting may be strategic. Fourth, there is both theoretical and empirical evidence that the final outcome depends critically on the order in which amendments are presented. For example, Ordeshook and Schwartz [1987] remark that ". . . legislative decisions are at the mercy of elites who control agendas."

It is therefore interesting to ask if, for example, computational complexity is a barrier to the control of the agenda or to strategic voting in such parliamentary voting procedures. It is also interesting to ask if we can efficiently compute whether a particular amendment can or will pass despite uncertainty in the votes or the agenda. We provide one of the the first computational studies of these issues, giving both theoretical as well as empirical results.

RelatedWork. There are many studies in the economic and political literature, starting with Black [1958], concerning "insincere" or "sophisticated" or "strategic" voting e.g. [Farquharson, 1969; Miller, 1977; Enelow and Koehler, 1980; McKelvey and Niemi, 1978; Shepsle and Weingast, 1984; Banks, 1985; Moulin, 1986; Ordeshook and Schwartz, 1987]. Apesteguia et al. [2014] characterize both the amendment and the successive procedures from an axiomatic perspective.

Miller [1977] studies the set of alternatives that may win. He shows that an alternative can become an amendment winner if and only if it belongs to the Condorcet set (a.k.a top cycle). We extend this result by a constructive proof. For the successive procedure, however, he only shows that any alternative from the Condorcet set can win. Barber`a and Gerber [2014] follow Miller's research of characterizing the set of alternatives that may become an amendment (or a successive) winner 1 Rasch [2014] empirically examines the behavior of voters in the Norwegian parliament, where the successive procedure is used. He reports that successful insincere voting, where voters may vote differently from their true preferences and the outcome is better for them, is very rare.

1 Their definitions for both procedures are actually different from ours, the common ones.

Using computational complexity as a barrier against manipulation was initiated by Bartholdi III et al. [1989]. They show that manipulating a special variant of the Copeland voting rule is NP-hard. Bartholdi III and Orlin [1991] show that manipulating the Single Transfer Vote (STV) voting rule is NP-hard even for coalition size one. This voting rule is used in the parliamentary elections of many countries. It is a sequential voting procedure and works similarly to the successive procedure except that there is no agenda. Instead, in each step, the alternative that is ranked first by the least number of voters will be deleted from the profile. The NP-hardness result for manipulating STV is of particular interest since we design a polynomial-time algorithm for manipulating the successive procedure, indicating that it is the agenda that makes an important difference.

Concerning uncertainty in elections, there is some work in the political literature [Ordeshook and Palfrey, 1988; Jung, 1989]; there seems to be significantly more activity on the computational side. Konczak and Lang [2005] consider possible and necessary winners for the Condorcet rule. The same problems for several other common voting rules are frequently studied [Walsh, 2007; Betzler et al., 2009; Hazon et al., 2012; Aziz et al., 2012].

The amendment procedure is a special case of the voting tree procedure [Moulin, 1986]. This general procedure employs a binary voting tree where the leaves represent the alternatives and each alternative is represented by at least one leaf, and each internal node represents the alternative that wins the pairwise comparison of its direct children. The alternative represented by the root defines the winner. If the binary tree is degenerated and each alternative is represented by exactly one leaf, then this procedure is identical to the amendment one. Conitzer et al. [2007] provide a cubic time algorithm to tackle weighted manipulation for the voting tree procedure while our quadratic time algorithm is tailored for the amendment one. Xia and Conitzer [2011] provide intractability results for the weighted possible (resp. necessary) winner problem when the given tree is balanced. Pini et al.; Lang et al. [2011; 2012] show that weighted possible (resp. necessary) winner is intractable for constant number of voters (c.f. Table 1).

Our Contributions. We investigate computational problems for the amendment procedure and the successive procedure. We focus on agenda control, manipulation, and winner determination problems with incomplete preferences. Our results indicate that the amendment procedure is computationally more expensive than the successive procedure. See Table 1 for an overview on our theoretical results.

Our experiments for agenda control and manipulation for real-world voting data indicate that while both problems are polynomial-time solvable, a successful agenda control is very rare and a successful manipulation on average needs a coalition containing more than half the voters.

Due to lack of space, we have deferred several details (mostly proofs) to the full version of the paper.

2 Preliminaries

Let A := {a1, . . . , am} be a set of m alternatives and let V := {v1, . . . , vn} be a set of n voters. A preference profile P := (A, V ) specifies the preference orders of the voters in V , where each voter vi ranks the alternatives according to a partial order ≻i over A. For three alternatives a, b, c ∈ A, the relation a ≻i b means that voter vi strictly prefers a to b, and {a, b} ≻i c means that voter vi strictly prefers a and b to c, but he thinks that alternatives a and b are incomparable. Given a subset A′ ⊆ A of alternatives, by -→ A′ we denote an arbitrary but fixed linear order of the alternatives in A′ . Consequently, ←- A′ denotes the corresponding reversed order of the alternatives in A′ . Given an alternative a ∈ A′ from this set, we say that a is a majority winner if in the profile restricted to only the alternatives from A′ , a is ranked first by more than half of the voters. We say that a beats b (in the head-to-head contest) when a majority of voters prefers a over b, and call a the survivor and b the loser of the two alternatives. Given two preference profiles P and P ′ for the same set of alternatives and the same set of voters, we say that P extends P ′ if for every i preference order ≻i from P includes the preference order ≻′i from P ′ . If additionally each ≻i is a linear order, then we also say that P completes P ′ .

We consider two of the most common parliamentary voting procedures. For both procedures, we assume that a linear order over the alternatives in A is given. We refer to this linear order L as an agenda. If this order is not linear, then we call it a partial agenda, denoted by B.

Definition 1 (Successive procedure). There can be at most m- 1 rounds. Starting with round i := 1, we repeat the following until we make a decision: Let c be the ith alternative in the agenda L. If a majority of voters prefers alternative c to all alternatives that are ordered behind it in L, then c is the decision and we call it a successive winner. Otherwise, we proceed to round i := i + 1.

For instance, given a profile with three alternatives a, b, c, and three voters v1, v2, v3 whose preference orders are specified as follows: v1 : a ≻ b ≻ c, v2 : b ≻ a ≻ c, v3 : c ≻ a ≻ b. Consider the agenda a ≻ b ≻ c. Since a is not preferred to {b, c} by a majority of voters (only v1 does), a is not a successive winner. Since a majority of voters prefers b to c (voters v1 and v2), b is the successive winner.

In Europe, the successive procedure is used in many parliamentary chambers including those of Austria, Belgium, Denmark, France, Germany, Greece, Iceland, Ireland, Italy, Luxembourg, the Netherlands, Norway, Portugal, and Spain [Rasch, 2000].

Definition 2 (Amendment procedure). This procedure has m rounds. In the 1st round, we let the 1st-round winner be the first alternative in the agenda L. Then, for each round 2 ≤ i ≤ m, i starting with 2, let the the ith-round winner be the survivor between the ith alternative in L and the (i - 1)th-round winner. We define the mth-round winner to be an amendment winner.

Consider now the profile and the agenda that follows Definition 1 for the amendment procedure. Alternative a is the 1st-round winner since it is the first alternative in the agenda. Since a majority of voters prefers a to b, a is the 2nd-round winner. Since a majority of voters also prefers a to c, a is the 3rd round and the amendment winner.

In Europe, the amendment procedure is used in the parliamentary chambers of Finland, Sweden, Switzerland, and the United Kingdom. It is also used in the U.S. Congress and several other countries with Anglo-American ties.

We assume that the number of voters is odd to reduce the impact of ties, and break ties that remain in favor of the manipulator(s). We consider both unweighted voters and voters with integer weights. The weighted case is especially interesting in the parliamentary setting: First, there are parliamentary chambers where voters are weighted (e.g. in the Council of Europe, preference orders are weighted by the size of the country). Second, voters will often vote along party lines. This effectively gives us parties casting weighted preference orders. Third, the weighted case can inform the situation where we have uncertainty about the preference orders.

3 Agenda Control

The order of the alternatives, that is, the agenda, may depend on the Speaker, the Government, logical considerations (e.g. the status quo goes last, the most extreme alternative comes first), the chronological order of submission, or other factors. The agenda used can have a major impact on the final decision. For example, suppose voters are sincere and we use the successive procedure. Then, the alternative that beats every other alternative will only necessarily win if it is introduced in one of the last two positions in the agenda. We therefore consider the following computational question.

AGENDA CONTROL

Input: A preference profile P := (A, V ) with linear

preference orders and a preferred alternative p ∈ A. Question: Is there an agenda for A such that p is the overall winner?

Theorem 1. AGENDA CONTROL can be solved in O(n ·m2 ) time for the successive procedure and in O(n·m2 +m3 ) time for the amendment procedure.

Proof sketch. First of all, we remark that for both procedures, we do not only solve the decision variant but also find a successful agenda if control is possible.

Successive procedure. The general idea behind successive control is to build an agenda from back to front such that each of the alternatives that are currently among the highest positions in the partial agenda may be strong enough to beat p alone but is too weak to be a majority winner against the whole set of alternatives behind them. To formalize this idea, we need some observations. Let a, b be two alternatives such that a beats b, that is, a majority of voters prefers a over b in the given profile. Then, under an agenda where a is behind b, b can never win since in the round when b is considered, b is not ranked first by a majority of voters due to a beating b and a is not yet deleted, implying that b will be deleted. We can even generalize the above observation to a set of alternatives:

Claim 1. Let A′ ⊆ A be a subset of alternatives. Let D(A′ ) be the set of all alternatives each a of which is not a majority winner when restricting the profile to A′ ∪ {a}. Then,

1. no alternative from D(A′ ) can be a successive winner under an agenda L that extends the partial order D(A′ ) ≻ A′ , and
2. if D(A′ ) is empty and if A′ ̸= A, then no alternative from A′ can be a successive winner.

By Claim 1, we can construct an agenda L from back to front by first placing our preferred alternative p at the last position, and we set A′ := {p}. We repeat the following algorithm until the set A′ includes all alternatives from A, extending the agenda L gradually.

Let D(A′ ) be the set of alternatives such that each alternative a of D(A′ ) is not a majority winner when restricting the profile to the set A′ ∪ {a} of alternatives. Then, we extend L by requiring D(A′ ) ≻L A′ , and set A′ := A′ ∪D(A′ ).

If D(A′ ) is empty but A′ ̸= A, then we reject and answer with "no". Otherwise, we repeat the above procedure until we obtain a complete agenda, and answer "yes".

We now come to the running time analysis. In each extension of the agenda, for each alternative a /∈ A′ we check whether it is a majority winner when restricting the profile to the alternatives from a ∪ A′ . By maintaining a list which stores for each voter v, the highest position of alternative from A′ ranked by v, the above check for a can be done in O(n) time. Since an agenda is completed after at most m extensions, the total running time is O(n · m2 ).

Amendment procedure. Controlling the amendment procedure is closely related to finding a Hamiltonian cycle in a strongly connected tournament. To see this, we first construct a majority graph for the given preference profile by creating a vertex ui for each alternative ai, and adding an arc (ui, uj) if and only if ai beats aj. Recall that we assume the number of voters to be odd. The majority graph constructed in this way is a tournament. From the theory of directed graphs [Harary and Moser, 1966, Thm. 7], we can conclude that every strongly connected tournament contains a Hamiltonian cycle. Now, the crucial idea is to check whether p corresponds to a vertex that belongs to a strongly connected tournament that has only out-going arcs. Alternative p can win under an appropriate agenda if and only if this is the case.

The O(n · m2 ) part in the running time comes from constructing the majority graph and the other part comes from finding a Hamiltonian cycle.

We close this section by remarking that first, the approach for the successive procedure actually works for both odd as well as even number of voters. Second, our approach for the amendment procedure can be extended to the case where the number of voters is even. There, alternative p is a winner if and only if no strongly connected component "dominates" the strongly connected component that contains up. We omit the proof due to lack of space.

4 Manipulation

We first consider the question of how difficult it is for voters to vote strategically to ensure a given outcome supposing the other voters vote sincerely.

MANIPULATION

Input: A profile P := (A, V ) with linear preference orders, a non-negative integer k ∈ N, a preferred alternative p ∈ A, and an agenda L for A.

Question: Is it possible to add a coalition of k voters such that p wins under agenda L?

In WEIGHTED COALITION MANIPULATION, the voters of the coalition also come with integer weights. However, we remark here that the weighted and non-weighted cases are equivalent because of the following observation:

Observation 1. If there is a successful (weighted) manipulation, then there is also a successful one where all voters from the coalition rank the alternatives in the same way.

We find that computing whether a manipulation is possible is polynomial for both the successive and amendment procedures. However, our procedure for deciding whether the amendment procedure can be successfully manipulated is asymptotically more complex than our procedure for deciding the same question for the successive procedure.

Theorem 2. MANIPULATION can be solved in O((k+n)·m) time for the successive procedure and in O((k+n) ·m2 ) time for the amendment procedure.

Proof sketch. By Observation 1, we can assume that the coalition votes in the same way. Thus, we only need to construct a single preference order for all voters in the coalition.

Successive procedure. We can observe that if a coalition of k voters can manipulate the successive procedure, then by ranking alternative p in the first position and the other alternatives in an arbitrary but fixed order, p must also win. This leads to a linear-time algorithm: Let the coalition all vote p ≻ ----→ A \ {p}, and check whether p may win the successive procedure.

Amendment procedure. Our approach to the amendment procedure works in a different way. Indeed, we can compute in quadratic time all alternatives that can become a winner when adding k additional voters to the profile, and we can compute the corresponding coalition for each of these alternatives. First, we need one further notion: We call an alternative an ith-round possible winner, if adding a coalition of k additional voters to the original profile makes this alternative the ith-round winner (see the amendment procedure definition). Now, let a denote the ith alternative in the agenda L. Observe that a will be an ith-round possible winner only if there is an (i-1)th-round possible winner b such that requiring all voters from the coalition to rank a above b makes a beat b. Otherwise, no matter how the preference orders of the coalition look like, a will not be an ith-round possible winner and hence, will never be an amendment winner. Analogously, an (i-1)th-round possible winner b can become an ith-round possible winner only if requiring all voters from the coalition to rank b above a can make b beat a.

Based on the above observation, we can build a recursive algorithm that constructs a linear order over the first i alternatives from L for each ith-round possible winner. Obviously, the first-round possible winner is the first alternative in the agenda. To compute the set Wi of all ith-round possible winners, the program needs as input two sets: a set Wi-1 of all (i - 1)th-round possible winners and a set Qi-1 of linear orders over the first i-1 alternatives such that for each (i-1)thround possible winner b fromWi-1, there is exactly one order πb from Qi-1 such that if the coalition ranks πb , then b becomes an (i - 1)th-round winner. Now, the algorithm goes through every (i - 1)th-round possible winner b and decides whether it can become an ith-round possible winner, that is, whether it is possible to make b beat a where a is the ith alternative in the agenda L. As already discussed, this is only the case if adding the coalition with the order πb ∪ {b ≻ a} can make b beat a; otherwise, if a is not yet added to Wi, then we add a to Wi and the preference order πb ∪ {a ≻ b} to Qi.

Finally, the mth-round possible winners fromWi are all alternatives that can become an amendment winner if the coalition decides to manipulate.

5 Possible/NecessaryWinner

We might only have partial knowledge about how the voters will vote, and about how the agenda will be ordered. Nevertheless, we might be interested to ask questions about what may or may not be the final outcome. Does our favorite alternative stand any chance of winning? Is it inevitable that the government's alternative will win? Is there an agenda under which our alternative can win? Hence, we consider the question of which alternative possibly or necessarily wins.

POSSIBLE (resp. NECESSARY) WINNER

Input: A preference profile P := (A, V ), a preferred alternative p ∈ A, and a partial agenda B.

Question: Can p win in a (resp. every) completion of the profile P for an (resp. every) agenda which completes B?

Our next result implies that as soon as the preference profile is not complete, deciding who may be a possible winner is NP-hard even for a fixed agenda.

Theorem 3. POSSIBLE WINNER with a fixed agenda is NPhard for both the successive and amendment procedures.

Proof sketch. We only show the NP-hardness result for the amendment procedure by describing a polynomial-time reduction from the NP-hard VERTEX COVER problem which, given an undirected graph G = (U, E) and an integer k, asks whether there is a vertex cover of size at most k, that is, a subset of at most k vertices whose removal destroys all edges.

Let (G, k) be an instance of VERTEX COVER where U := {u1, . . . , ur} denotes the set of vertices and E := {e1, . . . , es} denotes the set of edges. We construct a POSSIBLE WINNER instance ((A, V ), p, B) as follows. The set A of alternatives contains the preferred alternative p, one helper alternative h, one dummy alternative d, and for each edge ej ∈ E one edge alternative aj. The set V of voters contains for each vertex ui ∈ U one vertex voter vi and r - 1 additional auxiliary voters with the following preferences:

The preference order of each vertex voter vi is specified by

where I(ui) denotes the set of edge alternatives corresponding to edges incident to the vertex ui. All auxiliary voters' preference orders are complete: r - k - 1 auxiliary voters have the same preferences specified by the linear order p ≻ --------→ A \ {p, d, h} ≻ h ≻ d, and the remaining k auxiliary voters have the same preferences specified by the linear order d ≻ h ≻ p ≻ --------→ A \ {p, d, h}. The partial agenda B is fixed and is defined as h ≻ d ≻ p ≻ ←-------- A \ {p, d, h}.

This completes the construction which can be computed in polynomial time. We briefly sketch the idea of the correctness proof. Our construction ensures that in order to let p beat each edge alternative aj in the final s rounds of the procedure one has to put p (and by the preference orders of the vertex voters, one also has to put h) in front of aj (and by the preference orders of the vertex voters, also in front of d) in the preference order of at least one vertex voter that corresponds to a vertex incident to the edge ej. This implies that the vertices corresponding to the voters for which we put p in front of d form a vertex cover. Furthermore, since h beats p in every extension of the partial orders the solution must ensure that d beats h in the first round of the procedure. However, this is only the case if the number of vertices that correspond to the vertex voters where we put p (and by the preference orders, we also put h) in front of d is at most k. Thus, the vertex cover is of size at most k.

We mention without going into details that POSSIBLE WINNER can be solved in O(f(m) · nc ) time for both procedures, where f is a computable function solely depending on the number m of alternatives and c is a constant. The idea behind such algorithms is that there are at most 2m2 partial orders over the m alternatives; thus, we can guess in h(m) time the structure of a completion of the profile and a completion of the agenda such that p may win, and use an integer linear program with g(m) variables to check whether the guess is implementable. Using the famous result from Lenstra [1983], we can conclude that the algorithms constructed in this way are solvable in O(f(m) · nc ) time.

Notably, the two procedures have different computational complexity regarding the necessary winner problem.

Theorem4. NECESSARY WINNER takes O(n ·m3 ) time for the successive procedure while it is coNP-hard for the amendment procedure even with a fixed agenda.

Proof sketch. Successive procedure. The idea of the algorithm is to check whether there is a completion (P ∗ , B∗ ) of the profile P and the agenda B satisfying one of the following properties, where an alternative is called a predecessor (resp. a successor) of p if it is ordered ahead of (resp. behind) p in the agenda B∗ .

1. No majority of the voters prefers p to all successors of p implying that a predecessor or a successor of p wins.
2. A majority of the voters prefers p to all successors of p, but some predecessor of p wins.

One can verify that p is a necessary winner if and only if no completion (P ∗ , B∗ ) satisfies at least one of both properties.

Let A⇐p be the set of alternatives that must be in front of p in every completion of B, let A→p be the set of alternatives that may be behind p in some completion of B, and let A←a be the set of alternatives that may be in front of a given alternative a in some completion of B.

Let P = (A, V ) be a profile and a be some alternative. We call a completion of P a-discriminating if each partial preference order is completed such that a′ ≻ a for every alternative a′ ∈ A \ {a} where this is possible (and arbitrary with respect to any other relation). We call a completion of P aprivileging if each partial preference order is completed such that a ≻ a′ for every alternative a′ ∈ A \ {a} where this is possible (and arbitrary with respect to any other relation).

• Claim 2. There is a completion (P ∗ , B∗ ) of (P, B) satisfying Property 1 if and only if p is not a majority winner when restricting every p-discriminating completion of P ∗ to A→p ∪ {p}.

Claim 3. Assume that there is no completion of (P, B) satisfying Property 1. Then, there is a completion (P ∗ , B∗ ) of (P, B) satisfying Property 2 if and only if there is some alternative a ∈ A⇐p being the majority winner of every aprivileging completion of P restricted to A \ A←a .

Now, we have all ingredients to describe our algorithm.

1. Compute a p-discriminating completion P ∗ of P.
2. If p is a not majority winner when restricting the profile P ∗ to A→p ∪ {p} then return 'no'.
3. For each alternative a ∈ A⇐p do
4. Compute an a-privileging completion P ∗ of P.
5. If a is a majority winner when restricting the profile P ∗ to A \ A←a then return 'no'.
6. Return 'yes'.

Computing a p-discriminating or an a-privileging completion takes O(n · m2 ) time, finding the majority winner also takes O(n · m2 ) time, and the algorithm iterates at most m times through the loop in Step 3. Altogether it takes O(n·m3 ) time.

Amendment procedure. Adapting the VERTEX COVER reduction for Theorem 3, we can also show that NECESSARY WINNER for the same procedure is coNP-hard.

The weighted case. If each voter comes with a weight, then the possible winner as well as the necessary winner problems turn out to be already NP-hard for a constant number of alternatives. This is in contrast to the manipulation problem where the weighted case is computationally equivalent to the non-weighted case: they are both polynomial-time solvable.

Theorem 5. Both for the successive and the amendment procedures, POSSIBLE WINNER with weighted voters is weakly NP-hard even for three alternatives and when the B is linear.

Theorem 6. For the successive procedure, NECESSARY WINNER with weighted voters can be solved in O(n · m3 ) time. For the amendment procedure, NECESSARY WINNER with weighted voters can be solved in linear time for up to three alternatives while it is already weakly coNP-hard with at least four alternatives and B being linear.

6 Experimental Results

Our polynomial-time algorithms leave open how many alternatives can win through control (or manipulation). We therefore use the data from Preflib due to Mattei and Walsh [2013] to investigate empirically the likelihood of successful manipulation or agenda control. Since only one case of the possible and the necessary winner problems is polynomial-time solvable and since Preflib offers only a very restricted variant of incomplete preferences, we do not run experiments for these two problems. Our results are shown in Table 2.

Agenda Control. For each profile with m alternatives and n voters such that n is odd, using the algorithm behind Theorem 1, we compute the number ms (resp. ma) of alternatives for which a successive (resp. amendment) agenda control is possible. Then, we calculate the control vulnerability ratio as ms-1 m-1 and ma-1 m-1 , respectively. Note that we have m- 1 here since we factor out the alternative that wins originally. For instance, control vulnerability ratio 0.5 means that m-1 2 candidates are controllable. Our results show that the amendment procedure tends to be more resistant than the successive procedure when considering agenda control: Less than 5% of the alternatives have a chance to win the amendment procedure, while it is about 10% for the successive procedure.

Manipulation. Since Preflib does not offer any agenda, we have to generate a set of agendas for manipulation to obtain a good representation. We consider a set X of x different agendas, depending on the number m of alternatives: If m ≤ 8, then we let X be the set of all possible agendas, that is, x := m!. Otherwise, we generate a set X of x uniformly distributed random agendas with x := min(n2 , 8!). Then, for each alternative c and each agenda L ∈ X, using the algorithm behind Theorem 2, we compute the minimum coalition size, that is, the minimum number of voters needed to make c a winner. Let this be κ(P, c,L). This is upper-bounded by n + 1. Then, we calculate the manipulation resistance ratio as ∑L∈X ∑c∈C κ(P,c,L) x·(m-1)·(n+1) . Since most alternatives need a coalition of more than n voters to manipulate successfully which strongly affects the manipulation resistance ratio, we also consider two related concepts: The ratio of the 2nd winner coalition size, that is, the coalition size for the alternative that becomes a winner after the original winner is removed, and the ratio of the smallest coalition size, that is, the size of the smallest coalition that makes any alternative win. Our results show that successful manipulations with few voters are rare: For profiles up to four alternatives the average coalition size is n/2 (even the 2nd winner coalition size is n/5; the smallest coalition size is only slightly lower), while for profiles with at least five alternatives the average coalition size is almost n + 1 (even the 2nd winner coalition size is roughly n/2).

7 Conclusion

Our work indicates that, from a computational perspective, the amendment procedure seems superior to the successive procedure. Our work supports the claim that most European and Latin parliaments (cf. Apesteguia et al. [2014]) should rather go the Anglo-American way, that is, they should use amendment procedures instead of successive procedures.

Following the spirit of Betzler et al. [2009], it would be of interest to complement our computational hardness results for possible and necessary winner problems with a refined complexity analysis concerning tractable special cases. For instance, our NP-hardness reductions for the possible winner problems assume that voters may have arbitrary partial preferences. It would be interesting to know whether this still holds if voter preferences are single-peaked [Black, 1958]. Moreover, it would be natural to also adopt a more game-theoretic view on the strategic voting scenarios we considered. Finally, it would be also interesting to study further manipulation scenarios for parliamentary voting procedures including, for example, candidate control as discussed by Rasch [2014].