# computational_aspects_of_nearly_singlepeaked_electorates__79cf9f23.pdf

Journal of Artiﬁcial Intelligence Research 58 (2017) 297-337 Submitted 05/16; published 02/17

Computational Aspects of Nearly Single-Peaked Electorates

G abor Erd elyi erdelyi@wiwi.uni-siegen.de School of Economic Disciplines University of Siegen Siegen, Germany

Martin Lackner martin.lackner@cs.ox.ac.uk Department of Computer Science University of Oxford Oxford, United Kingdom

Andreas Pfandler pfandler@dbai.tuwien.ac.at Institute of Information Systems TU Wien Vienna, Austria

Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting rules are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these rules suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the computational complexity of strategic behavior in nearly singlepeaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure. In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given proﬁle is nearly single-peaked is NP-complete in many cases. For one case we present a polynomial-time algorithm. In case the singlepeaked axis is given, we show that determining the distance is always possible in polynomial time. Furthermore, we explore the relations between the new notions introduced in this paper and existing notions from the literature.

1. Introduction

Voting is a ubiquitous method for preference aggregation and collective decision-making. It has applications in many settings ranging from politics to artiﬁcial intelligence and further topics in computer science (see, e.g., Ephrati & Rosenschein, 1997; Ghosh, Mundhe, Hernandez, & Sen, 1999; Dwork, Kumar, Naor, & Sivakumar, 2001). In the presence of huge data volumes, the computational properties of voting rules gain great importance. In particular, it is desirable to be able to quickly determine the winner(s) of an election. On the other hand it should be computationally hard to ﬁnd strategies for dishonest behavior. Bartholdi, Tovey, and Trick (1989a) were the ﬁrst to study the computational aspects of strategic behavior in elections. They deﬁned and studied manipulation in voting, i.e., a group of voters casts their votes insincerely in order to reach a desired outcome. Another type of manipulative behavior is control, where an external agent makes structural changes to the election such as adding/deleting/partitioning either candidates or voters in order to

c 2017 AI Access Foundation. All rights reserved.

Erd elyi, Lackner & Pfandler

reach a desired outcome. Control has been studied ﬁrst also by Bartholdi, Tovey, and Trick (1992). There is also bribery, where an external agent changes some votes in order to inﬂuence the outcome of the election (see, e.g., Faliszewski, Hemaspaandra, & Hemaspaandra, 2009). For an overview and many natural examples of bribery, control, and manipulation we refer to the literature (Baumeister, Erd elyi, Hemaspaandra, Hemaspaandra, & Rothe, 2010; Faliszewski, Hemaspaandra, & Hemaspaandra, 2010; Faliszewski & Procaccia, 2010; Brandt, Conitzer, & Endriss, 2013; Rothe, 2015; Brandt, Conitzer, Endriss, Lang, & Procaccia, 2016). Traditionally, the complexity of such attacks is studied under the assumption that, in each election, any admissible vote can occur. However, there are many elections where the diversity of the votes is limited in the sense that there are admissible votes nobody would ever cast. One of the best known examples is the single-peaked domain, introduced by Black (1948). It is based on the assumption that the votes are polarized along some linear axis and voters prefer candidates closer to their ideal candidate on this axis over candidates farther away. The study of the computational aspects of elections with single-peaked preferences was initiated by Walsh (2007), followed by fundamental contributions by Faliszewski, Hemaspaandra, Hemaspaandra, and Rothe (2011) and Brandt, Brill, Hemaspaandra, and Hemaspaandra (2015). The general conclusion of these papers is that many voting problems which are NP-hard in the general case turn out to be easy for single-peaked societies. A recent line of research initiated by Conitzer (2009) suggests that many elections are not perfectly single-peaked but are close to it with respect to some measure. In the work of Faliszewski, Hemaspaandra, and Hemaspaandra (2014) various notions of nearly singlepeaked elections were introduced and it was shown that the complexity of manipulative actions jumps back to NP-hardness in many cases. This paper is the ﬁrst to systematically study notions of distances for nearly singlepeaked electorates. Our main contributions are:

We introduce three new notions of nearly single-peakedness. In addition, we study six notions that already have been deﬁned or suggested in the literature.

We explore connections between both existing and new notions by providing inequalities. These allow one to compare these notions and better understand their relationship. We also brieﬂy discuss to which degree axiomatic properties of single-peaked preferences transfer to nearly single-peaked preferences.

We analyze the computational complexity of computing the distance of arbitrary preference proﬁles to single-peakedness. In most cases we show NP-completeness. For the k-candidate deletion distance, we present a polynomial-time algorithm.

Finally, we analyze the computational complexity of the nearly single-peaked evaluation problem, where the task is to compute the distance for a given axis.

1.1 Related Work

The main computational problem studied in this work is recognizing nearly single-peaked preferences. For single-peaked preferences, the question of whether a given proﬁle is singlepeaked has received considerable attention. Bartholdi and Trick (1986) were the ﬁrst to

Computational Aspects of Nearly Single-Peaked Electorates

prove that it requires only polynomial time to detect single-peaked preferences; their algorithm based on the consecutive ones problem requires O(m2n) time for proﬁles with n voters and m candidates. This runtime was improved to O(mn + m2) by Doignon and Falmagne (1994) and ﬁnally to O(mn) by Escoﬃer, Lang, and Ozt urk (2008). Our work, in contrast to these results, shows that computing the distance to single-peaked preferences is often computationally hard. The impact of single-peaked preferences on computational problems in social choice is generally well understood. Let us mention the work of Faliszewski et al. (2011) and Brandt et al. (2015), in which the complexity of winner problems and of strategic behavior (e.g., manipulation and control) in electorates with single-peaked preferences is investigated. These papers do not consider nearly single-peaked preferences, but mention them as future work. In the context of nearly single-peaked preferences the most relevant paper is by Faliszewski et al. (2014). They introduce several notions of nearly single-peakedness and analyze the complexity of bribery, control, and manipulation in nearly single-peaked elections. Their work on manipulation and bribery has recently been extended to other voting rules (Menon & Larson, 2016) and to other notions of distance (Erd elyi, Lackner, & Pfandler, 2015). These papers deal with applications of nearly single-peaked electorates and assume that the underlying axis is part of the input. Our paper, in contrast, studies the complexity of computing an axis that minimizes the distance of a preference proﬁle to single-peakedness. The work of Bredereck, Chen, and Woeginger (2016) has a similar objective but is somewhat orthogonal to our paper. They study only two distance measures (Voter Deletion and Candidate Deletion) but for a variety of domain restrictions (e.g., also the single-crossing and group-separable domains). Their work is based on a combinatorial characterization of domain restrictions by Ballester and Haeringer (2011) and Bredereck, Chen, and Woeginger (2013). Recent work by Elkind and Lackner (2014) presents approximation and ﬁxedparameter tractable (fpt) algorithms for computing such distances. Sui, Francois-Nienaber, and Boutilier (2013) propose heuristics to compute distances to single-peakedness and its two-dimensional analogue, 2D single-peakedness; they also perform experiments on realworld data sets. Two further distance measures have been studied: Single-peaked width by Cornaz, Galand, and Spanjaard (2012, 2013) and the decloning measure by Elkind, Faliszewski, and Slinko (2012). The complexity of manipulation and control in proﬁles of bounded single-peaked width has been studied by Yang and Guo (2014b) and Yang (2015). Single-peakedness on trees (Demange, 1982) and single-peakedness on circles (Peters & Lackner, 2017) are also generalizations of classical single-peakedness but are not directly related to (distance based) nearly single-peakedness. Both concepts have proven to be algorithmically useful in the context of multiwinner elections (Yu, Chan, & Elkind, 2013; Peters & Elkind, 2016; Peters & Lackner, 2017). Multiwinner elections have also been studied for single-peaked (Betzler, Slinko, & Uhlmann, 2013) and single-crossing elections (Skowron, Yu, Faliszewski, & Elkind, 2015). Another line of research are domain restrictions in incomplete preferences (partial orders); incomplete single-peaked proﬁles (Lackner, 2014) and incomplete single-crossing proﬁles (Elkind, Faliszewski, Lackner, & Obraztsova, 2015) have been considered. Domain restrictions have also been studied in dichotomous preferences (Elkind & Lackner, 2015) and notions of single-peakedness for preferences with ties, i.e., for weak orders (Fitzsimmons & Hemaspaandra, 2016). Finally, we remark that single-peaked preferences have also

Erd elyi, Lackner & Pfandler

been considered in the context of preference elicitation (Conitzer, 2009) and in the context of possible and necessary winners under uncertainty regarding the votes (Walsh, 2007). The mathematical likelihood of single-peaked preferences has been analyzed by Bruner and Lackner (2015).

1.2 Organization

This paper is organized as follows. In Section 2, we recall some notions from voting theory and deﬁne single-peaked proﬁles. In Section 3, we introduce the decision problems we are investigating in our paper. Section 4 presents basic results regarding single-peaked proﬁles. Our results on the relations between the diﬀerent notions of nearly single-peakedness are presented in Section 5. The results on the complexity of nearly single-peaked consistency and evaluation can be found in Section 6. Finally, Section 7 provides some conclusions and directions for future work.

2. Preliminaries

Let C be a ﬁnite set of candidates and let be a total order on C. Let P = ( 1, . . . , n) be a preference proﬁle, i.e., a list of total orders on the candidate set C. An election is deﬁned as a pair E = (C, P), where C is the set of candidates and P a preference proﬁle on C. We say that i is the vote of voter i. For simplicity we write i: c1c2 . . . cm instead of c1 i c2 i i cm. For a vote i: c1c2 . . . cm let the vote i : cmcm 1 . . . c1 denote the reverse vote of i. For two preference proﬁles on the same set of candidates P = ( 1, . . . , n) and L = ( n+1, . . . , s), let (P, L) = ( 1, . . . , s) deﬁne the union of the two preference proﬁles. In our constructions, we sometimes insert a subset of the candidates B C into a vote, where we assume some arbitrary, ﬁxed order of the candidates in B (e.g., i: c1Bc3 means that c1 is the top-ranked candidate of voter i and c3 is the last-ranked candidate, whereas all b B are ranked between c1 and c3).

Deﬁnition 2.1. Let an axis A be a total order on C denoted by >. Furthermore, let be a vote with top-ranked candidate c. The vote is single-peaked with respect to A if for any x, y C, if x > y > c or c > y > x then c y x has to hold. A preference proﬁle P is said to be single-peaked with respect to an axis A if and only if each vote is single-peaked with respect to A. A preference proﬁle P is said to be single-peaked consistent if there exists an axis A such that P is single-peaked with respect to A.

Let C C. By P[C ] we denote the proﬁle P restricted to the candidates in C . Analogously if A is an axis on C, we denote by A[C ] the axis A restricted to candidates in C . Escoﬃer, Lang, and Ozt urk (2008) present an algorithm that decides whether a given preference proﬁle is single-peaked consistent in time O(m n). Their algorithm improves upon the runtime of the original algorithm by Bartholdi and Trick (1986). The corresponding decision problem is deﬁned as follows.

Single-Peaked Consistency

Given: An election E = (C, P). Question: Is P single-peaked consistent?

Computational Aspects of Nearly Single-Peaked Electorates

If an axis is given additionally in the input, we have the evaluation problem. Since Single-Peaked Consistency can be solved in O(m n) time, so can Single-Peaked Evaluation.

Single-Peaked Evaluation

Given: An election E = (C, P) and an axis A. Question: Is P single-peaked with respect to A?

3. Nearly Single-Peaked Preferences

In real-world settings one has to expect a certain amount of noise in preference data. The single-peakedness property is very fragile and thus susceptible to such noise. The following example illustrates the fragility of single-peakedness: Consider the single-peaked election consisting of two kinds of votes: abcd and dcba. Assume that both votes have been cast by a large number of voters. This election is single-peaked only with respect to the axis a > b > c > d and its reverse. Adding a single vote abdc destroys the single-peakedness property although this vote is almost identical to the ﬁrst kind of votes. In this section we formally deﬁne diﬀerent notions of nearly single-peakedness. All these notions deﬁne a distance measure1 to single-peaked proﬁles. We will now describe them with help of a running example and provide ﬁrst (trivial) upper bounds on these distances. The following notions of nearly single-peakedness are deﬁned for proﬁles. The same deﬁnitions also hold for elections and thus we do not strictly distinguish between elections and proﬁles. Throughout the following deﬁnitions let E = (C, P) be an election and k be a positive integer.

k-Voter Deletion (VD)

The ﬁrst formal deﬁnition of nearly single-peaked societies was given by Faliszewski et al. (2014), however the idea of removing voters that are not single-peaked dates back to Conitzer (2009). Consider a preference proﬁle P for which most voters are single-peaked with respect to some axis A. The voters that are not single-peaked with respect to A are referred to as mavericks by Faliszewski et al. (2014). The number of mavericks, i.e., the number of voters that have to be deleted, deﬁnes a natural distance measure to singlepeakedness. If an axis can be found for a large subset of the voters, this is still a fundamental observation about the structure of the preference proﬁle.

Deﬁnition 3.1 (Faliszewski et al., 2014). A proﬁle P is k-voter deletion single-peaked with respect to an axis A if by removing at most k votes from P one can obtain a preference proﬁle P that is single-peaked with respect to A. Furthermore, P is k-voter deletion singlepeaked consistent if there exists an axis A such that P is k-voter deletion single-peaked with respect to A. Let VD(P) denote the smallest k such that P is k-voter deletion single-peaked consistent.

1. We remark that we use the words distance and distance measure with their informal meaning and not in the mathematical sense of a metric.

Erd elyi, Lackner & Pfandler

Note that VD(P) n 1 always holds. We remark that k-voter deletion single-peaked is also referred to as k-maverick-SP (Faliszewski et al., 2014) and as k-maverick single-peaked consistent (Erd elyi, Lackner, & Pfandler, 2013).

Example 1. Consider an election with C = {a, b, c, d, e} and P = { 1, 2, . . . , 202}. We deﬁne 1: abced, 2: edcab, the votes 3 . . . 102: abcde, and the remaining votes 103 . . . 202: edcba. Notice that any preference proﬁle containing abcde and edcba may only be single-peaked consistent with respect to the axis a > b > c > d > e and its reverse. Since 1 and 2 are not single-peaked with respect to this axis, P is not single-peaked. Deleting 1 and 2 yields single-peaked consistency and thus we have VD(P) = 2.

k-Candidate Deletion (CD)

As suggested by Escoﬃer et al. (2008), let us consider deleting candidates to obtain a singlepeaked proﬁle. This distance measure can be particularly useful if there are candidates that do not have a correct place on any axis. Examples could be candidates that are not wellknown (e.g., a new political party) or candidates that prioritize other topics than most candidates and thereby are judged by voters according to diﬀerent criteria. The votes restricted to the remaining candidates might still have a clear and signiﬁcant structure, in particular they might be single-peaked consistent.

Deﬁnition 3.2. A proﬁle P is k-candidate deletion single-peaked with respect to an axis A if there exists a set C C obtained by removing at most k candidates from C such that P[C ] is single-peaked with respect to A. Furthermore, P is k-candidate deletion singlepeaked consistent if there exists an axis A such that P is k-candidate deletion single-peaked with respect to A. Let CD(P) denote the smallest k such that P is k-candidate deletion single-peaked consistent.

Note that CD(P) m 2 always holds.

Example 1 (continued). Consider the preference proﬁle P as deﬁned above. Observe that for C = {b, c, d}, P[C ] is single-peaked consistent. Deleting a single candidate does not yield single-peaked consistency and thus CD(P) = 2.

k-Local Candidate Deletion (LCD)

Personal friendships or hatreds between voters and candidates could move candidates up or down in a vote. These personal relationships cannot be reﬂected in a global axis; this is an obstacle to single-peakedness already discussed by Conitzer (2009). To eliminate the inﬂuence of personal relationships to some candidates we deﬁne a local version of the previous notion. This notion can also deal with the possibility that the least favorite candidates might be ranked without special consideration or even randomly. We ﬁrst have to deﬁne partial domains and partial proﬁles.

Deﬁnition 3.3. Let C be a set of candidates and A an axis on C. A vote on a candidate set C C is called a partial vote. It is said to be single-peaked with respect to A if it is single-peaked with respect to A[C ]. A partial preference proﬁle consists of partial votes. It is called single-peaked consistent if there exists an axis A such that its partial votes are single-peaked with respect to A.

Computational Aspects of Nearly Single-Peaked Electorates

Deﬁnition 3.4. A proﬁle P is k-local candidate deletion single-peaked with respect to an axis A if by removing at most k candidates from each vote in P we obtain a partial preference proﬁle P that is single-peaked with respect to A. Furthermore, P is k-local candidate deletion single-peaked consistent if there exists an axis A such that P is k-local candidate deletion single-peaked with respect to A. Let LCD(P) denote the smallest k such that P is k-local candidate deletion single-peaked consistent.

Note that LCD(P) m 2 always holds.

Example 1 (continued). Note that it is suﬃcient to remove candidate a from vote 1 and candidate e from vote 2 to obtain single-peaked consistency. Consequently, LCD(P) = 1.

k-Additional Axes (AA)

Another suggestion by Escoﬃer et al. (2008) was to consider the minimum number of axes such that each vote is single-peaked with respect to at least one of these axes. Note that this corresponds to partitioning the voters in such a way that each group of voters is single-peaked. Additional Axes is particularly useful if each candidate represents opinions on several issues (as it is the case in political elections). A voter s ranking of the candidates would then depend on which issue is considered most important by the voter and consequently each issue might give rise to its own corresponding axis.

Deﬁnition 3.5. A proﬁle P is k-additional axes single-peaked with respect to axes A1, . . . , Ak+1 if there exists a partition P1, . . . , Pk+1 of P such that the subproﬁle P1 is single-peaked consistent with respect to A1, P2 is single-peaked with respect to A2, etc. Furthermore, P is k-additional axes single-peaked consistent if there exist k + 1 axes A1, . . . , Ak+1 such that P is k-additional axes single-peaked with respect to A1, . . . , Ak+1. Let AA(P) denote the smallest k such that P is k-additional axes single-peaked consistent.

Note that AA(P) < min n, m!

2 always holds. This is because the number of distinct votes is bounded by m!

2 , since at most m! distinct votes exist and each vote and its reverse are single-peaked with respect to the same axis.

Example 1 (continued). Notice that 1 and 2 are single-peaked consistent with respect to axis b > a > c > e > d. The remaining votes are consistent with respect to a > b > c > d > e. Thus, one additional axis is suﬃcient and hence AA(P) = 1.

k-Global Swaps (GS)

There is a second method of dealing with candidates that are not placed correctly according to an axis A. Instead of deleting them from either the candidate set C or from a vote, we could try to move them to the correct position. We do this by performing a sequence of swaps of consecutive candidates. We remark that the minimum number of swaps required to change one vote to another is the Kendall tau distance (Kendall, 1938) of these two votes. For example, to get from vote abcd to vote adbc, we ﬁrst have to swap candidates c and d, and then we have to swap b and d. The Global Swaps distance counts the number of swaps globally, i.e., it considers the total number of swaps required; this is in contrast to the Local Swaps distance. Since swaps change a vote only in a subtle way, k-global swaps can be considered a less obtrusive notion than k-(local) candidate deletion.

Erd elyi, Lackner & Pfandler

Deﬁnition 3.6. A proﬁle P is k-global swaps single-peaked with respect to an axis A if P can be made single-peaked with respect to A by performing at most k swaps of consecutive candidates in the proﬁle. Furthermore, we say that the proﬁle P is k-global swaps singlepeaked consistent if there exists an axis A such that P is k-global swaps single-peaked with respect to A. Let GS(P) denote the smallest k such that P is k-global swaps single-peaked consistent.

Note that these swaps can be performed wherever we want we can have k swaps in only one vote, or one swap each in k votes. Since rearranging a total order to obtain any other total order requires at most m 2 swaps, we know that GS(P) m 2 n.

Example 1 (continued). It is possible to make P single-peaked consistent by swapping d and e in vote 1 and swapping a and b in vote 2. This gives GS(P) = 2.

k-Local Swaps (LS)

We can also consider a local , per-vote budget for swaps, i.e., we allow up to k swaps per vote. This distance measure has been introduced by Faliszewski et al. (2014) as Dodgsonk.

Deﬁnition 3.7. A proﬁle P is k-local swaps single-peaked with respect to an axis A if P can be made single-peaked with respect to A by performing at most k swaps per vote. Furthermore, P is k-local swaps single-peaked consistent if there exists an axis A such that P is k-local swaps single-peaked with respect to A. Let LS(P) denote the smallest k such that P is k-local swaps single-peaked consistent.

Note that LS(P) m 2 always holds.

Example 1 (continued). Since only one swap is required in 1 and 2 each, we have LS(P) = 1.

Faliszewski et al. (2014) also introduce the Perception Flipk distance. An election E = (C, P) is k-perception ﬂip single-peaked with respect to an axis A if for every vote V in P, the axis A can be transformed to an axis A by at most k swaps of consecutive candidates so that V is single-peaked with respect to A . We show in the following lemma that Perception Flipk and k-Local Swaps are identical. In other words, we show that swapping consecutive candidates in the vote or in the axis has the same power .

Lemma 3.8. Let E = (C, P) be an election and A an axis on C. The proﬁle P is k-local swaps single-peaked with respect to A if and only if P is k-perception ﬂip single-peaked with respect to A.

Proof. Given two total orders on the candidate set C, we deﬁne a permutation p(T1, T2) from {1, . . . , m} to {1, . . . , m} as follows: i maps to j if the i-th largest element in T1 equals the j-th largest element in T2. For T1 : bac and T2 : cab we have p(T1, T2) = 321, where 321 is a short form for the permutation {1 7 3, 2 7 2, 3 7 1}. Note that given a vote V and an axis A, the vote V is single-peaked with respect to A if and only if p(A, V ) consists of a decreasing sequence followed by an increasing sequence. (The top-ranked candidate in V corresponds to 1 in the permutation, hence V being single-peaked with respect to A corresponds to p(A, V ) being a V-shaped sequence.) Performing swaps in either V or A

Computational Aspects of Nearly Single-Peaked Electorates

implies that the permutation p(A, V ) is permuted. Swapping the j-th largest and the (j+1)- th largest element in V implies that j and j + 1 are exchanged in p(A, V ). Analogously, swapping the i-th and (i+1)-th largest element on A implies that in p(A, V ) the elements in position i and i+1 are exchanged. If we view a sequence of swaps as a permutation σ, then the number of swaps is equal to the number of inversions in σ, i.e., the number of pairs i < j with σ(i) > σ(j). In the case of swaps in the vote, the permutation σ is directly applied to p(A, V ); in the case of swaps in the axis the inverse σ 1 is applied to p(A, V ). Consequently, a vote V can be made single-peaked with respect to A by at most k swaps if and only if there exists a permutation σ with at most k inversions such that σ applied to p(A, V ) consists of a decreasing sequence followed by an increasing sequence. Analogously, an axis A can be transformed by at most k swaps so that a vote V is single-peaked if and only if there exists a permutation σ with at most k inversions such that σ 1 applied to p(A, V ) consists of a decreasing sequence followed by an increasing sequence. The statement of the lemma follows now from the well-known fact that the number of inversions in a permutation π equals the number of inversions in π 1 and, consequently, using the inverse permutations we can transform a series of swaps in V to a series of swaps in A and vice versa.

k-Candidate Partition (CP)

The Candidate Partition distance is similar to Additional Axes: Whereas Additional Axes requires a partition of votes, now we partition the set of candidates. For each candidate set in the partition, the proﬁle restricted this candidate set has to be single-peaked consistent. This notion is useful, for example, in the following situation. Each candidate has an opinion on a controversial Yes/No-issue. Depending on their own preference voters will always rank all Yes-candidates before or after all No-candidates. It might be that when considering only the Yesor only the No-candidates, the election is single-peaked. Therefore, if we acknowledge the importance of this Yes/No-issue and partition the candidates accordingly, we may obtain two single-peaked elections.

Deﬁnition 3.9. Let C1, . . . , Ck+1 be a partition of C. A proﬁle P is k-candidate partition single-peaked with respect to an axis A and C1, . . . , Ck+1 if the proﬁles P[C1], . . . , P[Ck+1] are single-peaked with respect to A. Furthermore, P is k-candidate partition single-peaked consistent if there exist an axis A and a partition C1, . . . , Ck+1 of C such that P is kcandidate partition single-peaked with respect to A and C1, . . . , Ck+1. Let CP(P) denote the smallest k such that P is k-candidate partition single-peaked consistent.

Note that CP(P) m

2 always holds.

Example 1 (continued). We partition the candidates into C1 = {a, e} and C2 = {b, c, d}. Notice that P[C1] is trivially single-peaked consistent because it contains only two candidates. Furthermore, P[C2] contains only votes of the form bcd and dcb. Thus, CP(P) = 1.

We remark that k-candidate partition is related to the notion of k-peaked elections, introduced by Yang and Guo (2014a). A proﬁle P is k-peaked with respect to an axis A if for every vote P there exists a partition C1, . . . , Ck of C that yields single-peakedness of [Ci] with respect to A for every i {1, . . . , k}. In this sense, the k-peaked distance can be considered a local variant of the k-candidate partition distance, as a diﬀerent partition can be chosen for every vote.

Erd elyi, Lackner & Pfandler

k-Clones (CL)

Elkind, Faliszewski, and Slinko (2012) studied clone sets in elections. A clone set is a set of candidates that are ranked consecutively in every vote, but not necessarily in the same order. Clone sets can be used to obtain single-peaked proﬁles via decloning, i.e., clone sets are replaced by a single candidate contained in this clone set. The distance to singlepeakedness is here the minimal number of clones that need to be removed from the election via decloning in order to make it single-peaked.

Deﬁnition 3.10. We say that the proﬁle P is k-clones single-peaked with respect to an axis A, if we can obtain a set C C by removing at most k clones from C via decloning such that the preference proﬁle P[C ] is single-peaked with respect to A. Furthermore, we say that the proﬁle P is k-clones single-peaked consistent if there exists an axis A such that P is k-clones single-peaked with respect to A. Let CL(P) denote the smallest k such that P is k-clones single-peaked consistent.

Note that CL(P) m 1 always holds.

Example 1 (continued). In our example we can obtain single-peakedness by decloning {a, b} and {d, e}. Since CD(P) = 2 and deleting candidates is more general than decloning, CL(P) can not be less than 2. Thus, CL(P) = 2.

k-Width (WI )

Clustered single-peakedness, as introduced by Cornaz et al. (2012), is a notion strongly related to the Clones measure (clone sets are called clusters in their paper). Given a partition of the candidates into clone sets such that the preferences are single-peaked after decloning, the width of a partition is the size of the largest clone set minus one. Since there are several partitions of preferences into clone sets, the distance single-peaked Width is deﬁned as the minimum width among all possible partitions of candidates into clone sets.

Deﬁnition 3.11. We say that the proﬁle P is k-width single-peaked with respect to an axis A, if we can obtain a partition of C into clone sets C1, . . . , Cℓsuch that the size of the largest clone set is k + 1 and the proﬁle resulting from decloning is single-peaked with respect to A. Furthermore, we say that the proﬁle P is k-width single-peaked consistent if there exists an axis A such that P is k-width single-peaked with respect to A. Let WI(P) denote the smallest k such that P is k-width single-peaked consistent.

Note that WI(P) m 1 always holds.

Example 1 (continued). Again, partition C into the clone sets C1 = {a, b}, C2 = {c}, and C3 = {d, e}. The resulting decloned proﬁle is single-peaked, the size of the largest clone set is two, and thus WI(P) = 1.

Another notion appearing in the literature is the Swoon distance introduced by Faliszewski et al. (2014). A proﬁle P is (k, k )-Swoon with respect to A if by removing the top k and the last k candidates from each vote yields a partial proﬁle that is single-peaked with respect to A. Due to the two parameters k and k , this notion does not immediately yield a clear deﬁnition of distance and hence we have excluded it from our study. Note, however, that Local Candidate Deletion is a natural generalization of this concept.

Computational Aspects of Nearly Single-Peaked Electorates

Decision Problems

We now introduce the decision problems we will study. We deﬁne the following problems for X {Voter Deletion, Candidate Deletion, Local Candidate Deletion, Additional Axes, Global Swaps, Local Swaps, Candidate Partition, Clones, Width}.

X Single-Peaked Consistency

Given: An election E = (C, P) and a positive integer k. Question: Is P k-X single-peaked consistent?

X Single-Peaked Evaluation

Given: An election E = (C, P), a positive integer k and an axis2A. Question: Is P k-X single-peaked with respect to A?

The complexity of these problems has not been studied with the exception of Clones Single-Peaked Consistency and Width Single-Peaked Consistency, both of which are solvable in polynomial time (Elkind et al., 2012; Cornaz et al., 2013). Furthermore, independent from our work, Bredereck et al. (2016) have shown that Voter Deletion Single-Peaked Consistency is NP-complete. In Section 6 we will study the complexity of these two decision problems in detail.

4. Basic Results about Single-Peaked Proﬁles

In this section we collect simple facts about the single-peaked restriction, which we will use in several proofs.

Lemma 4.1. Let P be a preference proﬁle containing the vote : c1 . . . cm and its reverse . Then P is either single-peaked with respect to the axis c1 > > cm (and its reverse) or it is not single-peaked at all.

Proof. Since the vote ranks cm last while the vote ranks c1 last, these candidates have to be at the left-most and right-most position on any compatible axis. Note that c1 is the top-ranked candidate of . Hence this already determines the position of all other candidates. Consequently only two axes are possible: c1 > > cm and cm > > c1.

Lemma 4.2 provides an alternative characterization of single-peakedness.

Lemma 4.2. Given an election (C, P), the proﬁle P is not single-peaked consistent with respect to an axis A if and only if there is some voter P and three candidates ci, cj, ck C such that ci > cj > ck on axis A, and ci cj holds as well as ck cj.

Proof. Assume that P is not single-peaked consistent. Then, for each axis A, there has to exist some voter v that is not single-peaked with respect to A. Let c be the top-ranked candidate of voter v. Then there exist candidates c1, c2 C with either c > c1 > c2 or

2. For Additional Axes we assume that k + 1 axes A1, . . . , Ak+1 are given in the input (cf. Deﬁnition 3.5). For Candidate Partition we assume that an axis A together with a partition C1, . . . , Ck is given in the input (cf. Deﬁnition 3.9).

Erd elyi, Lackner & Pfandler

c2 > c1 > c such that c2 c1. Depending on whether c > c1 > c2 or c2 > c1 > c we can instantiate (ci, cj, ck) with either (c, c1, c2) or with (c2, c1, c). It is now easy to see that ci > cj > ck, ci cj and ck cj. Let A be an axis on C. For the converse direction assume that there is some voter v and three candidates ci, cj, ck C such that ci > cj > ck on axis A, ci cj and ck cj. Notice that cj cannot be the top-ranked candidate of voter v as this would contradict ci cj and ck cj. Thus, the top-ranked candidate c lies either left or right of cj on axis A. We consider only the ﬁrst case the other case can be dealt with analogously. It holds that c > cj > ck. Deﬁnition 2.1 now requires c cj ck for v to be single-peaked with respect to A. This condition is, however, violated by our assumption ck cj. Therefore P is not single-peaked consistent.

The following observation says that any subelection of a single-peaked election is also single-peaked.

Lemma 4.3. Let (C, P) be a given election and C C. If P is single-peaked consistent then also P[C ] is single-peaked consistent.

Proof. Assume towards a contradiction that there is some C C such that P[C ] is not single-peaked consistent. Let A be an arbitrary axis ordering C. By Lemma 4.2 there is some voter P and three candidates ci, cj, ck C such that ci > cj > ck on the axis A[C ], ci cj and ck cj. Then, however, it also holds that ci > cj > ck on the axis A since A is an extension of A[C ]. Therefore the right-hand side of Lemma 4.2 holds for every axis A on C. Hence, by Lemma 4.2, P is not single-peaked consistent.

The following lemma is an immediate consequence of the single-peaked classiﬁcation theorem of Ballester and Haeringer (2011). For completeness we prove this much simpler statement directly.

Lemma 4.4. An election (C, P) is not single-peaked if there exist three candidates c1, c2, c3 C and three votes V1, V2, V3 P such that, for i {1, 2, 3}, ci is ranked last in Vi[{c1, c2, c3}].

Proof. It is straightforward to verify that for any axis A on {c1, c2, c3} with candidate ci in the middle, vote Vi is not single-peaked with respect to A. Hence, by Lemma 4.3, (C, P) is not single-peaked.

5. Relations between Notions of Nearly Single-Peakedness

Theorem 5.1 states inequalities that hold for the distance measures under consideration. We hereby show how these measures relate to each other. For an overview consult Figure 1: In this Hasse diagram one distance measure X is above and connected to a distance measure Y if the measure Y can be bounded by a function of measure X. Intuitively, distances at the top are more ﬁne-grained notions. More formally, Figure 1 displays a partial order deﬁned as follows. For two distances measures X and Y , Y X if and only if there exists a function f such that Y (P) f(X(P)) for any proﬁle P.

Computational Aspects of Nearly Single-Peaked Electorates

CL GS VD WI CD LS AA CP LCD

. . . . . . . . . . . . . . . . . . . . . . . . . . .

Clones Global Swaps Voter Deletion Width Candidate Deletion Local Swaps Additional Axes Candidate Partition Local Candidate Deletion

Figure 1: The relation of distance measures (cf. Theorem 5.1). This Hasse diagram shows a partial order deﬁned as Y X if and only if Y can be bounded by a function of X.

Theorem 5.1. Let (C, P) be an election. Then the following inequalities hold:

(1) LS(P) GS(P). (5) VD(P) GS(P). (9) CP(P) WI(P).

(2) LCD(P) CD(P). (6) AA(P) VD(P). (10) CD(P) CL(P).

(3) CD(P) GS(P). (7) CP(P) CD(P). (11) WI(P) CL(P).

(4) LCD(P) LS(P). (8) CP(P) LS(P). (12) AA(P) (6 CL(P))!.

This list is complete in the following sense: Inequalities that are not listed here and that do not follow from transitivity do not hold in general.

Proof. Inequalities 1 and 2 are immediate consequences from the deﬁnitions since LS permits more swaps than GS and LCD is more ﬂexible than CD. Inequalities 3 and 4 are due to the fact that swapping two candidates in a vote is at most as eﬀective as removing one of these candidates. Similarly, for Inequality 5 observe that removing the corresponding voter is at least as eﬀective as swapping two candidates in the vote. Concerning Inequality 6 observe that instead of deleting a voter we can always add an additional axis for this voter. Inequality 7 follows from the fact that putting each deleted candidate in its own partition leads to single-peakedness if deleting these candidates does. In order to show Inequality 8 let P be k-local swaps single-peaked consistent. This means that there exists an axis A such that after performing at most k swaps per voter, P becomes single-peaked with respect to A. Without loss of generality assume that the axis A is c1 > c2 > > cm. We now partition the candidates in k + 1 sets S0, . . . , Sk. This is done by putting the i-th largest element of A into the (i modulo k + 1)-th set. Since we assume that A is c1 > c2 > > cm, we can equivalently say that ci is put into the (i modulo k + 1)-th set, i.e., the c1 in S1, the c2 in S2, the ck in Sk and ck+1 in S0. Let S {S0, . . . , Sk}. Towards a contradiction assume that P[S] is not single-peaked with respect to A[S]. By Lemma 4.2 there exists some voter P and three candidates cx, cy, cz C with x < y < z, cx cy and cz cy. On axis A the distance between cx and cy respectively cy and cz is at least k + 1, i.e., at least k elements lie in between

Erd elyi, Lackner & Pfandler

them. We know that at most k swaps in can make this vote single-peaked with respect to A. Let denote this swapped vote. Necessarily, these swaps have to either cause that cy cy 1 cx+1 cx holds or that cy cy+1 cz 1 cz holds in

(depending whether the top-ranked candidate of is right or left of cy). Let us focus on the case that the swaps ensure that cy cy 1 cx+1 cx the other case is analogous. For , contrary to , it holds that cx cy. Hence these swaps have to cause that cy cx holds. In addition, at least k elements, namely cx+1, . . . , cy 1, have to be in between them. This requires at least k + 1 swaps which contradicts the fact that at most k swaps suﬃce. Therefore, for all partition sets S, P[S] is single-peaked consistent and CP(P) LS(P). To prove Inequality 9, consider a partition into clone sets. If we partition C in sets so that every set contains at most one element from each clone set, then we obtain a partition consisting of WI(P) + 1 sets, since the original partition consisted of sets with at most WI(P) + 1 elements. The given proﬁle is WI(P)-candidate partition single-peaked with respect to this partition and hence CP(P) WI(P). Inequality 10 is an immediate consequence of the deﬁnitions since removing clones is a restricted form of deleting candidates. To see Inequality 11 note that CL is the total number of candidates removed via decloning whereas WI only measures the number of candidates removed in the largest clone set. For Inequality 12, let C be the reduced candidate set obtained by decloning and let A

be an axis such that P[C ] is single-peaked with respect to A . We will show that by building upon A we can construct an axis compatible with all votes that order certain candidates (namely D1 D2, as deﬁned below) in the same way. Let D1 be the set of all candidates appearing in clone sets of size at least 2 and let D2 be the set of all right and left neighbors on A of candidates in D1 C . To bound the size of D1 observe that in every clone set of size c exactly c 1 candidates are decloned and for c 2 it holds that c 2(c 1). Thus, we can bound |D1| 2 CL(P). Since D2 contains at most twice as many candidates as D1, it holds that |D2| 4 CL(P). Hence, |D1 D2| 6 CL(P) and the total number of permutations on D1 D2 is bounded by (6 CL(P))!. For each possible permutation of D1 D2 we consider a separate axis, i.e., two votes share the same axis only if they agree on the order of all candidates in D1 D2. Let T be a ﬁxed order on D1 D2; we write a T b to compare two candidates with respect to T. We intend to build an axis that is compatible with all votes agreeing with T on the order of candidates in D1 D2. This is done as follows: Let C be a clone set and d its representative on A , i.e., d is the unique candidate in C that has not been decloned. Further let c and e be the elements left and right of d on A , respectively. We replace the contiguous sequence c > d > e of A with c > T[C ] > e if c T d and with c > T[C ] > e if d T c, i.e., the elements of C are ordered descending (ascending) according to T if c is larger (smaller) than d in all votes compatible with T. We repeat this procedure for all clone sets and obtain an axis A for C that witnesses single-peakedness for all votes compatible with T. To see that this is the case, we employ Lemma 4.2: Assume towards a contradiction that there is some voter in P and three candidates ci, cj, ck C such that ci > cj > ck on axis A, and ci cj holds as well as ck cj. If the representatives of ci, cj, and ck are all diﬀerent, then also the representatives violate the single-peaked condition, which contradicts our assumption that A is a single-peaked axis for all representatives. If ci, cj,

Computational Aspects of Nearly Single-Peaked Electorates

Voter Deletion . . . . . . . . . . . . . . . . VD (P) = 1 4 4 1 1 9 9 Candidate Deletion . . . . . . . . . . . CD (P) 3 = 4 4 3 3 11 Local Candidate Deletion . . . LCD (P) 3 = 3 3 11 Global Swaps . . . . . . . . . . . . . . . . . GS (P) 2 2 2 = 4 2 2 9 9 Local Swaps . . . . . . . . . . . . . . . . . . .LS (P) 2 2 2 = 2 2 11 Additional Axes. . . . . . . . . . . . . . .AA (P) 5 5 6 = 5 11 Candidate Partition. . . . . . . . . . .CP (P) 8 7 8 = Clones . . . . . . . . . . . . . . . . . . . . . . . . CL (P) 10 10 10 10 10 10 10 = 12 Width . . . . . . . . . . . . . . . . . . . . . . . . WI (P) 10 10 10 10 10 10 10 =

Table 1: Inequalities regarding the distance measures. This table should be read as follows. Measures in the left-most column are bounded ( ) by a function of the measures in the top row. Numbers point to the corresponding counterexample if no such bound exists.

and ck all have the same representative, then we obtain a contradiction to our assumption that ci cj and ck cj from the fact that either ci cj ck (or the reverse) holds in all votes compatible with T. If ci, cj, and ck have two representatives in total, we can assume without loss of generality that cj and ck share the same representative (i.e., they are in the same clone set), since if ci and ck are in the same clone set then also cj is in this clone set. (The case where ci and cj share the same representative is analogous.) Observe that {cj, ck} D1 and hence ci D2. Thus the order of these three candidates is determined by T and therefore the same in all votes under consideration. Furthermore, cj and ck are consecutive in T since they are in the same clone set and hence, due to our assumption that ci cj and ck cj, the only possibility to order the three candidates is ci ck cj. This, however, implies that either ci > ck > cj or the reverse holds on A by our construction, a contradiction. Therefore, we conclude that all votes compatible with T are single-peaked with respect to our constructed axis A, and consequently, we can bound AA(P) (6 CL(P))!. It remains to show that the inequalities listed in the theorem statement are indeed all inequalities that hold for these measures. To this end we provide counterexamples for each remaining case of the following form: To show that measure X cannot be bounded measure Y, we present a sequence of elections with arbitrary large X and constant Y. In these sequences of elections either the number of votes n or the number of candidates m (or both) is growing. Table 1 oﬀers an overview by pointing to the corresponding counterexample.

Counterexample 1 (VD cannot be bounded by CD, AA and CP): Consider the preference proﬁle on the candidate set C = {c1, . . . , cm} with the following 2m votes:

There are m votes of the form: c1 c2 . . . cm.

There are m votes of the form: cm c2 c3 . . . cm 1 c1.

Erd elyi, Lackner & Pfandler

The corresponding preference proﬁle P is not single-peaked consistent. This is because c2 has to be next to both c1 and cm on any suitable axis but both have to be either the left-most or right-most element. Consequently, VD(P) = m. Removing candidates instead of voters is far more useful in this case. When we remove either c1 or cm, P becomes singlepeaked and hence CD(P) = 1. Since we have only two distinct votes, we require two axes to make P single-peaked and hence AA(P) = 1. Furthermore, notice that we can obtain single-peaked consistency by partitioning the candidates into two sets C1 = {c1, cm} and C2 = {c2, . . . , cm 1}, hence CP(P) = 1.

Counterexample 2 (Neither GS nor LS can be bounded by VD, AA, CD, LCD and CP): This counterexample is similar to the previous one but P consists of only two votes. Let C = {c1, . . . , c3m+1} be the set of candidates.

There is one vote of the form: c1 c2 . . . c3m+1.

There is one vote of the form: c3m+1 c2 c3 . . . c3m c1.

If we consider P [{c1, cm+1, c2m+1, c3m+1}], we observe that this restricted proﬁle is not single-peaked. Consequently, by Lemma 4.3, P is not single-peaked as well. If we want to make P single-peaked via swaps, at least two of {c1, cm+1, c2m+1, c3m+1} have to swap position. This requires at least m swaps and consequently GS(P) LS(P) m. Since there are only two votes, AA(P) = VD(P) = 1. As in the previous counterexample removing either c1 or c3m+1 yields a single-peaked proﬁle and hence LCD(P) = CD(P) = CP(P) = 1.

Counterexample 3 (Neither CD nor LCD can be bounded by VD, AA and CP): This time we consider three votes on the candidates C = {c1, . . . , c2m}.

There is one vote 1 of the form: c1 c2 . . . c2m.

There is one vote 2 of the form: c2m c2m 1 . . . c1.

There is one vote 3 of the form: cm . . . c1 cm+1 . . . c2m.

By Lemma 4.1 we only have to consider the axis c1 > c2 > > c2m for P = ( 1, 2, 3). The third vote 3 is however not single-peaked with respect to this axis. Hence VD(P) = AA(P) = 1. Also, we have that CP(P) = 1 since P[{c1, . . . , cm}] and P[{cm+1, . . . , c2m}] are single-peaked consistent. However, we have to remove a lot of candidates to obtain a single-peaked proﬁle. Indeed, we have to remove candidates such that the indices of the remaining candidates in 3 are either increasing or decreasing. That are at least m 1 to remove and hence CD(P) LCD(P) m 1.

Counterexample 4 (Neither VD, GS nor CD can be bounded by LCD and LS): We consider an election with 3n votes on the candidates C = {c1, . . . , c3n}.

There are n votes 1, . . . , n of the form: c1 c2 . . . c3n.

There are n votes n+1, . . . , 2n of the form: c3n c3n 1 . . . c1.

Computational Aspects of Nearly Single-Peaked Electorates

The remaining votes are obtained from the ﬁrst vote by swapping the last two candidates in the i-th block consisting of three candidates. Formally, for each i, 1 i n there is a vote 2n+i of the form: c1 . . . c3(i 1) 1 c3(i 1) c3(i 1)+2 c3(i 1)+1 | {z } i-th block

c3i . . . c3n.

Let P = ( 1, 2, . . . , 3n). By using Lemma 4.4 it is easy to check that for each 1 i n, P[{c3(i 1)+2, c3(i 1)+1, c3i}] is not single-peaked consistent. By Lemma 4.3, P is not single-peaked consistent. Also, this implies that we have to remove at least one candidate in each set {c3(i 1)+2, c3(i 1)+1, c3i} in order to make P single-peaked consistent. Therefore CD(P) n. Since GS(P) CD(P) also GS(P) n. We now want to prove a lower bound on VD(P). If we delete n 1 votes then at least one vote of { 1, . . . , n}, one of { n+1, . . . , 2n} and one of { 2n+1, . . . , 3n} remains. Again by Lemma 4.3 and 4.4, P is not single-peaked consistent. Hence VD(P) > n 1. Finally, notice that the votes 2n+1, . . . , 3n can be turned into vote 1 by a single swap, which shows that LS(P) = 1. Since LCD(P) LS(P) also LCD(P) = 1.

Counterexample 5 (AA cannot be bounded by CD, LCD and CP): In this example we use n votes on the candidates C = {c1, . . . , cn+1}.

For each i, 1 i n, there is one vote i of the form: cn+1 ci ci 1 . . . c1 ci+1 ci+2 . . . cn.

Let us consider the preference proﬁle P = ( 1, 2, . . . , n). All votes have the same top-ranked candidate but diﬀerent candidates in the second place. If this preference proﬁle was single-peaked then these second-place candidates had to be either left or right of the peak. This is not possible for three or more candidates. Hence the proﬁle P containing three or more votes is not single-peaked. Thus, AA(P) n

3 1. Deleting cn+1 however makes P single-peaked with respect to the axis c1 > c2 > > cn and hence CD(P) = LCD(P) = CP(P) = 1.

Counterexample 6 (AA cannot be bounded by LS): We consider n votes on 4n candidates C = {c1, . . . , c4n}.

For each i, 1 i n, there is one vote i of the form: c1 . . . c4i 4 c4i c4i 2 c4i 1 c4i 3 c4i+1 . . . c4n.

Let P = ( 1, . . . , n). The preference proﬁle P is not single-peaked consistent since the restricted proﬁles P[{ci 3, ci 2, ci 1, ci}], i {1, . . . , n}, are neither. With ﬁve swaps in each vote we can make these votes identical and hence LS(P) 5. Even any pair of votes in P is not single-peaked. Hence AA(P) n

Counterexample 7 (CP cannot be bounded by LCD): Consider an election with 3n votes on the candidates C = {c1, . . . , c3n}.

For each i, 1 i 3n, there is one vote i of the form: c1 . . . ci 1 ci+1 . . . c3n ci.

Erd elyi, Lackner & Pfandler

Let P = ( 1, . . . , 3n). Since the lowest ranked candidates have to be either at the left-most or right-most position on the axis and there are more than two lowest ranked candidates, this proﬁle is not single-peaked consistent. However, when the last-ranked candidate is removed in each vote, the proﬁle becomes single-peaked consistent and hence LCD(P) = 1. Concerning CP(P), notice that any partition into n sets contains a set with at least three candidates and thus, by Lemma 4.4 does not yield a single-peakedness. Hence n candidate partitions are not enough to obtain single-peaked consistency and hence CP(P) n.

Counterexample 8 (CP cannot be bounded by VD and AA): Consider the candidate set C = {c1, . . ., cm2} and the following three votes:

There is one vote 1 of the form: c1 c2 . . . cm2.

There is one vote 2 of the form: cm2 cm2 1 . . . c1.

There is one vote 3 of the form: c1 cm+1 c2m+1 . . . cm(m 1)+1 c2 cm+2 . . . cm(m 1)+2 . . . cm c2m c3m . . . cm2.

Let P = ( 1, 2, 3). This preference proﬁle is not single-peaked but VD(P) = 1 and AA(P) = 1. The candidates, however, have to be partitioned into many sets in order to obtain single-peakedness. First, observe that by Lemma 4.1 we only have to consider the axis c1 > c2 > > cm2. Let us now consider vote 3. Since we have ﬁxed an axis we can consider longest increasing and decreasing subsequences in this vote. Note that both increasing and decreasing subsequences have a length of less than 2m. Hence a subset of the candidates cannot be single-peaked if it contains more than 4m candidates. We therefore have to partition the candidates of P into sets of cardinality at most 4m and by that CP(P) m

Counterexample 9 (VD and GS cannot be bounded by CL and WI): This counterexample uses 3n votes and three candidates.

There are n votes are of the form: c1 c2 c3.

There are n votes are of the form: c1 c3 c2.

There are n votes are of the form: c2 c3 c1.

Since all three candidates appear at the last position in votes, n votes have to be deleted to make this proﬁle single-peaked. Analogously, at least n swaps have to be performed. Since {c2, c3} can be decloned, CL and WI can be bounded by 1.

Counterexample 10 (Neither WI nor CL can be bounded by GS, LS, CP, CD, VD, AA, and LCD): Consider an election with four votes and m candidates.

There is one vote 1 of the form: c1 c2 . . . cm.

There is one vote 2 of the form: cm cm 1 . . . c1.

There is one vote 3 of the form: c1 c2 . . . cm 2 cm cm 1.

Computational Aspects of Nearly Single-Peaked Electorates

There is one vote 4 of the form: cm 1 cm 2 . . . c1 cm.

Let P = ( 1, . . . , 4). Since P has three distinct last-ranked candidates, it is not singlepeaked. Swapping candidates cm 1 and cm in 3 provides us with a single-peaked proﬁle according to axis c1 > c2 > > cm, thus GS(P) = 1. Let us consider CL and WI . There are three last-ranked candidates: c1, cm 1 and cm. At least two of them have to be contained in a clone set. As can easily be veriﬁed, such a clone set would have to be of size at least m. Hence, CL(P) WI(P) m 1. Since GS is an upper bound for LS, CP, CD, VD, AA, and LCD, none of them can bound WI or CL.

Counterexample 11 (Neither CD, LCD, GS nor LS can be bounded by WI): We consider an election with three votes and 2m + 1 candidates.

There is one vote 1 of the form: c1 c2 . . . c2m+1.

There is one vote 2 of the form: c2m+1 c2m . . . c1.

There is one vote 3 of the form: c2 c1 c4 c3 . . . c2m 2 c2m 3 c2m c2m 1 c2m+1.

Every candidate with an odd index is part of a valley, i.e., with respect to the axis ﬁxed by 1 and 2 all candidates with odd indices are ranked below their two neighbors with respect to 3. Hence LCD is at least m and by the Inequalities 2, 3 and 4 so are CD, GS and LS. On the contrary, if we put, for all i {1, . . . , m}, c2i and c2i 1 in a clone set, we obtain a single-peaked proﬁle. Since all these clone sets are of size 2, WI is bounded by 1.

Counterexample 12 (CL cannot be bounded by WI): Let C = {c1, . . . , c3m}. We deﬁne 3m votes that are contained in P. For every sequence s of length m on the alphabet {X, Y, Z} we deﬁne a vote. The i-th entry of s determines the order of c3i 2, c3i 1, c3i. If s[i] = X then we choose the order c3i 2 c3i 1 c3i. If s[i] = Y then we choose the order c3i 2 c3i c3i 1. If s[i] = Z then we choose the order c3i 1 c3i c3i 2. The vote corresponding to s is now deﬁned as

{c1, c2, c3} {c4, c5, c6} {c3m 2, c3m 1, c3m}

and the order in these sets is given by the sequence s and the rules as deﬁned above. We have to remove m candidates to make this proﬁle single-peaked, i.e., CD(P) = m. By Inequality 10, CL(P) m. In contrast, grouping c3i 2, c3i 1, c3i together in clone sets (for all i {1, . . . , m}) and decloning accordingly yields a single-peaked proﬁle and hence WI(P) is bounded by 2.

We conclude this section by illustrating how the inequalities stated in Theorem 5.1 can be used to obtain new results. More speciﬁcally, we will show that there are preference proﬁles that are close to being single-peaked but do not have a weak Condorcet winner in contrast to single-peaked proﬁles for which a weak Condorcet winner is guaranteed. A weak Condorcet winner is a candidate that is preferred to each other candidate by at least half of the voters.

Proposition 5.2. For every m 3 and n 1 there is an election E = (C, P) with 2n + 1 votes and m candidates such that GS(P) = 1, CL(P) = WI(P) = 2 and P does not have a weak Condorcet winner.

Erd elyi, Lackner & Pfandler

Proof. Let the set of candidates be C = {a, b, c} {d1, . . . , dm 3}. The proﬁle P contains the following votes:

a single vote of the form: b c a d1 . . . dm 3,

n votes of the form: a b c d1 . . . dm 3, and

n votes of the form: c a b d1 . . . dm 3.

It is straightforward to verify that the proﬁle P does not have a weak Condorcet winner since it contains a cycle on a, b, c. Notice that P becomes single-peaked with respect to axis b > a > c > d1 > > dm 3 if we swap candidates b and c in the ﬁrst vote. Hence, we know that GS(P) = 1. Furthermore, we obtain a single-peaked proﬁle via decloning the clone set {a, b, c} and consequently CL(P) = WI(P) = 2.

Due to the inequalities stated in Theorem 5.1, the result of Proposition 5.2 holds also if GS(P) is replaced by one of the measures VD, CD, LCD, LS, AA, and CP. (In principle these measures could be smaller than GS but the proﬁle is not single-peaked and the distance is only 1.) Therefore, even a distance of 1 to single-peakedness (with respect to the VD, CD, LCD, LS, AA, CP, and GS) does not help to avoid the Condorcet paradox. Let us now brieﬂy consider proﬁles with CL(P) = 1 or WI(P) = 1. In contrast to our previous result, such proﬁles preserve an important property of single-peaked proﬁles, namely that weak Condorcet winners are guaranteed.

Proposition 5.3. An election E = (C, P) with CL(P) = 1 or WI(P) = 1 has a weak Condorcet winner.

Proof. If this statement holds for WI(P) = 1, it also holds for CL(P) = 1 since all proﬁles with CL(P) = 1 satisfy WI(P) = 1. Let C1, . . . , Ck be a partition of candidates into clone sets so that decloning these sets yields a single-peaked proﬁle. Let C be the corresponding set of decloned candidates, i.e., P[C ] is single-peaked. Let w be a weak Condorcet winner of P[C ] and let w Ci. Observe that |Ci| 2 since WIP = 1. For all candidates c C \Ci and all candidates d Ci, d is preferred to c by at least half the voters of P. If Ci = {w}, w is a weak Condorcet winner in P. If |Ci| = 2 and the number of voters is odd, one of these two candidates is preferred over the other by more than half of the voters in P; hence this preferred candidate is a weak Condorcet winner. If |Ci| = 2 and the number of voters is even, either one of these two candidates is preferred over the other by more than half of the voters in P and thus is a weak Condorcet winner or these two candidates are preferred over each other by exactly half of the voters, hence they are both weak Condorcet winners.

6. Computational Results

In this section we study the complexity of X Single-Peaked Consistency and X Single Peaked Evaluation for X {Voter Deletion, Candidate Deletion, Local Candidate Deletion, Additional Axes, Global Swaps, Local Swaps, Candidate Partition}. The general theme is that X Single-Peaked Consistency is NP-complete whereas X Single Peaked Evaluation is solvable in polynomial time. The exception is the Candidate Deletion distance, for which also the consistency problem requires only polynomial time.

Computational Aspects of Nearly Single-Peaked Electorates

We do not consider consistency problems corresponding to the Clones and Width distance as it was already established that these are solvable in polynomial time (Elkind et al., 2012; Cornaz et al., 2013).

6.1 Hardness Results

We start with the complexity analysis of voter deletion single-peaked consistency. In the reduction we are going to cascade two or more preference proﬁles. The following deﬁnition captures this operation.

Deﬁnition 6.1. Let (C1, P1) and (C2, P2) be two elections with C1 C2 = . Furthermore, let P1 = ( 1, . . . , n) and P2 = ( 1, . . . , n). We deﬁne P1 P2 = ( 1, . . . , n), where for any 1 i n the total order i is deﬁned by

c i c iﬀ(c, c C1 and c i c ) or (c, c C2 and c i c ) or (c C1 and c C2).

Note that P1 P2 is always a preference proﬁle on C1 C2.

Lemma 6.2. Let (C1, P1) and (C2, P2) be two elections with C1 C2 = . Assume that:

P1 and P2 are single-peaked consistent with respect to the axes A1 and A2, respectively.

The votes in P2 have at most 2 distinct top-ranked candidates.

These (two) top-ranked candidates are adjacent on the axis A2.

Then P1 P2 is single-peaked.

Proof. We are going to construct an axis A in a way that P1 P2 is single-peaked with respect to A. First we split A2 in two parts A 2 and A 2. If P2 contains votes with two distinct top-ranked candidates (which have to be adjacent), we split A2 in between these two candidates. If all votes in P2 share the same top-ranked candidate, we split A2 left of this candidate (this is arbitrary). The new axis A is A 2 followed by A1 and then A 2, i.e., A 2 > A1 > A 2. The correctness proof of this construction is straightforward.

Before we start with the hardness proof, let us ﬁrst make the following observation.

Observation 6.3. We are given a set of candidates C = {a, b, c, d} and the following three votes: d: acbd, e: cbda, and ne: dcba. Then the preference proﬁle ( d, e) is singlepeaked with respect to the axis a > c > b > d and ( e, ne) is single-peaked with respect to the axis d > c > b > a. The proﬁle ( d, ne) is not single-peaked consistent3.

We now show NP-hardness via a reduction from the clique problem, a well-known NPcomplete problem. We remark that the following result has been proven independently by Bredereck et al. (2016) in a more general form that also applies to domain restrictions other than single-peakedness.

3. Indeed, ( d, ne) corresponds to an α-conﬁguration in Ballester and Haeringer s (2011) characterization of the single-peaked domain and thus cannot be single-peaked consistent.

Erd elyi, Lackner & Pfandler

Given: A graph (VG, EG) and a positive integer s. Question: Does (VG, EG) contain a clique of size s, i.e., has the graph (VG, EG) an induced subgraph of size s that is complete?

Theorem 6.4. Voter Deletion Single-Peaked Consistency is NP-complete.

Proof. To show hardness we reduce from Clique. Let VG = {v1, . . . , vn}. Each vertex vi has four corresponding candidates c1 i , . . . , c4 i . We consequently have C = {c1 1, . . . , c4 1, c1 2, . . . , c4 2, . . . , c1 n, . . . , c4 n}. The votes directly correspond to vertices and thus P = ( 1, . . . , n). In order to deﬁne the votes we introduce three functions creating partial votes. For a, b, c, d C, let fd(a, b, c, d) = acbd, fe(a, b, c, d) = cbda, and fne(a, b, c, d) = dcba. If we consider fd, fe and fne as votes then by Observation 6.3 (fd, fe) and (fe, fne) are singlepeaked consistent but (fd, fne) is not. Next we deﬁne a function p(i, j), mapping a pair in {1, . . . , n}2 to a total order on {c1 j, . . . , c4 j}.

fd(c1 j, c2 j, c3 j, c4 j) if i = j, fe(c1 j, c2 j, c3 j, c4 j) if {i, j} EG, fne(c1 j, c2 j, c3 j, c4 j) if {i, j} / EG.

The intuition behind function p(i, j) is to encode a row of the adjacency matrix of G as a vote in the preference proﬁle P. To this end, we put in cell (i, j) the result of fe if there is an edge between i and j. If there is no edge between i and j, then we put the result of fne in cell (i, j). In the special case i = j (we are in the diagonal of the matrix) we put the result of fd in the cell. Let the partial proﬁles representing the columns of the adjacency matrix be deﬁned as Pj = (p(1, j), . . . , p(n, j)), for 1 j n. We are now going to deﬁne the preference proﬁle P = ( 1, . . . , n) by P = P1 P2 Pn. To conclude the construction let E = (C, P) and k = n s, i.e., we are allowed to delete k voters from E in order to obtain a single-peaked proﬁle. The intention behind the construction is that the voters in a single-peaked proﬁle will correspond to a clique. We claim that G has a clique of cardinality s if and only if it is possible to remove at most k voters from P in order to make the resulting preference proﬁle single-peaked consistent. Assume that there is a clique I = { i1, . . . , is} with |I| = s. Let P = ( i1 , . . . , is). Thereby we keep only those voters whose corresponding vertices are contained in the clique I. Observe that the election E = (C, P ) can be obtained by deleting k = n s voters from the proﬁle P. It remains to show that P is indeed single-peaked consistent. Let Ci = {c1 i , c2 i , c3 i , c4 i } for i {1, . . . , n}. Since I is a clique, for each x, y I, x = y, there is an edge {x, y} EG. Thus, for every i {1, . . . , n}, P [Ci] either contains only instantiations of fd and of fe (if ci is in the clique) or only contains fe and fne (if ci is not in the clique). By Observation 6.3, we conclude that P [Ci] is single-peaked consistent. Now we intend to use Lemma 6.2 to show that also P is single-peaked. Note that P [Ci] contains at most two distinct top-ranked candidates. In addition, these two top-ranked candidates are adjacent on the axis which gives single-peaked consistency, as can be seen as follows: Consider again Observation 6.3. For (fd, fe) the top-ranked candidates a and c are adjacent on the axis a > c > b > d. The same holds for (fe, fne) with axis d > c > b > a and c, d

Computational Aspects of Nearly Single-Peaked Electorates

as top-ranked candidates. Since all conditions of Lemma 6.2 are fulﬁlled, we can apply it iteratively. Therefore, P [C1] P [C2], (P [C1] P [C2]) P [C3], etc. are single-peaked consistent and hence also P is single-peaked consistent. Assume that E = (C, P ) is an election that has been obtained from E by deleting at most k voters from P such that P is single-peaked. Then there exists also an election E = (C, P ) which is obtained from E by deleting exactly k voters from P such that P is single-peaked. This is because deleting additional voters from a single-peaked proﬁle can never break single-peakedness. Consequently P contains s votes. Let i1, . . . , is {1, . . . , n} such that P = ( i1, . . . , is). We claim that the vertices {vi1, . . . , vis} form a clique in G. As before, let Ci = {c1 i , c2 i , c3 i , c4 i } for i {1, . . . , n}. By Lemma 4.3 we know that for all i {1, . . . , n}, P [Ci] is single-peaked consistent. Then, by Observation 6.3, each column must not contain an instance of fd together with an instance of fne. Let j {i1, . . . , is}. Observe that by construction vote j contains an instance of fd on candidate set Cj. Consequently, all other votes in P have to be instantiations of fe on Cj and thus vertex vj is adjacent to all other vertices in {vi1, . . . , vis}. Since j is arbitrary, the vertices vi1, . . . , vis form a clique.

We now turn to additional axes single-peaked consistency. Here we make use of a similar construction as presented in Theorem 6.4 with the diﬀerence that we now show NP-hardness via a reduction from the partition into cliques problem (Karp, 1972; Garey & Johnson, 1979).

Partition Into Cliques

Given: A graph (VG, EG) and a positive integer s. Question: Is it possible to partition VG into s sets such that each set of vertices induces a clique on (VG, EG)?

Theorem 6.5. Additional Axes Single-Peaked Consistency is NP-complete.

Proof. Hardness is shown by a reduction from Partition Into Cliques. For the reduction we use the same transformation as presented in the proof of Theorem 6.4 to obtain an election. Then we set k = s 1, i.e., we are searching for a partition of the voters into s disjoint sets such that each of the partitions is single-peaked consistent. Due to the oneto-one correspondence between voters and vertices we can use the partition of the vertices to obtain a partition of the voters and vice versa. With arguments similar to the proof of Theorem 6.4 one can show that a set of vertices is a clique if and only if the corresponding proﬁle is single-peaked consistent.

Remark 6.6. The Partition Into Cliques problem is NP-complete even when one is asked to partition the graph into three cliques. Consequently it follows from the proof of Theorem 6.5 that Additional Axes Single-Peaked Consistency is NP-complete even for k = 2, i.e., for deciding single-peaked consistency with two additional axes.

In the proofs of our next two results, we will provide reductions from the NP-complete Minimum Radius problem (Frances & Litman, 1997). It is deﬁned as follows:

Erd elyi, Lackner & Pfandler

Minimum Radius

Given: A set of strings S {0, 1}ℓand a positive integer s. Question: Has S a radius of at most s, i.e., is there a string α {0, 1}l such that each string in S has a Hamming distance to α of at most s?

Theorem 6.7. Local Candidate Deletion Single-Peaked Consistency is NPcomplete.

Proof. For proving hardness, we reduce from the Minimum Radius problem. Let S {0, 1}ℓand s a positive integer. Given a string β S, let β(i) denote the bit value at the i-th position in β. We are going to construct an LCD Single-Peaked Consistency instance. Each string in S = {β1, . . . , βn} will correspond to two voters. Each bit of the strings will correspond to two candidates. In addition, we have 2ℓs + 2 extra candidates. Consequently, we have C = {c1 1, c2 1, c1 2, c2 2, . . ., c1 ℓ, c2 ℓ, c 1, . . . , c ℓs+1, c 1, . . . , c ℓs+1}. We deﬁne the preference proﬁle with the help of two functions creating total orders.

f0(a, b) = ab f1(a, b) = ba

The vote j, for each j {1, . . . , n}, is of the form

j: c 1 . . . c ℓs+1 fβj(1)(c1 1, c2 1) fβj(2)(c1 2, c2 2) . . . fβj(ℓ)(c1 ℓ, c2 ℓ) c 1 . . . c ℓs+1.

The preference proﬁle P is now deﬁned as ( 1, . . . , n, 1, . . . , n). We claim that (C, P) is s-local candidate deletion single-peaked consistent if and only if S has a radius of at most s. Suppose that S has a radius of at most s, i.e., there is a string α {0, 1}ℓwith Hamming distance at most s to each β S. We consider the following axis A:

c 1 > > c ℓs+1 > fα(1)(c1 1, c2 1) > fα(2)(c1 2, c2 2) > > fα(ℓ)(c1 ℓ, c2 ℓ) > c 1 > > c ℓs+1.

We claim that P is single-peaked with respect to A after deleting at most s candidates in each vote. The deletions for vote j, j {1, . . . , n}, are the following: We delete candidate c1 i in j if and only if α(i) = βj(i). The deletions in j are exactly the same as in j. These are at most s deletions since the Hamming distance between α and every β S is at most s. After these deletions all votes are either subsequences of A or its reverse. Hence we obtain a single-peaked consistent proﬁle. Let P be the partial, single-peaked consistent proﬁle that was obtained by deleting at most s candidates in each vote. First, note that some c {c 1, . . . , c ℓs+1} has not been deleted in any vote since in total at most ℓ s diﬀerent candidates can be deleted. In the same way let c {c 1, . . . , c ℓs+1} be a candidate that has not been deleted in any vote. Now let us consider the proﬁle P [{c , c , c1 i , c2 i }] for any i {1, . . . , ℓ}. We claim that α {0, 1}ℓ, deﬁned in the following way, has a Hamming distance of at most s to all bitstrings in S.

0 if P contains a vote with c c1 i c2 i c , 1 if P contains a vote with c c2 i c1 i c , 1 otherwise.

Computational Aspects of Nearly Single-Peaked Electorates

First, observe that Case 1 and 2 cannot occur at the same time since then P would not be single-peaked consistent. Let βj S, j {1, . . . , n}. Note that if at any position i, βj(i) = α(i) then either c1 i or c2 i had to be deleted in the vote j. Otherwise P would not be single-peaked consistent. Hence |{i {1, . . . , ℓ} | α(i) = βj(i)}| s because otherwise we would require more than s candidate deletions in the corresponding vote j. Hereby we have shown that the Hamming distance of α and βj is at most s.

Theorem 6.8. Local Swaps Single-Peaked Consistency is NP-complete.

Proof. We use the same construction as in the proof of Theorem 6.7. It holds that (C, P) is s-local swaps single-peaked consistent if and only if S has a radius of at most s. This can be shown similarly to the proof of Theorem 6.7 except that we swap candidates instead of deleting them.

The following problem will be useful for showing NP-hardness of Global Swaps Single-Peaked Consistency. Given two votes, x and y, let swaps( x, y) denote the minimum number of swaps of adjacent candidates needed to make x and y equal, i.e., swaps( x, y) is the Kendall tau distance of x and y.

Kemeny Optimal Aggregation

Given: An election (C, P), with P = ( 1, . . . , n), and an integer s. Question: Is there a vote on C such that P

1 i n swaps( i, ) s.

Kemeny Optimal Aggregation was shown to be NP-complete (Bartholdi, Tovey, & Trick, 1989b). Later, this result was strengthened to require only four voters (Dwork et al., 2001; Biedl, Brandenburg, & Deng, 2009).

Theorem 6.9. Global Swaps Single-Peaked Consistency is NP-complete.

Proof. We show NP-hardness of this problem by reduction from Kemeny Optimal Aggregation. Let an instance of Kemeny Optimal Aggregation be given by C = {c1, . . . , cm}, P = ( 1, . . . , n), and s. We deﬁne k, the number of allowed swaps, be deﬁned as 2s. Then we create a new election (C , P ) with C = C {ctop 1 , . . . , ctop 2k+1, clast 1 , . . . , clast 2k+1}, i.e., |C | = m + 4k + 2. For each i {1, . . . , m} we create two votes i and i as follows. The vote i ranks ctop 1 ﬁrst, followed by ctop 2 , ctop 3 , . . ., ctop 2k and ﬁnally ctop 2k+1. Then it ranks the candidates in C in the same order as i does. Finally, it orders the candidates clast 1 . . . clast 2k+1 with descending preference, i.e., clast 2k+1 being the last-ranked candidate. Vote i is the reverse of i. The preference proﬁle P is now deﬁned as ( 1, 1, . . . , n, n). We refer to 1, . . . , n as the non-reversed votes and to 1, . . . , n as the reversed votes. We claim that (C , P ) is k-global swaps single-peaked consistent if and only if (C, P) and s are a yes-instance of the Kemeny Optimal Aggregation problem. Suppose that (C , P ) is k-global swaps single-peaked consistent. Therefore, one can obtain a proﬁle PS from P by applying at most k = 2s swaps such that PS is singlepeaked consistent with respect to an axis A. Since there are 2k + 1 candidates in the set {ctop 1 , . . . , ctop 2k+1} at least one of them must have remained in place in each vote. Analogously,

Erd elyi, Lackner & Pfandler

the same holds for one of the candidates contained in the set {clast 1 , . . . , clast 2k+1}. Let ctop and clast denote these two candidates. From Lemma 4.3 we know that PS[{ctop, c1, . . . , cm, clast}] is single-peaked consistent as well. Observe that all non-reversed votes in PS[{ctop, c1, . . . , cm, clast}] have ctop as top-ranked candidate and clast as last candidate, while in all reversed votes clast is top and ctop is the last-ranked candidate. By Lemma 4.1 all non-reversed votes in PS[{c1, . . . , cm}] must be ordered in the same way and the reversed votes in exactly their reverse order. We denote this ordering of {c1, . . . , cm} by . Notice that turning the non-reversed votes into requires the same number of swaps as turning the reversed votes into . Therefore, k

2 = s swaps are suﬃcient to turn all non-reversed votes into . Taken together, fulﬁlls all properties to be a yes-instance of the Kemeny Optimal Aggregation problem. Assume (C, P) and s describe a yes-instance of the Kemeny Optimal Aggregation problem. Then there is some common ordering , which has in total a swap distance of s to all votes in P. Then, (C , P ) is k-global swaps single-peaked consistent with respect to the axis ctop 1 > ctop 2 > > ctop 2k+1 > [c1, . . . , cn as ordered by ] > clast 1 > clast 2 > > clast 2k+1. This is because all votes can be brought into the form ctop 1 ctop 2 ctop 2k+1 [c1, . . . , cn as ordered by ] clast 1 clast 2 clast 2k+1 or its reverse by using at most k = 2s swaps s swaps for the non-reversed and s swaps for the reversed votes.

Remark 6.10. Since Kemeny Optimal Aggregation with only four voters is NPcomplete (Dwork et al., 2001), it follows from the proof of Theorem 6.9 that Global Swaps Single-Peaked Consistency is NP-complete even for eight voters.

6.2 A Polynomial-Time Algorithm for Candidate Deletion Single-Peaked Consistency

In contrast to the previous hardness results, we are able to show that Candidate Deletion Single-Peaked Consistency can be decided in polynomial time. The algorithm builds upon the O(n m) time algorithm for testing single-peaked consistency by Escoﬃer, Lang and Ozt urk (2008). Since we make some modiﬁcations to the algorithm and also for the sake of completeness we present it here as well. For the remainder of this section let (C, P) be an election with n voters and C = {c1, . . . , cm}.

6.2.1 The Single-Peaked Consistency Algorithm

The algorithm presented here is a modiﬁed version of the algorithm by Escoﬃer et al. (2008). It tests whether a given proﬁle is single-peaked consistent and thus does not consider candidate deletions. Before we start with presenting the algorithm, let us ﬁx some notation.

Deﬁnition 6.11. For C C, let L(P, C ) denote the set of last-ranked candidates in P[C ].

Deﬁnition 6.12. An incomplete axis is a total order on a subset of C with a marked position that indicates where further elements may be added. We denote this position by a star symbol, e.g., the incomplete axis c1 > c2 > > c3 allows additional candidates to be

Computational Aspects of Nearly Single-Peaked Electorates

added right of c2 and left of c3. We write |A| to denote the number of candidates on an incomplete axis A. The boundary of an incomplete axis A, boundary(A), is a quadruple consisting of the two candidates left of the star and the two candidates right of the star, e.g., boundary(c1 > c2 > > c3 > c4 > c5) = (c1, c2, c3, c4). If only one or no candidates exist left/right of the star, the corresponding entries in the quadruple are ϵ, e.g., boundary(c1 > ) = (ϵ, c1, ϵ, ϵ). Given an incomplete axis A and a candidate set C, an axis A extends A if A can be constructed from A by adding elements left or right of the symbol.

The algorithm proceeds iteratively by placing the last-ranked candidates that have not yet been placed. Let C C be the set of candidates that have not yet been positioned on the (incomplete) axis A. The algorithm checks what kind of constraints follow from each vote. If these constraints do not contradict each other, the set of last-ranked candidates L(P, C ) is placed. We denote this procedure by place(A, X) where X = L(P, C ). The procedure place(A, X) returns either a new incomplete axis (extending A by the candidates in X) or the value inconsistent. The algorithm repeatedly invokes place until all elements have been placed or a contradiction has been found. Now we describe place(A, X) in detail since it is also used by our candidate deletion algorithm. Let boundary(A) = (b 1, b1, b2, b 2), i.e., the current incomplete axis A is given as > b 1 > b1 > > b2 > b 2 > . If a condition contains a boundary element and this element is ϵ (i.e., it does not exist), corresponding constraints can be ignored. The following cases are considered for each vote i, i {1, . . . , n}.

Case 1: |L(P, C )| 3. There are three or more candidates that would have to be placed at the positions next to b1 and b2. Since this is not possible, P is not single-peaked consistent; place returns inconsistent.

Case 2: L(P, C ) = {x1, x2}. The candidates x1 and x2 have to be placed at the positions next to b1 and next to b2.

(a) b1 i x1 and b2 i x1: This case cannot occur since x1 is ranked below b1 and b2 and thus cannot be placed after b1 and b2.

(b) x1 i b1 and x1 i b2: There are no constraints for x1 that follow from i.

(c) b2 i x1 and x2 i x1: In this case x1 has to be placed next to b1 and therefore x2 is placed next to b2.

(d) b1 i x1 and x2 i x1: In this case x1 has to be placed next to b2 and therefore x2 is placed next to b1.

All these rules are also applicable if x1 and x2 are interchanged.

Case 3: L(P, C ) = {x}. The candidate x has to be placed either at the position next b1 or b2. It is important that if x is the last candidate to be placed, it can be placed either next to b1 or next to b2.

(a) b1 i x and b2 i x: This case cannot occur since x is ranked below b1 and b2 and thus cannot be placed after b1 and b2.

(b) x i b1 and x i b2: There are no constraints for x.

Erd elyi, Lackner & Pfandler

(c) b2 i x: In this case x has to be placed left, i.e., next to b1.

(d) b1 i x: Then x has to be placed right, i.e., next to b2.

In addition to these three cases, the following constraint is applicable independently of the cardinality of L(P, C ). Let x L(P, C ).

Case 4: If b 1 i b1 and x i b1, or if b 2 i b2 and x i b2, then the candidates b 1, b1, x or x, b2, b 2, respectively, violate the single-peaked condition (cf. Lemma 4.2). Thus place returns inconsistent.

For each vote i, these case distinctions yield constraints on placing the candidates in X. If there is a way to place the candidates in X that is compatible with every vote, place(A, X) has been successful and returns the new incomplete axis. (If there is more than one possibility to place the candidates in X, place chooses arbitrarily.) Otherwise the value inconsistent is returned. To simplify the notation, we deﬁne place(A, ) to return A. As mentioned before, the place procedure described here is similar to the procedure used in the original single-peaked consistency algorithm by Escoﬃer et al. (2008). The main diﬀerence is that the original single-peaked consistency algorithm places all remaining candidates at once as soon there is only one possibility left; place continues to place at most two candidates in each step. In particular, this necessitates Case 4, which did not appear in the original algorithm. The following lemma shows that the place procedure is indeed correct; the proof can be found in the appendix.

Lemma 6.13. Let (C, P) be an election. If the iterative application of place yields an axis A, then (C, P) is single-peaked with respect to A. If at some point place returns inconsistent, then (C, P) is not single-peaked.

The following observation is the main reason why we can employ dynamic programming in our algorithm for deciding the Candidate Deletion Single-Peaked Consistency problem.

Observation 6.14. The place(A, X) procedure places the candidates in X on the incomplete axis A only by considering boundary(A) and thus place does not depend on the full incomplete axis A.

6.2.2 The Candidate Deletion Algorithm

Observation 6.14 states that the (at most) four boundary candidates of an incomplete axis fully determine whether and which further candidates can be placed on the axis. The main idea of our algorithm is to store only incomplete axes that diﬀer in these four candidates, i.e., only incomplete axes with diﬀering boundaries. If two axes with the same boundary are considered, we take the axis with the larger cardinality, i.e., the one with more candidates placed on it. This strategy allows us to use a dynamic programming approach. Our algorithm resembles the previously described single-peaked consistency algorithm in that it places last-ranked candidates ﬁrst. However, since we are allowed to delete candidates, our algorithm does not terminate if at some point three or more last-ranked candidates are encountered (cf. Case 1 in the single-peaked consistency algorithm). Nevertheless,

Computational Aspects of Nearly Single-Peaked Electorates

Algorithm 1: Polynomial-time algorithm for k-candidate deletion single-peaked consistency Theorem 6.16

1 S0[ϵ, ϵ, ϵ, ϵ, ] // S0 contains the empty incomplete axis

2 for i = 1 . . . m do

4 foreach incomplete axis A Si 1 do

5 Let (c1, c2, c3, c4, Y ) be the key of A. // i.e., Si 1(c1, c2, c3, c4, Y ) = A

6 foreach X N(i, Y ) do

7 Anew place(A, X)

8 if Anew = inconsistent then

9 if Si[c1, c2, c3, c4, X] is empty then

10 Si[c1, c2, c3, c4, X] Anew

12 if |Anew| > |Si[c1, c2, c3, c4, X]| then

13 Si[c1, c2, c3, c4, X] Anew

14 return an axis A in Sm with maximum |A|

our algorithm utilizes the place procedure and thus can place at most two candidates in each step (cf. Lemma 4.4). Candidates that would violate the single-peaked condition are not actively deleted but rather cannot be successfully placed. We now describe the algorithm in more detail (cf. Algorithm 1). The algorithm s main data structure is an associative array S containing incomplete axes. The axes are indexed by quintuples (c1, c2, c3, c4, Y ) where c1, c2, c3, c4 C and Y {c2, c3}, i.e., such quintuples constitute keys for S. The associative array my contain at index (c1, c2, c3, c4, Y ) only an incomplete axis A with boundary(A ) = (c1, c2, c3, c4). Furthermore, the candidates in Y have been placed most recently on A; this can either be {c2}, {c3} or {c2, c3}. We write S[c1, c2, c3, c4, Y ] to denote the entry S with key (c1, c2, c3, c4, Y ). We start with S0 containing only the empty incomplete axis . (Recall that marks the position where new candidates can be added to the axis.) We write N(i, Y ) to denote the set containing all X C that may be placed on A in step i of the algorithm; we will deﬁne N(i, Y ) after an overview of the algorithm. Note that at most two of the candidates can be placed and hence 1 |X| 2. So, in step i = 1, for every axis A S0 (only ) and every set of candidates X N(1, Y ), we use the place procedure to place the candidates in X on A. This step gives rise to new incomplete axes. These new axes as well as those in S0 are stored in S1. For i = 2, we continue by placing the candidates in N(2, Y ) for every incomplete axis A S1. Again this creates new incomplete axes, which we store in S2 (in addition to elements from S1). At this point, it might be that S2 already contains an entry with the same key. In this case, we keep the axis with more candidates placed on it. We repeat this procedure until we have considered the sets in N(m, Y ). The associative array Sm now

Erd elyi, Lackner & Pfandler

contains a several incomplete axes; we output a cardinality maximal axis as it requires the minimum number of candidate deletions.

Let us now deﬁne N(i, Y ).

Deﬁnition 6.15. For all 1 i m, let Li = L (P, C \ (L1 Li 1)). Further, ﬁx 1 i m and let Y be the candidates last placed on the incomplete axis. We deﬁne N(i, Y ) to be the set of all X Li Lm satisfying the following conditions:

(i) 1 |X| 2

(ii) X Li =

(iii) L(P, X) = X

(iv) if Y = then L(P, Y X) = Y

Note that S i {1,...,m} Li = C and that some Li s may be empty (more precisely, there might exist some index j m such that Lj, . . . , Lm are empty). The conditions can be intuitively understood as follows: Condition (i) is a necessity if we want to obtain a singlepeaked axis: No more than two last-ranked candidates may be placed on the axis. Condition (ii) is mostly important for showing runtime bounds. Note that condition (iii) implies that if X = {x1, x2}, then there must be a vote i with x1 i x2 and a vote j with x2 j x1. If one candidate would always be ranked below the other, the former had to be placed ﬁrst and the second only in a later step. Condition (iv) guarantees that the candidates in X are never ranked below Y . Candidates that are below Y cannot be placed anymore, i.e., they have been deleted. Intuitively, the correctness of Algorithm 1 rests on two pillars. First, we have observed that the place procedure only considers the four boundary elements of an incomplete axis. Hence, it is correct to identify incomplete axes with the same boundary. Since we search for a cardinality maximal axis, we can safely pick a larger axis if we have the choice (cf. Lines 12 and 13). Second, the correctness of the algorithm relies fundamentally on the correctness of the place procedure, which we have shown in Lemma 6.13. We will now formally prove the runtime bounds and correctness of Algorithm 1.

Theorem 6.16. Candidate Deletion Single-Peaked Consistency can be solved in time O(n m6).

Proof. The runtime bound can be seen as follows. The sets L1, . . . , Lm can be computed in O(m n) time. The associative array Si uses quintuples (c1, c2, c3, c4, Y ) as keys, where Y {c2, c3} Hence Si contains at most 4m4 entries. Let us now bound the size of N(i, Y ). The singleton sets in N(i, Y ) are subsets of Li. Two-element sets in N(i, Y ) contain one element of Li and one of Li Lm. Thus, |N(i, Y )| |Li| + m|Li| = (m + 1)|Li|. The place procedure is executed in step i of the algorithm for every axis in Si 1 and element of N(i, Y ), i.e., at most 4m4(m + 1)|Li| times. If we add up over all iterations we obtain Pm i=1 4m4(m + 1)|Li| = 4m4(m + 1) Pm i=1 |Li| = O(m6) procedure calls. Since place has a runtime of O(n), we require in total O(n m6) time for place calls. Furthermore, N(i, Y ) has to be computed for every axis under consideration. It is straight-forward to verify that N(i, Y ) can be computed in O(n m |Li|) time: At most (m+1)|Li| sets have to be considered and the conditions of Deﬁnition 6.15 can be veriﬁed in O(n) time. Again, adding up over all iterations we obtain a runtime of O(Pm i=1 m4nm|Li|) = O(nm5 Pm i=1 |Li|) = O(nm6), also within the desired time bound.

Computational Aspects of Nearly Single-Peaked Electorates

Let us now prove correctness. For the one direction, let A be a cardinality maximal axis returned by the algorithm. Furthermore, let X1, . . . , Xm be the set of candidates placed in each step of the algorithm to obtain axis A. In particular, this implies that A is a total order on X1 Xm. Since some of those sets may be empty, let X 1, . . . , X ℓbe the selection of non-empty sets. Let P = P[X 1 X m]. Our goal is to show that P is single-peaked with respect to A and we intend to apply Lemma 6.13 to prove this. To do so, we will ﬁrst show for every i, 1 i ℓ, that L(P , X i X ℓ) = X i. We prove this statement by induction. In the following we write N( , Y ) and by that omit the ﬁrst parameter, as the exact step at which a candidate was placed is irrelevant for our argument. Observe that X ℓ N( , X ℓ 1) since X ℓhas been placed on A and X ℓ 1 has been placed on A before that. Thus the conditions listed in Deﬁnition 6.15 apply to X ℓ. In particular L(P , X ℓ) = X ℓholds due to condition (iii), which serves as our base case. For the induction step, assume that L(P , X i+1 X m) = X i+1. We want to show that L(P , X i X m) = X i. Note that for arbitrary X , X it holds that L(P , X X ) = L(P , X L(P , X )). Thus, by our hypothesis, we know that L(P, X i X m) = L(P, X i X i+1). Since X i+1 N( , X i), condition (iv) yields that L(P, X i X i+1) = X i. It follows now immediately from Lemma 6.13 that P is single-peaked with respect to A: We have shown that Algorithm 1 ﬁrst computes place( , X 1) with X 1 = L(P , X 1 X m). Then place is applied on the resulting axis and X 2 = L(P , X 2 X m) is placed on it. This procedure is repeated until we obtain axis A and Lemma 6.13 applies. Thus, (P , X1 Xm) is single-peaked with respect to A. For the other direction, let C be a cardinality maximal subset of candidates such that P = P[C ] is single-peaked. Our goal is to show that Sm contains an axis with the same cardinality as C . Let Xi = L (P , C \ (X1 Xi 1)) for all 1 i m and X0 = . Further let ℓbe the largest index such that Xℓ = . Let us consider Xi and let s(i) = min{1 j m : x Xi and x Lj}. Our ﬁrst goal is to show that Xi N(s(i), Xi 1). To show this we have to check the conditions in Deﬁnition 6.15. First, Xi Ls(i) Lm by deﬁnition of s(i). Condition (i) holds since P[C ] is singlepeaked (cf. Lemma 4.4). Condition (ii) holds also by choice of s(i). Condition (iii) holds because Xi = L (P , C \ (X1 Xi 1)) = L (P , Xi Xℓ) and thus also Xi = L (P , Xi). Finally, condition (iv) holds because Xi 1 = L (P , C \ (X1 Xi 2)) = L (P , Xi 1 Xℓ) and thus also Xi 1 = L (P , Xi 1 Xi). Let us assume that the place procedure is applied to P . First X1 is placed, then X2, etc. Let A1, . . . , Aℓbe the corresponding incomplete axes. Furthermore let A0 be the empty incomplete axis, X0 = and s(0) = 0. We are going to show that for every 0 i ℓ, there exists an incomplete axis A i Ss(i) such that boundary(A i) = boundary(Ai) and |A i| |Ai|. We prove this statement by induction. For i = 0, note that A0 = S0. For the induction step, assume that A i Ss(i) such that boundary(Ai) = boundary(A i) and |Ai| = |A i|. By our previous argument, it holds that Xi+1 N(s(i + 1), Xi). Since A i Ss(i), we compute place(A i, Xi+1). By Observation 6.14, place(A i, Xi+1) is successful (i.e., it does not return inconsistent) if and only if place(Ai, Xi+1) is successful since both have the same boundary. Let A i+1 be the axis returned by place(A i, Xi+1). Then |Ai+1| = |A i+1| since in both cases the same candidates have been placed. Also boundary(Ai+1) = boundary(A i+1), again by Observation 6.14. If A i+1 is stored in Si+1, we have proven the induction step. If

Erd elyi, Lackner & Pfandler

it is not stored, then there exists an A i+1 in Si+1 with boundary(Ai+1) = boundary(A i+1) and |A i+1| |Ai+1|. Also in this case the induction statement holds. We have shown that there exists an incomplete axis A ℓ Ss(ℓ) such that boundary(Aℓ) = boundary(A ℓ) and |A ℓ| |Aℓ|. If such an element exists in Ss(ℓ), it does exist in Sm. Since |Aℓ| = |C |, we have shown that the algorithm returns an axis of maximum cardinality.

Finally, let us remark that very recently a modiﬁcation of this algorithm has been proposed (Przedmojski, 2016) that improves the runtime to O(n m3).

6.3 Complexity of Nearly Single-Peaked Evaluation

In the previous sections we have analyzed the computational complexity of the X Single Peaked Consistency problem. We now turn to the computational complexity of the related X Single-Peaked Evaluation problem, where the axis is additionally given in the input. Due to this additional information, all X Single-Peaked Evaluation problems are solvable in polynomial time in contrast to the consistency problems studied in the Section 6.1. Let us ﬁrst prove that the candidate deletion evaluation problem is solvable in polynomial time, as it is the case for the corresponding consistency problem.

Proposition 6.17. Candidate Deletion Single-Peaked Evaluation can be solved in time O(n m6).

Proof. Let A be the given axis and P the proﬁle for which we want to verify whether it is single-peaked with respect to A. Let P be the proﬁle obtained from P by adding two votes, 1 = A and 2 = A, where A denotes the reverse of axis A. By Lemma 4.1, P

is k-X single-peaked consistent if and only if P is k-X single-peaked with respect to A. By Lemma 4.3, the same statement holds if P and P are restricted to candidate subsets. Thus, applying the candidate deletion algorithm of Section 6.2 to P yields the same result as solving the evaluation problem for P and A.

We now turn to evaluation problems where their corresponding consistency problems are NP-hard.

Proposition 6.18. Voter Deletion Single-Peaked Evaluation can be solved in time O(n m).

Proof. Whenever a vote is not single-peaked consistent with respect to A, we have to delete it. If at most k votes have to be deleted, we know that the proﬁle is k-voter deletion single-peaked consistent with respect to A.

Proposition 6.19. Additional Axes Single-Peaked Evaluation can be solved in time O(k n m).

Proof. Recall that for this evaluation problem all axes are given. Hence it suﬃces to verify that every vote is single-peaked with respect to at least one of the given k + 1 axes.

Theorem 6.20. Local Candidate Deletion Single-Peaked Evaluation can be solved in time O(n m2 log m).

Computational Aspects of Nearly Single-Peaked Electorates

Proof. For every vote P we have to ﬁnd the minimum number of candidates that have to be deleted. We do this by iterating over all candidates p C and calculating a cardinality maximal C C such that [C ] is single-peaked with respect to the given axis A and p is top-ranked in [C ]. For each p, let C1 be the set of candidates containing p and all candidates left of p on A. We have to ﬁnd a (not necessarily contiguous) subsequence of A[C1] of maximum length that is increasing with respect to and contains p. Let C 1 be the set of candidates contained in this maximum increasing subsequence. Then, let C2 be the set of candidates containing p and all candidates right of p. We search for a subsequence of A[C2] of maximum length decreasing with respect to that contains p. Let C 2 be the set of candidates contained in this maximum decreasing subsequence. In this way, we obtain a selection of candidates C 1 C 2 (of maximum cardinality) such that [C 1 C 2] is singlepeaked and p is top-ranked in [C 1 C 2]. We repeat this step for all p C in order to ﬁnd the candidate for which |C 1 C 2| is maximal; let d( ) denote number of required deletions for vote , i.e., d( ) = m |C 1 C 2|. We return LCD(P) = max P d( ). Since ﬁnding a longest increasing subsequence in sequences of length m can be done in time O(m log m) (Schensted, 1961) and we have to do this 2m times per vote, we obtain the claimed runtime.

Theorem 6.21. Global Swaps Single-Peaked Evaluation as well as Local Swaps Single-Peaked Evaluation can be solved in time O(n m3).

Proof. Both algorithms rely on the minswaps( , A) procedure, which computes the minimal number of swaps required to make vote single-peaked with respect to A. Let us ﬁrst describe how this procedure is used and later on give a precise description of minswaps. To solve Global Swaps Single-Peaked Evaluation it suﬃces to execute for each in P the procedure minswaps( , A) and sum over all returned values. If the sum does not exceed the limit k we know that the proﬁle is k-global swaps single-peaked consistent with respect to A. For the Local Swaps Single-Peaked Evaluation the procedure is similar. Here, we check for every in P whether minswaps( , A) k. Let us now describe how minswaps( , A) can be implemented via dynamic programming. In the following, let sw(ci, ) be the minimum number of swaps required to move ci to the last position in , i.e., if if there are k candidates ranked below ci then sw(ci, ) = k. To simplify notation, we assume without loss of generality that A is c1 > c2 > > cm. For 0 i < j m + 1 let s(i, j) be the minimal number of swaps required to transform a vote into a vote such that ci ci 1 c1 as well as cj cj+1 cm, and all candidates in {ci+1, . . . , cj 1} are ranked above all other candidates. Observe that s(i, i + 1) is the number of swaps required to make single-peaked with respect to A such that ci is the peak. Thus, once we have values for s(i, i + 1) for all 1 i m, we can compute the number of swaps required to make single-peaked with respect to A as mini {0,...,m} s(i, i + 1). Thus, minswaps( , A) returns mini {0,...,m} s(i, i + 1). The quantity s(i, j) can be computed via dynamic programming. Let s(0, m+1) = 0 and

s(i, j) = min(s(i 1, j) + sw(ci, [{ci, . . . , cj 1}]),

s(i, j + 1) + sw(cj, [{ci+1, . . . , cj}])),

i.e., to compute s(i, j) we can either start with s(i 1, j) and move ci below ci+1, . . . , cj 1, or we start with s(i, j+1) and move cj below ci+1, . . . , cj 1. In both cases ci ci 1 c1

Erd elyi, Lackner & Pfandler

as well as cj cj+1 cm, and the candidates in {ci+1, . . . , cj 1} are ranked above all other candidates as we intend it to be. We choose the option which requires fewer swaps. Note that s(i, j) has to be computed for O(m2) values, which can be done in O(m3) time. Consequently, minswaps can be computed in O(m3) time. We conclude that Global Swaps Single-Peaked Evaluation as well as Local Swaps Single-Peaked Evaluation can be solved in time O(n m3).

Proposition 6.22. Candidate Partition Single-Peaked Evaluation can be solved in time O(n m).

Proof. Let C1, . . . , Ck+1 be the given partition of C. We can solve this problem in O(n m) time by verifying whether P[Ci] is single-peaked with respect to A[Ci] for every i {1, . . . , k + 1}.

Finally, one can show that the polynomial-time algorithms solving Clones Single Peaked Consistency and Width Single-Peaked Consistency (Elkind et al., 2012; Cornaz et al., 2013) are also applicable to the corresponding evaluation problems and maintain their time bounds; the argument for this is similar to the one of Proposition 6.17.

7. Conclusions and Open Questions

In this work, we have investigated notions of nearly single-peakedness. We have introduced three new notions of nearly single-peakedness and have studied in addition six already established notions. We have drawn a complete picture of the relations between these notions. For ﬁve notions we have shown that deciding nearly single-peaked consistency is NP-complete and for k-candidate deletion we have presented a polynomial-time algorithm. Furthermore, we have analyzed the complexity of the evaluation problem, i.e., the veriﬁcation task, where the axis is given as additional input. In contrast to consistency, all evaluation problems can be decided in polynomial time. We refer the reader to Table 2 for an overview. An obvious direction for future work is to determine the complexity of Candidate Partition Single-Peaked Consistency. Also, we want to remark that all notions of nearly single-peakedness presented in this work are not restricted to single-peakedness, but can also be applied to other domain restrictions (such as the single-crossing restriction). NP-completeness, as we have obtained for several consistency problems, does not rule out the possibility of algorithms that perform well in practice. One approach is to search for ﬁxed-parameter algorithms, i.e., an algorithm with runtime f(k) poly(n) for some computable function f depending only on parameter k. A ﬁrst ﬁxed-parameter algorithm for Voter Deletion Single-Peaked Consistency is mentioned by Bredereck et al. (2016). Another approach is the development of approximation algorithms since nearly single-peaked consistency can also be seen as an optimization problem. A detailed treatment of both fptand approximation-results for Candidate Deletion and Voter Deletion was presented recently for several domain restrictions including single-peakedness (Elkind & Lackner, 2014). The design of ﬁxed-parameter and approximation algorithms for the remaining notions of nearly single-peakedness deserves further attention.

Computational Aspects of Nearly Single-Peaked Electorates

Notion SP-Consistency SP-Evaluation

k-Voter Deletion NP-c (Thm. 6.4) in P (Prop. 6.18) k-Local Candidate Deletion NP-c (Thm. 6.7) in P (Thm. 6.20) k-Additional Axes NP-c (Thm. 6.5) in P (Prop. 6.19) k-Global Swaps NP-c (Thm. 6.9) in P (Thm. 6.21) k-Local Swaps NP-c (Thm. 6.8) in P (Thm. 6.21) k-Candidate Deletion in P (Thm. 6.16) in P (Prop. 6.17) k-Clones in P (Elkind et al., 2012) in P (Elkind et al., 2012) k-Width in P (Cornaz et al., 2013) in P (Cornaz et al., 2013) k-Candidate Partition open in P (Prop. 6.22)

Table 2: Complexity results for diﬀerent notions of nearly single-peakedness.

Another interesting direction for future work is extending our models to manipulative behavior, such as manipulation, control, and bribery. That is, assuming we have a nearly single-peaked electorate according to one of our notions, how computationally expensive is a manipulative action under a certain voting rule? The analysis of manipulation and control in such elections has already been started for some distance measures. In a ﬁrst step, manipulation and control was introduced in the context of nearly single-peaked elections under several voting rules, pinpointing that under some voting rules even the presence of only one maverick can raise the complexity of manipulative actions from P to NP-completeness (Faliszewski et al., 2014). In a second step, dichotomy results for manipulation of k-approval and k-veto under nearly single-peaked elections were achieved identifying the exact borders of tractability (Erd elyi et al., 2015). Still, the impact of nearly single-peakedness on manipulative behavior is far from being fully understood. Finally, there might be further useful and natural distance measures regarding singlepeakedness to be found. In particular, for practical purposes it may be useful to combine distance measures. For example, for a real-world preference data set two axes may be suﬃcient if in addition a small number of swaps is allowed. Computing distances of this sort would be require to deﬁne how to weigh measures against each other, e.g., how does an additional axis compare to 10 swaps? In addition, practical considerations have to be made to decide which distance measures are useful to combine. The aforementioned combination of Global Swaps and Additional Axes may be useful since it allows to correct minor disturbances in the preferences ( noise ) but also take a segregation of voters into account (e.g., there are two issues that are deemed important; every voter gives preference to one and orders the candidates accordingly). The hardness results obtained in this paper do not necessarily transfer to consistency problems for such mixed distance measures. These thoughts do not only apply to the single-peaked restriction but also to other domain restrictions such as the single-crossing or more-dimensional analogues of single-peakedness.

Acknowledgments

The third author, Andreas Pfandler, is aﬃliated both with the University of Siegen and TU Wien. This work was done in part while the second and the third author were visiting

Erd elyi, Lackner & Pfandler

the University of Siegen and while the ﬁrst author was visiting TU Wien, the University of Rochester, and NICTA, Sydney. This work was supported in part by the Austrian Science Fund (FWF) under grant P25518-N23 and Y698, by DFG grants ER 738/1-1 and ER 738/2-1, by COST Action IC1205, and by the European Research Council (ERC) under grant number 639945 (ACCORD). We thank Dominik Peters for pointing out a mistake in an earlier version of this paper. We would also like to thank the anonymous JAIR referees for their very helpful comments and suggestions as well as the reviewers of earlier versions of this paper (Erd elyi, Lackner, & Pfandler, 2012; Erd elyi et al., 2013).

Appendix A. Correctness of the Place Procedure

Lemma 6.13. Let (C, P) be an election. If the iterative application of place yields an axis A, then (C, P) is single-peaked with respect to A. If at some point place returns inconsistent, then (C, P) is not single-peaked.

Proof. Let us assume towards a contradiction that the iterative application of place yields an axis A, but (C, P) is not single-peaked with respect to A. By Lemma 4.2, there exists a vote in P and ci, cj, ck C such that ci > cj > ck on A, ci cj and ck cj. Let us consider the step in the algorithm at which the last element of {ci, cj, ck} is placed. Let A

be the incomplete axis at this point with boundary(A ) = (b 1, b1, b2, b 2). We assume that the election is single-peaked with respect to A , i.e., we consider the earliest step at which place makes a mistake. Before we start with the proof, we prove the following useful claim.

Claim A. Let A be an incomplete axis with boundary(A ) = (b 1, b1, b2, b 2) and is singlepeaked with respect to A . If for some c, c it holds that c c and c > c b1 (i.e., c might be the same candidate as b1), then b 1 b1. Analogously, if c c and b2 c > c, then b 2 b2.

Proof. We prove the ﬁrst statement; the second one is analogous. Note that if c = b 1 then c = b1 and the statement is immediate. So assume that c = b1. Since c > c b 1 > b1, c c and b1 b 1 contradict single-peakedness.

To disprove our assumption that (C, P) is not single-peaked with respect to A, let us distinguish the following cases.

ci has been placed last: When placing ci, it holds that b2 cj > ck on A . Since ck cj, Claim A implies that b 2 b2. However if b 2 b2 and ci cj b2, then by Case 4 place returns inconsistent, a contradiction to our assumption that place returns an axis. The case that ck is placed last is symmetric.

cj has been placed last: It is not possible that b1 cj and b2 cj since cj would have been placed at an earlier point (cf. Case 3a). Thus either cj b1 or cj b2. If cj b1, then by Claim A b 1 b1; if cj b2, then by Claim A b 2 b2. Hence by Case 4 place returns inconsistent.

{ci, cj} have been placed last: Let us ﬁrst prove that b2 cj. If b2 = ck, then b2 = ck cj. If b2 = ck and cj b2, then ck b2 and by Claim A b 2 b2. Thus by Case 4 place would return inconsistent, a contradiction. We have shown that

Computational Aspects of Nearly Single-Peaked Electorates

b2 cj. But if b2 cj and ci cj (by assumption), then by Case 2c cj has to be placed next to b1 and ci next to b2, and hence cj > ci > ck on A. This contradicts our assumption that ci > cj > ck on A. The case that {cj, ck} are placed last is symmetric.

We conclude that (C, P) is single-peaked with respect to A. Now we show that if place returns inconsistent, then (C, P) is not single-peaked. Let A be an incomplete axis, let C be the candidates already placed on A and let X the set of candidates to be placed next, i.e., X = L(P, C \ C ). Assume that place(A , X) returns inconsistent. We consider all cases where place returns inconsistent and show that (C, P) is not single-peaked consistent. Since we have already shown that the iterative application of place yields a single-peaked axis, we can assume that P[C ] is single-peaked with respect to A .

Case 1: It follows from Lemma 4.3 and 4.4 that (C, P) is not single-peaked consistent.

Case 4: Let 1 be the vote under consideration with b 1 1 b1 and x 1 b1. Let us consider the step when b1 was placed; the incomplete axis at this point was of the form > b 1 > > . Since b 1 i b1 and b1 was placed next to b 1, we know that Case 2d occurred. (If Case 3 had been applicable then b 1 i b1 would imply that b1 is placed on the right-hand side and not next to b 1.) Let y be the second candidate that was placed at this step. Since the proﬁle is single-peaked with respect to the incomplete axis A , we know that b 1 1 b1 1 y. Since b1 was placed at this step, there has to be a vote 2 with y 2 b1. Furthermore, it has to hold that either x 2 y or x 2 b1 since x was not placed at this step. Finally, b1 2 b 1 has to hold, because otherwise the proﬁle would not be single-peaked with respect to A . To sum up, we have b 1 1 b1 y and x 1 b1 as well as y 2 b1 2 b 1 and x 2 b1. It is straightforward to verify that this subproﬁle is not single-peaked; indeed, this is one of the forbidden subproﬁles occurring in the single-peakedness characterization by Ballester and Haeringer (2011). Hence by Lemma 4.3 the full proﬁle is not single-peaked.

The procedure may also return inconsistent if a candidate x1 has to be placed both left and right. This occurs if (i) Case 2c occurs once as stated and once with x1 and x2 interchanged, (ii) Case 2d occurs once as stated and once with x1 and x2 interchanged, (iii) both Case 2c and 2d occur, and (iv) both Case 2c and 2d occur with x1 and x2 interchanged. We ﬁrst handle (i); the argument for (ii) is analogous. Let L(P, C ) = {x1, x2}. Assume that there exists a vote 1 with b2 1 x1 and x2 1 x1 (Case 2c). Further there exists a vote 2 with b2 2 x2 and x1 2 x2. Since b2 has been placed at an earlier step, there exists a vote 3 where x1 3 b2 and x2 3 b2. This proves that the proﬁle is not single-peaked via Lemma 4.4.

Let us now consider (iii); the argument for (iv) is analogous. There exists a vote 1 with b2 1 x1 and x2 1 x1 (Case 2c). Since b1 and b2 have been placed before x1 and x2, either b1 or b2 has to be ranked below both x1 and x2. Thus it has to hold that x2 1 x1 1 b1. Also, there exists a vote 2 exists with b1 2 x1 and x2 2 x1 (Case 2d) and by the same argument as before x2 2 x1 2 b2. It is straight-forward to show that this subproﬁle is not single-peaked; indeed, it is equivalent to the one we encountered when we dealt with Case 4. Hence the full proﬁle is not single-peaked.

Erd elyi, Lackner & Pfandler

Let us consider contradictions that can arise in Case 3. Recall from the algorithm description that a contradiction can only arise if x is not the last candidate to be placed. Let y = x be some candidate not yet placed. It has to hold that y x in all votes. Let 1 be a vote with b2 1 x. Since both b1 and b2 have been placed before x, we infer that b2 1 x 1 b1. Further let 2 be a vote with b1 2 x and hence b1 2 x 2 b2. Considering the votes 1, 2 and candidates {x, y, b1, b2}, we encounter the same subproﬁle as in the previous step.

This concludes the correctness proof of the place procedure.

Ballester, M. A., & Haeringer, G. (2011). A characterization of the single-peaked domain. Social Choice and Welfare, 36(2), 305 322.

Bartholdi, J., Tovey, C., & Trick, M. (1989a). The computational diﬃculty of manipulating an election. Social Choice and Welfare, 6(3), 227 241.

Bartholdi, J., Tovey, C., & Trick, M. (1989b). Voting schemes for which it can be diﬃcult to tell who won the election. Social Choice and Welfare, 6(2), 157 165.

Bartholdi, J., Tovey, C., & Trick, M. (1992). How hard is it to control an election?. Mathematical and Computer Modeling, 16(8/9), 27 40.

Bartholdi, J., & Trick, M. (1986). Stable matching with preferences derived from a psychological model. Operations Research Letters, 5(4), 165 169.

Baumeister, D., Erd elyi, G., Hemaspaandra, E., Hemaspaandra, L., & Rothe, J. (2010). Computational aspects of approval voting. In Laslier, J., & Sanver, R. (Eds.), Handbook on Approval Voting, chap. 10, pp. 199 251. Springer.

Betzler, N., Slinko, A., & Uhlmann, J. (2013). On the computation of fully proportional representation. Journal of Artiﬁcial Intelligence Research (JAIR), 47, 475 519.

Biedl, T., Brandenburg, F. J., & Deng, X. (2009). On the complexity of crossings in permutations. Discrete Mathematics, 309(7), 1813 1823.

Black, D. (1948). On the rationale of group decision making. Journal of Political Economy, 56(1), 23 34.

Brandt, F., Conitzer, V., & Endriss, U. (2013). Computational social choice. In Weiss, G. (Ed.), Multiagent Systems. MIT Press.

Brandt, F., Brill, M., Hemaspaandra, E., & Hemaspaandra, L. A. (2015). Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates. Journal of Artiﬁcial Intelligence Research (JAIR), 53, 439 496.

Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. D. (Eds.). (2016). Handbook of Computational Social Choice. Cambridge University Press.

Bredereck, R., Chen, J., & Woeginger, G. (2013). A characterization of the single-crossing domain. Social Choice and Welfare, 41(4), 989 998.

Bredereck, R., Chen, J., & Woeginger, G. (2016). Are there any nicely structured preference proﬁles nearby?. Mathematical Social Sciences, 79, 61 73.

Computational Aspects of Nearly Single-Peaked Electorates

Bruner, M., & Lackner, M. (2015). On the likelihood of single-peaked preferences. Co RR, abs/1505.05852.

Conitzer, V. (2009). Eliciting single-peaked preferences using comparison queries. Journal of Artiﬁcial Intelligence Research (JAIR), 35, 161 191.

Cornaz, D., Galand, L., & Spanjaard, O. (2012). Bounded single-peaked width and proportional representation. In Proceedings of the 20th European Conference on Artiﬁcial Intelligence (ECAI 2012), Vol. 242 of Frontiers in Artiﬁcial Intelligence and Applications, pp. 270 275. IOS Press.

Cornaz, D., Galand, L., & Spanjaard, O. (2013). Kemeny elections with bounded singlepeaked or single-crossing width. In Proceedings of the 23rd International Joint Conference on Artiﬁcial Intelligence (IJCAI 2013), pp. 76 82. AAAI Press.

Demange, G. (1982). Single-peaked orders on a tree. Mathematical Social Sciences, 3(4), 389 396.

Doignon, J.-P., & Falmagne, J.-C. (1994). A polynomial time algorithm for unidimensional unfolding representations. Journal of Algorithms, 16(2), 218 233.

Dwork, C., Kumar, R., Naor, M., & Sivakumar, D. (2001). Rank aggregation methods for the web. In Proceedings of the 10th International World Wide Web Conference (WWW 2001), pp. 613 622. ACM Press.

Elkind, E., Faliszewski, P., & Slinko, A. M. (2012). Clone structures in voters preferences. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC 2012), pp. 496 513. ACM.

Elkind, E., Faliszewski, P., Lackner, M., & Obraztsova, S. (2015). The complexity of recognizing incomplete single-crossing preferences. In Proceedings of the 29th AAAI Conference on Artiﬁcial Intelligence (AAAI 2015), pp. 865 871. AAAI Press.

Elkind, E., & Lackner, M. (2014). On detecting nearly structured preference proﬁles. In Proceedings of the 28th AAAI Conference on Artiﬁcial Intelligence (AAAI 2014), pp. 661 667. AAAI Press.

Elkind, E., & Lackner, M. (2015). Structure in dichotomous preferences. In Proceedings of the 24th International Joint Conference on Artiﬁcial Intelligence (IJCAI 2015), pp. 2019 2025. AAAI Press.

Ephrati, E., & Rosenschein, J. (1997). A heuristic technique for multi-agent planning. Annals of Mathematics and Artiﬁcial Intelligence, 20(1 4), 13 67.

Erd elyi, G., Lackner, M., & Pfandler, A. (2012). The complexity of nearly single-peaked consistency. In Proceedings of the 4th International Workshop on Computational Social Choice (COMSOC 2012), pp. 179 190.

Erd elyi, G., Lackner, M., & Pfandler, A. (2013). Computational aspects of nearly singlepeaked electorates. In Proceedings of the 27th AAAI Conference on Artiﬁcial Intelligence (AAAI 2013), pp. 283 289. AAAI Press.

Erd elyi, G., Lackner, M., & Pfandler, A. (2015). Manipulation of k-approval in nearly singlepeaked electorates. In Proceedings of the 4th International Conference on Algorithmic

Erd elyi, Lackner & Pfandler

Decision Theory (ADT 2015), Vol. 9346 of Lecture Notes in Computer Science, pp. 71 85. Springer.

Escoﬃer, B., Lang, J., & Ozt urk, M. (2008). Single-peaked consistency and its complexity. In Proceedings of the 18th European Conference on Artiﬁcial Intelligence (ECAI 2008), Vol. 178 of Frontiers in Artiﬁcial Intelligence and Applications, pp. 366 370. IOS Press.

Faliszewski, P., Hemaspaandra, E., & Hemaspaandra, L. A. (2009). How hard is bribery in elections?. Journal of Artiﬁcial Intelligence Research (JAIR), 35, 485 532.

Faliszewski, P., Hemaspaandra, E., & Hemaspaandra, L. A. (2010). Using complexity to protect elections. Communications of the ACM, 53(11), 74 82.

Faliszewski, P., Hemaspaandra, E., & Hemaspaandra, L. A. (2014). The complexity of manipulative attacks in nearly single-peaked electorates. Artiﬁcial Intelligence, 207, 69 99.

Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L. A., & Rothe, J. (2011). The shield that never was: Societies with single-peaked preferences are more open to manipulation and control. Information and Computation, 209(2), 89 107.

Faliszewski, P., & Procaccia, A. D. (2010). AI s war on manipulation: Are we winning?. AI Magazine, 31(4), 53 64.

Fitzsimmons, Z., & Hemaspaandra, E. (2016). Modeling single-peakedness for votes with ties. In Proceedings of the 8th European Starting AI Researcher Symposium (STAIRS 2016), Vol. 284 of Frontiers in Artiﬁcial Intelligence and Applications, pp. 63 74. IOS Press.

Frances, M., & Litman, A. (1997). On covering problems of codes. Theory of Computing Systems, 30, 113 119.

Garey, M., & Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.

Ghosh, S., Mundhe, M., Hernandez, K., & Sen, S. (1999). Voting for movies: The anatomy of recommender systems. In Proceedings of the 3rd Annual Conference on Autonomous Agents (AGENTS 1999), pp. 434 435. ACM Press.

Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of Computer Computations, pp. 85 103. Plenum Press.

Kendall, M. G. (1938). A new measure of rank correlation. Biometrika, 30(1/2), pp. 81 93.

Lackner, M. (2014). Incomplete preferences in single-peaked electorates. In Proceedings of the 28th AAAI Conference on Artiﬁcial Intelligence (AAAI 2014), pp. 742 748. AAAI Press.

Menon, V., & Larson, K. (2016). Reinstating combinatorial protections for manipulation and bribery in single-peaked and nearly single-peaked electorates. In Proceedings of the 30th AAAI Conference on Artiﬁcial Intelligence (AAAI 2016), pp. 565 571. AAAI Press.

Computational Aspects of Nearly Single-Peaked Electorates

Peters, D., & Elkind, E. (2016). Preferences single-peaked on nice trees. In Proceedings of the 30th AAAI Conference on Artiﬁcial Intelligence (AAAI 2016), pp. 594 600. AAAI Press.

Peters, D., & Lackner, M. (2017). Preferences single-peaked on a circle. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence (AAAI 2017). AAAI Press. Forthcoming.

Przedmojski, T. (2016). Algorithms and experiments for (nearly) restricted domains in elections. Master s thesis, TU Berlin.

Rothe, J. (Ed.). (2015). Economics and Computation. Springer.

Schensted, C. (1961). Longest increasing and decreasing subsequences. Canadian Journal of Mathetmatics, 13(2), 179 191.

Skowron, P., Yu, L., Faliszewski, P., & Elkind, E. (2015). The complexity of fully proportional representation for single-crossing electorates. Theoretical Computer Science, 569, 43 57.

Sui, X., Francois-Nienaber, A., & Boutilier, C. (2013). Multi-dimensional single-peaked consistency and its approximations. In Proceedings of the 23rd International Joint Conference on Artiﬁcial Intelligence (IJCAI 2013), pp. 375 382. AAAI Press.

Walsh, T. (2007). Uncertainty in preference elicitation and aggregation. In Proceedings of the 22nd AAAI Conference on Artiﬁcial Intelligence (AAAI 2007), pp. 3 8. AAAI Press.

Yang, Y. (2015). Manipulation with bounded single-peaked width: A parameterized study. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015), pp. 77 85. IFAAMAS/ACM.

Yang, Y., & Guo, J. (2014a). The control complexity of r-approval: from the singlepeaked case to the general case. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2014), pp. 621 628. IFAAMAS/ACM.

Yang, Y., & Guo, J. (2014b). Controlling elections with bounded single-peaked width. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2014), pp. 629 636. IFAAMAS/ACM.

Yu, L., Chan, H., & Elkind, E. (2013). Multiwinner elections under preferences that are single-peaked on a tree. In Proceedings of the 23rd International Joint Conference on Artiﬁcial Intelligence (IJCAI 2013), pp. 425 431. AAAI Press.