# on_recognising_nearly_singlecrossing_preferences__7b193e35.pdf

On Recognising Nearly Single-Crossing Preferences

Florian Jaeckle, Dominik Peters, Edith Elkind Department of Computer Science University of Oxford, UK ﬂorian.jaeckle@eng.ox.ac.uk, {dominik.peters, edith.elkind}@cs.ox.ac.uk

If voters preferences are one-dimensional, many hard problems in computational social choice become tractable. A preference proﬁle can be classiﬁed as one-dimensional if it has the singlecrossing property, which requires that the voters can be ordered from left to right so that their preferences are consistent with this order. In practice, preferences may exhibit some onedimensional structure, despite not being single-crossing in the formal sense. Hence, we ask whether one can identify preference proﬁles that are close to being single-crossing. We consider three distance measures, which are based on partitioning voters or candidates or performing a small number of swaps in each vote. We prove that it can be eﬃciently decided if voters can be split into two single-crossing groups. Also, for every ﬁxed k 1 we can decide in polynomial time if a proﬁle can be made single-crossing by performing at most k candidate swaps per vote. In contrast, for each k 3 it is NP-complete to decide whether candidates can be partitioned into k sets so that the restriction of the input proﬁle to each set is single-crossing.

1 Introduction There is a growing body of literature in computational social choice that aims to identify notions of structure in collective preferences, and to provide eﬃcient algorithms for recognising structured preferences; see a recent survey by Elkind, Lackner, and Peters (2017). By discovering structural properties of a preference proﬁle we obtain an explanatory model of voters behavior. Often such models allow us to solve preference aggregation and elicitation problems more eﬃciently. This is particularly important in the context of multiwinner voting: while multiwinner voting rules are useful in a variety of applications ranging from group recommendation systems and design of marketing campaigns to parliamentary elections, and have attracted intense interest in recent years (see Faliszewski et al. 2017), for many appealing multiwinner rules the winner determination problem is computationally hard (Lu and Boutilier 2011; Aziz et al. 2015; Skowron, Faliszewski, and Lang 2016). Thus, it is important to identify natural subdomains where winning sets can be computed eﬃciently. The approach based on structured preferences has been very successful in this setting, with a number

Copyright 2018, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

distance metric single-peaked single-crossing

voter deletion NP-complete a,b in P b

alternative deletion in P a NP-complete b voter partition NP-complete a in P for k = 2 alternative partition open NP-complete local swaps NP-complete a in XP wrt k

Table 1: Overview of the complexity of deciding whether a proﬁle is close to being structured. Bold results are new. a proved by Erdélyi, Lackner, and Pfandler (2017). b proved by Bredereck, Chen, and Woeginger (2016).

of polynomial-time algorithms proposed for several rules and various notions of structure (Betzler, Slinko, and Uhlmann 2013; Skowron et al. 2015; Yu, Chan, and Elkind 2013; Clearwater, Puppe, and Slinko 2015; Peters and Elkind 2016; Peters and Lackner 2017). The two best-known types of structured preferences are single-peaked preferences (Black 1948; Arrow 1951) and single-crossing preferences (Inada 1964; Mirrlees 1971; Roberts 1977). Informally, the former notion is based on ordering the candidates along a one-dimensional axis, while the latter notion is based on ordering the voters from left to right; in both cases, the voters preferences are required to be consistent with this ordering. In particular, single-crossing preferences arise when voters opinions depend only on a single one-dimensional type or parameter. For example, in political elections, this parameter may be the position of the voter on the left-to-right ideological spectrum (if candidates, too, can be positioned on this spectrum, the voters preferences will be single-peaked, in addition to being singlecrossing, but single-crossing preferences may arise even if this is not the case). Similarly, when voters choose among several policies, the policy space may be complicated and not obviously one-dimensional, but the voter s preferences could still be explainable by a single parameter (such as their position on how to deal with a trade-oﬀ). The economics literature considers many such scenarios, including taxation, coalition formation, public goods, and education markets (see Saporiti 2009). Proﬁles that are single-peaked or single-crossing have many attractive properties: for instance, for both domains it

The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18)

holds that the majority preferences are transitive, and there is a strategyproof preference aggregation rule. Also, the membership in either of these domains can be eﬃciently tested, and both domains admit polynomial-time algorithms for problems that are hard for general preferences (see Elkind, Lackner, and Peters 2017). However, these notions of structure are not robust: even the addition of a single misbehaving voter to a structured proﬁle can make it non-structured. Further, they are restrictive in that only an exponentially small fraction of all preference proﬁles belongs to one of these domains (Lackner and Lackner 2017). Indeed, most preference proﬁles elicited in the real world are unlikely to belong to either of these domains: none of the proﬁles in the Pref Lib library (Mattei and Walsh 2013) is single-peaked or single-crossing. Nevertheless, voters preferences are often driven by considerations that are essentially single-dimensional (consider, e.g., voting over tax rates), and in such cases we expect the preferences to be nearly structured. For instance, it may be the case that a proﬁle can be made single-peaked or single-crossing by swapping a few pairs of adjacent candidates in each vote, ignoring a small number of irrational voters or unconventional candidates, or splitting the voters in a few groups so that within each group the preferences have the desired structure. Such nearly structured preferences may inherit some of the attractive computational properties of the original domain. Nearly structured preferences have been explored in a number of recent papers (Faliszewski, Hemaspaandra, and Hemaspaandra 2014; Cornaz, Galand, and Spanjaard 2012; 2013; Bredereck, Chen, and Woeginger 2016; Erdélyi, Lackner, and Pfandler 2017), which introduced several distance measures capturing how close a given proﬁle is to being structured, studied the complexity of computing such distances, and proposed algorithms for social choice problems that are hard for general preferences for instances from nearly structured domains. In particular, these papers argue that, for nearly structured domains to be algorithmically useful, they need to admit eﬃcient recognition algorithms. To address this challenge, Erdélyi, Lackner, and Pfandler (2017) put forward an extensive list of distance measures, and show that, for almost all distances on their list, it is NP-hard to compute how far a given proﬁle is from being single-peaked. In contrast, for the singlecrossing domain the picture is far from complete: Bredereck, Chen, and Woeginger (2016) provide a hardness result for candidate deletion and a polynomial-time algorithm for voter deletion, and Cornaz, Galand, and Spanjaard (2012; 2013) provide positive algorithmic results for a measure they call the single-peaked/single-crossing width, but for many distance measures introduced by Erdélyi, Lackner, and Pfandler (2017) the complexity of deciding if a given proﬁle is close to being single-crossing remains open.

Our contribution. We study proﬁles that are almost singlecrossing in three diﬀerent senses:

Voter partition. We ask whether the input proﬁle can be partitioned into k single-crossing subproﬁles, i.e., whether the electorate can be subdivided into few sub-communities each of which is well-structured. We solve this problem

for k = 2 by reducing it to 2SAT.

Local swaps. We ask whether the input proﬁle can be made single-crossing by making at most k swaps of adjacent alternatives in the preferences of each voter, i.e., whether it can be the case that the input proﬁle fails to be singlecrossing simply because voters made small errors when reporting their preferences. We show that this problem is in XP with respect to k, i.e., for each ﬁxed k we can answer this question in polynomial time.

Alternative partition. We ask whether the set of alternatives can be partitioned into k subsets A = A1 Ak so that the restriction of the input proﬁle to each subset is single-crossing. We show that this problem is NP-hard for every ﬁxed k 3, by providing a reduction from the k-colouring problem.

Our results are summarised in Table 1.

2 Preliminaries Let A be a ﬁnite set of m alternatives, or candidates, and let N = {1, . . ., n} be a set of n voters; each voter i is associated with a strict total order vi over A, which we call vi s preference order. If alternative a is ranked above alternative b in a strict total order v, we write a v b. The collection P = (v1, . . ., vn) is called a preference proﬁle. Given a subset A of A, we write P[A ] to denote a proﬁle (u1, . . ., un) of strict linear orders over A such that for each i [n] and all a, b A we have a ui b if and only if a vi b; we refer to P[A ] as the restriction of P to A . We write Nab = {i N : a vi b} to denote the set of voters who prefer a to b.

Deﬁnition. Let L be a linear order over the set N of voters. We say that P is single-crossing with respect to L if for all pairs a, b A of alternatives, the sets Nab and Nba are intervals of L.

Thus, as we move along L from left to right, we observe that the voters preferences over a and b cross at most once. We say that a proﬁle P is single-crossing if there exists some linear order L over N such that P is single-crossing with respect to L. We also say that P = (v1, . . ., vn) is single-crossing in the given order if P is single-crossing with respect to the order L given by 1 < 2 < < n. Figure 1 shows an example of a single-crossing proﬁle.

v1 v2 v3 v4 v5

a b b d d b a d b c c d a c b d c c a a

Figure 1: A preference proﬁle that is single-crossing with respect to the voter ordering 1 < 2 < 3 < 4 < 5. The trajectories of any two alternatives cross at most once.

We now introduce an alternative way of looking at singlecrossing preferences, and present a method to decide whether

a given proﬁle is single-crossing. Given two linear orders u and v, we deﬁne the conﬂict set Δ(u, v) to be the set of pairs of alternatives on which u and v disagree:

Δ(u, v) = {{a, b} A : a u b and b v a}.

The Kendall-tau distance between u and v is then deﬁned as d(u, v) = |Δ(u, v)|. Consider a proﬁle P = (v1, . . ., vn) that is single-crossing in the given order. Then, as i grows from 1 to n, the number of conﬂicts between v1 and vi increases with each crossing. Thus, we have

= Δ(v1, v1) Δ(v1, v2) Δ(v1, vn). (1)

Clearly, the converse is also true: If (1) holds, then P is single-crossing in the given order. For example, in Figure 1, we have

Δ(v1, v2) = {ab, cd}, Δ(v1, v3) = {ab, cd, ad}, Δ(v1, v4) = {ab, cd, ad, bd, ac}, Δ(v1, v5) = {ab, cd, ad, bd, ac, bc},

and these sets form a chain with respect to . Given a proﬁle P and a voter i, we say that P is singlecrossing with ﬁrst voter i if P is single-crossing with respect to an ordering L in which i is the ﬁrst (leftmost) voter. Then (1) implies the following characterisation. Proposition 1. A proﬁle P = (v1, . . ., vn) is single-crossing with ﬁrst voter i if and only if for all pairs of voters j, k either Δ(vi, vj) Δ(vi, vk) or Δ(vi, vk) Δ(vi, vj).

The condition formulated in Proposition 1 is easy to check. Thus, ﬁxing the ﬁrst voter substantially simpliﬁes the task of ﬁnding an ordering L such that P is single-crossing with respect to L. In particular, using this characterisation, we can decide in polynomial time whether a given proﬁle P is single-crossing. Proposition 2. We can decide whether a given proﬁle is single-crossing in time O(n3m2).

Proof. Guess the ﬁrst voter i, compute the sets Δ(vi, vj), and check if they form a chain with respect to .

This basic algorithm can be optimised in various ways, leading to faster runtimes. For instance, one can work with the Kendall-tau distances d(vi, vj) rather than the conﬂict sets (see, e.g., Doignon and Falmagne 1994; Elkind, Faliszewski, and Slinko 2012). Our algorithms for detecting nearly singlecrossing proﬁles, however, build on this simple template based on conﬂict sets. Another corollary to Proposition 1 is that, in order for a proﬁle P to be single-crossing with ﬁrst voter i, the distances d(vi, vj), vj P, must be pairwise distinct.

3 Voter Partition Arguably, if a preference proﬁle is single-crossing, then there is a form of consensus among the voters: while individuals may have very diﬀerent preferences, there is a common understanding of what the underlying issue space is, and how

diﬀerent positions in this issue space translate into preference rankings (List et al. 2012 make a similar argument in the context of single-peaked preferences). However, it may also happen that, while there is no common agreement over the issue space, voters can be split into a few disjoint groups so that each group shares the same perspective on issues and, consequently, each group has single-crossing preferences. This is the underlying idea of the voter partition metric, which will be considered in this section. Formally, we ask if we can partition N into k subsets, N = N1 N2 Nk, so that for each j [k] the subproﬁle Pj = (vi)i N j is single-crossing. Certainly, the answer is yes if k is large enough: e.g., every two-voter proﬁle is single-crossing, so for k |N|/2 the answer is positive. But given our original motivation, we are particularly interested in solving this problem for small values of k. An example of a proﬁle where the answer is yes for k = 2 is shown in Figure 2. We note that voter partition is related to voter deletion, where we look for a maximum-cardinality subset N of N such that the proﬁle P = (vi)i N is single-crossing; in contrast, in the voter partition problem we want both P and P \ P to be single-crossing.

v1 v2 v3 v4 v5 v6

a a d b d a b c c c a d c d b d b c d b a a c b

Figure 2: A preference proﬁle that can be partitioned into two single crossing proﬁles, {v1, v2, v3} and {v4, v5, v6}.

The main result of this section is a polynomial-time algorithm for the voter partition problem with k = 2. Our algorithm proceeds by creating and solving several instances of 2SAT, and uses the characterisation of single-crossing preferences with a ﬁxed ﬁrst voter from Proposition 1. Theorem 3. Given a proﬁle P with n voters and m alternatives, we can decide in time O(n4m2) whether the voter set N can be partitioned as N = N1 N2 so that both proﬁles P1 = (vi)i N1 and P2 = (vi)i N2 are single-crossing.

Proof. As a ﬁrst step, we guess two voters i, ℓ N, i ℓ, and let s1 = vi, s2 = vℓ. We then check whether there is a partition P = P1 P2 such that for j = 1, 2 it holds that sj N j and Pj is single-crossing with ﬁrst vote sj. We perform this check by a reduction to 2SAT, the problem of deciding if a formula of propositional logic in 2-CNF is satisﬁable. 2SAT is known to be solvable in linear time (see, e.g., Papadimitriou 1993). To construct this formula, we introduce one variable zv for each vote v P. Intuitively, an assignment α to these variables corresponds to a partition of P into subproﬁles

P1 = {v : α(zv) = true} and P2 = {v : α(zv) = false}. (2)

We now introduce clauses that force each of the proﬁles Pj, j = 1, 2, to be single-crossing with ﬁrst vote sj. Given two

sets A and B, we write A B if A and B are incomparable under , i.e., A B and B A. For each j = 1, 2 and every pair of votes x, y Pj the sets Δ(sj, x) and Δ(sj, y) must be comparable under , i.e., Δ(sj, x) Δ(sj, y). That is, if Δ(sj, x) Δ(sj, y) for some j = 1, 2, then votes x and y cannot both belong to Pj. Hence our condition is captured by the following 2-CNF formula:

x,y P Δ(s1,x) Δ(s1,y)

x,y N Δ(s2,x) Δ(s2,y)

(zx zy). (3)

If formula (3) is not satisﬁable, there is no partition of P into two single-crossing proﬁles with s1 and s2 as ﬁrst votes. Conversely, a satisfying assignment α can be converted into a partition via (2). Formula (3) has n variables and O(n2) clauses, and can be constructed in O(n2m2) time. Since 2SAT can be solved in linear time, we can decide whether (3) can be satisﬁed in time O(n2). As we consider up to n 2 diﬀerent formulas, the overall runtime of this algorithm is O(n4m2).

The proof of Theorem 3 does not extend to k = 3, since the reduction to SAT would yield clauses with three literals. We leave the complexity of voter partition with k 3 open. This problem seems structurally similar to the problem of 3colouring a graph formed by a union of three incomparability graphs. However, existing results on incomparability graphs (see, e.g., Bosek, Krawczyk, and Matecki 2013) do not seem to be directly applicable to our problem. We note that for the case of single-peaked preferences, voter partition is known to be NP-hard for each k 3, but the case k = 2 is open (Erdélyi, Lackner, and Pfandler 2017).

4 Local Swaps We now consider the local swaps distance, where we have a budget of k swaps per vote: for each voter, we may (successively) perform k swaps of two candidates that are adjacent in the vote, with the aim of making the proﬁle single-crossing. A swap of adjacent candidates is, in some sense, a minimal change of a preference order, so this distance corresponds to ﬁne-grained perturbations of the input proﬁle. Figure 3 shows an example of a proﬁle that can be made single-crossing by performing a single swap per voter. Note that the original version of the proﬁle on the left looks rather chaotic, whereas the perturbed version on the right is visibly structured. If we are in a setting where we expect the true proﬁle to be single-crossing, but we observe the proﬁle in the left part of Figure 3, we may well come to the conclusion that there have been errors in the process of eliciting the voters preferences, and that the perturbed proﬁle is closer to the truth. As in the previous section, our aim is to decide whether we can make a proﬁle single-crossing by using at most k swaps per vote. Note that even the case k = 1 is not trivial: a naive brute-force search requires considering (m 1)n possibilities. However, we show that for k = 1 this problem can be solved in polynomial time. In fact, we obtain a stronger result: our problem can be solved in polynomial time for every ﬁxed k, though the exponent in the runtime may depend on k. This

v1 v2 v3 v4 v5 v6

a d a a b f

b a d d d c c b b f a d

d c e b f b

f e c c c a

e f f e e e

v1 v2 v3 v4 v5 v6

a a a a d f

b d d d b d c b b b a c

d c c f f b

e e e c c a

f f f e e e

Figure 3: A proﬁle that becomes single-crossing after we swap a single pair of adjacent candidates in each vote.

places our problem in the parameterised complexity class XP with respect to k. Our algorithm proceeds by splitting the proﬁle into several pieces. Then for each piece we enumerate all ways in which that piece can be made single-crossing by using at most k swaps per voter. Finally, we use dynamic programming to ﬁnd a way to combine the results for individual pieces.

Theorem 4. Given a proﬁle P with n voters and m alternatives, we can decide in time O((nm)8k3+2k2poly(n, m)) whether P can be made single-crossing by making at most k swaps in the preferences of each voter.

Proof. Note that if P contains multiple copies of some preference order, we can remove all but one copy without changing the answer to our question. Thus, in what follows we can treat P as a set of (distinct) preference orders. Recall that the Kendall-tau distance d(vi, vj) between two preference orders is the number of pairs on which they disagree. Given a set P = {v1, . . ., vq} of preference orders, we say that a set P = {u1, . . ., ur} is a k-variant of P if for each i [q] there is a j [r] such that d(vi, uj) k and for each j [r] there is an i [q] such that d(vi, uj) k; note that we may have q r. Thus, a proﬁle is obtainable from P by performing k local swaps if and only if it is a k-variant. We can now formalise our question as follows: is there a k-variant P of P that is single-crossing? Throughout our analysis of the problem, we will ﬁx the number k of allowed swaps per vote. Thus, polynomial size and polynomial time refer to values that are polynomial for constant k, that is, to values bounded by (nm)f (k) for some function f . Let P be the input proﬁle, interpreted as a set of linear orders. The ﬁrst step in our algorithm is to guess which voter will appear ﬁrst in the order of voters witnessing that the target proﬁle P is single-crossing. We implement this guessing by iterating through all preference orders v P, and iterating through all possibilities of applying at most k swaps to v, yielding s. There are O(nmk) possibilities for this. Having guessed the starting voter, we have to check whether P is within k local swaps from being single-crossing with ﬁrst voter s. We now partition P into blocks based on the distance to s.

For each r = 1, . . ., m 2 , let

Pr := {vi P : d(s, vi) = r}

be the set of preference orders at distance exactly r from s. At ﬁrst we will handle each Pr separately, by enumerating all promising ways of applying k swaps to the orders in Pr. To this end, let Bk(Pr) denote the set of all k-variants P r of Pr such that P r {s} is single-crossing with ﬁrst vote s.

Lemma 5. The set Bk(Pr) is of polynomial size and can be enumerated in polynomial time.

Proof. Consider a set P r Bk(Pr). We have d(s, v) [r k, r + k] for each v P r. For P r to be single-crossing with ﬁrst vote s, the votes in P r must be at pairwise diﬀerent distances from s. Thus, for each d [r k, r + k], there is at most one preference order v in P r with d(s, v) = d. Hence |P r | 2k + 1. It follows that P r is a k-variant of some subset P r Pr of size at most 2k + 1. Thus, to enumerate Bk(Pr), we can enumerate all O(|Pr |2k+1) subsets P r Pr of size at most 2k + 1, then, for each P r, enumerate all O((mk)2k+1) k-variants of P r, and ﬁnally cross out all sets that are not k-variants of Pr or are not single-crossing with ﬁrst voter s.

The procedure described in Lemma 5 is rather ineﬃcient even for relatively small k. For the case k = 1, we can show that Bk(Pr) can be enumerated in time linear in m. We omit the proof due to space constraints. Having enumerated all potential k-variants for each Pr separately, we now need a way to decide whether there is a way to combine them into a single-crossing proﬁle. Note that in this proﬁle votes from diﬀerent sets P r may be interleaved, which makes our problem more diﬃcult. Nevertheless, we will now argue that it can be reduced to the problem of ﬁnding a path of a certain length in the directed acyclic graph that we will now construct. Let Pr1, . . ., Prq be a list of all non-empty sets Pr, where r1 < < rq. For each i = 1, . . ., q 4k + 1, let

Cri := {(P ri, . . ., P ri+4k 1) Bk(Pri ) Bk(Pri+4k 1) :

{s} P ri P ri+4k 1 is single-crossing with ﬁrst vote s}

Thus, Cri is the set of all combinations of k-variants from 4k successive non-empty sets Pr that together are single-crossing with ﬁrst vote s. We now construct a directed graph D with vertex set V = Cr1 Crq 4k+1 and add an arc

(P ri, . . ., P ri+4k 1) (P ri+1, . . ., P ri+4k )

whenever these two vectors are compatible, that is, whenever P ri+t = P ri+t for all t [4k 1]. Note that there are only arcs between vertices from two successive sets Cri. To ﬁnish the proof, we need the following lemma.

Lemma 6. Proﬁle P admits a k-variant that is single-crossing with ﬁrst vote s if and only if D contains a path of length q 4k + 1.

Proof. Suppose P is such a k-variant. Then, for each ri, there is some P ri Bk(Pri) such that P ri P by the correctness of the algorithm in Lemma 5. Then D contains the path

(P r1, . . ., P r4k ) (P rq 4k+1, . . ., P rq).

Conversely, suppose D contains a path of length q 4k + 1. This induces a choice of P ri Bk(Pri) for each i [q]. Let P = {s} P r1 P rq. We claim that P is single-crossing with ﬁrst vote s. We check this using Proposition 1. Suppose, aiming for a contradiction, that there exist preference orders x Pri and y Prj with i j such that Δ(s, x) and Δ(s, y) are incomparable under . Choose x and y so as to minimize j i. Clearly j i 4k by construction of Cri. Take any preference order z P ri+2k . Then by minimality of j i, the sets Δ(s, x) and Δ(s, z) must be comparable, and the sets Δ(s, z) and Δ(s, y) must be comparable (under ). Since we are only allowed k swaps per vote, we have

d(s, x) ri + k = (ri + 2k) k d(s, z), and d(s, z) ri + 3k rj k d(s, y).

Hence, we must have Δ(s, x) Δ(s, z) and Δ(s, z) Δ(s, y). Thus Δ(s, x) Δ(s, y), which is a contradiction.

Now, the digraph D is acyclic, since it admits a topological ordering; also, for every ﬁxed k it has polynomially many vertices. Thus, we can decide in polynomial time whether D contains a directed path with q 4k + 1 vertices. By Lemma 6, such paths correspond to k-variants of P that are single-crossing with ﬁrst vote s. Thus, the proof is complete.

5 Alternative Partition The alternative partition metric is similar in spirit to the voter partition metric: given a proﬁle P over a set of alternatives A, we ask whether we can partition A into k subsets A = A1 Ak so that for each j [k] the restriction of P to Aj is single-crossing. Importantly, each restricted proﬁle P[Aj] may be single-crossing with respect to a diﬀerent voter ordering. We will now argue that this problem is NP-complete.

v1 v2 v3 v4

a a b b b b a a c d c d d c d c

In our hardness reduction, it will be useful to have some small proﬁles that are not single-crossing. For example, consider the proﬁle on the right. Suppose this proﬁle was singlecrossing with respect to some order <L. By considering the pair {a, b}, we conclude that {1, 2} <L {3, 4} or {3, 4} <L {1, 2}. Similarly, by considering the pair {c, d}, we conclude that either {1, 3} <L {2, 4} or {2, 4} <L {1, 3}. The conditions imposed by {a, b} are incompatible with those imposed by {c, d}, so this proﬁle is not single-crossing. We can use this proﬁle as a gadget in our reduction, to ensure that alternatives a, b, c, d cannot all be contained in the same part of our partition. Proﬁles of this type are known as δ-conﬁgurations, which together with γ-conﬁgurations are used by Bredereck, Chen, and Woeginger (2013) to characterise the domain of singlecrossing proﬁles in terms of forbidden subproﬁles. Given a

proﬁle P, we will say that a subset A A of alternatives induces a δ-conﬁguration if there are four voters i1, i2, i3, i4 and we can write A = {a, b, c, d} (where a, b, c, d are not necessarily distinct) so that a i1 b and c i1 d, a i2 b and d i2 c, b i3 a and c i3 d, b i4 a and d i4 c. As argued above, when A induces a δ-conﬁguration, and A A is such that P[A ] is single-crossing, it holds that A A , i.e., the alternatives in A cannot all be in the same part of the partition. Our reduction is from the k-colouring problem. An instance of this problem is an undirected graph G = (V, E) and a parameter k; it is a yes -instance if it is possible to partition V into k independent sets, and a no -instance otherwise. The k-colouring problem is NP-complete for each k 3 (Garey and Johnson 1979). The high-level idea of our reduction is that the vertices of G become alternatives, and we use voters and further dummy alternatives to build δ-conﬁgurations that force alternatives corresponding to adjacent vertices to lie in diﬀerent partition parts. The implementation details are rather involved. Our reduction is inspired by the proof that it is NP-hard to decide if a given proﬁle can be made single-crossing by removing k alternatives (Bredereck, Chen, and Woeginger 2016). Theorem 7. For every k 3, it is NP-complete to decide whether given a proﬁle P we can partition the alternative set A into k sets A = A1 Ak so that for each j [k] the proﬁle P[Aj] is single-crossing.

Proof. This problem is in NP, since one can check in polynomial time whether k sets form a partition and whether a given proﬁle is single-crossing. To show NP-hardness, we reduce from the k-colouring problem. Given an instance G of the k-colouring problem, where G has vertex set F = { f1, . . ., fn} and edge set E = {e1, . . ., em}, we will construct a proﬁle P over a set of alternatives A in such a way that A can be partitioned into k sets A = A1 Ak with each proﬁle P[Aj] being single-crossing if and only if G is k-colourable. For every vertex fi F we introduce a candidate qi. Let Q := {qi : i [n]}. Deﬁne the canonical order of Q to be Q := q1 qn. For every edge ei E we introduce 4k candidates a1 i, . . ., a2k i , x1 i , . . ., x2k i , and deﬁne

Bi := {a1 i, . . ., a2k i }, Xi := {x1 i , . . ., x2k i }, with the canonical orders of Bi and Xi being deﬁned as Bi := a1 i a2k i , Xi := x1 i x2k i . Furthermore, for j [2k] we let ℓ= 2k j and deﬁne the following linear orders over the sets Bi and Xi: Bi j := a1 i a2 i aℓ i a2k i a2k 1 i aℓ+1 i ,

Xi j := x1 i x2 i xℓ i x2k i x2k 1 i xℓ+1 i ,

Bi j := aj i aj 1 i a1 i aj+1 i aj+2 i a2k i ,

Xi j := x j i x j 1 i x1 i x j+1 i x j+2 i x2k i .

Deﬁne the candidate set A to be

A := Q B1 X1 Bm Xm.

Now for every j [2k] we construct two votes vj, v j that rank the candidates as follows:

vj : Q B1 j X1 j Bm j Xm j,

v j : Q B1 j X1 j Bm j Xm j.

For each i [m] it holds that any three distinct candidates ar i , as i, at i in Bi such that r < s < t, together with votes v1, v2k r, v s, v2k, induce a δ-conﬁguration, since

v1 : ar i as i at i,

v2k r : ar i at i as i,

v s : as i ar i at i,

v2k : at i as i ar i .

Similarly, any three distinct candidates xr i , xs i , xt i in Xi with r < s < t, together with votes v1, v2k r, v s, v2k, induce a δ-conﬁguration. Now, for every edge ei = { fj, fk} with j < k we construct four votes w4i 3, w4i 2, w4i 1, w4i that rank the candidates as follows:

B1 X1 Bi 1 Xi 1 q1 qj 1 {qj} Bi qj+1 qk 1 {qk} Xi qk+1 qn Bi+1 Xi+1 Bm Xm .

We still need to deﬁne the relative ranking of qj and Bi, as well as of qk and Xi:

w4i 3 ranks qj Bi and qk Xi , w4i 2 ranks qj Bi and Xi qk, w4i 1 ranks Bi qj and qk Xi , w4i ranks Bi qj and Xi qk.

Note that for all candidates s Bi and t Xi it holds that votes w4i 3, . . ., w4i and candidates qj, qk, s, t induce a δ-conﬁguration. Deﬁne the proﬁle P to be

{vi, v i : i [2k]} {w4i 3, w4i 2, w4i 1, w4i : i [m]}.

The proﬁle P can be constructed in polynomial time. We will now show that G is k-colourable if and only if there exists a partition A1 Ak of A such that P[Ai] is single-crossing for each i [k]. = Suppose A1, . . ., Ak is a partition of A such that P[A1], . . ., P[Ak] are all single-crossing. For each i [k], deﬁne Fi := { fj F : qj Ai}.

We show that F1, . . ., Fk is a valid k-colouring for G. Clearly, F1, . . ., Fk partition F; hence it suﬃces to show that each Fi is an independent set. Suppose, aiming for a contradiction, that one of the sets Fi, say F1, is not an independent set. Then there exists an edge eℓ= ( fi, fj) E

such that fi, fj F1. By deﬁnition of F1 both qi and qj are in A1. Recall that any three distinct candidates ar ℓ, as ℓ, at ℓin Bℓ, where r < s < t, together with votes v1, v2k r, v s, v2k induce a δ-conﬁguration. Since P[A1], . . ., P[Ak] are all singlecrossing, it follows that |Bℓ At| 2 for all t [k]. Because |Bℓ| = 2k, it follows that |Bℓ At| = 2 for all t [k]; similarly, |Xℓ At| = 2 for all t [k]. Now let a Bℓ A1 and x Xℓ A1. Then votes w4ℓ 3, . . ., w4ℓand candidates a, x, qi, qj induce a δ-conﬁguration, which contradicts the assumption that P[A1] is single-crossing. Thus F1, and similarly all other sets Fi, are independent sets. Hence F1, . . ., Fk is a valid colouring of G. = Now suppose that G is k-colourable. Let F1, . . ., Fk be a k-colouring of G. We construct a partition of A = A1 Ak, where for each i [k] we take

Ai := {qj A : fj Fi}

{a2i 1 j , a2i j , x2i 1 j , x2i j A : j [m]}.

The sets A1, . . ., Ak form a partition of A, and thus we only need to show that P[Ai] is single-crossing for each i [k]. To do so, we deﬁne an order of votes in each proﬁle P[Ai], i [k]. We set

Li := v2(k i+1) > > v2k > v 2i > > v 2k > v1 > > v2k 2i+1 > v 1 > > v 2i 1 > {w1, w2, w3, w4} > > {w4m 3, w4m 2, w4m 1, w4m}.

It remains to deﬁne Li on the sets {w4j 3, w4j 2, w4j 1, w4j} for j [m]. Suppose that ej = ( fk, fℓ). Then if fℓ Fi, then

Li : w4j 3 > w4j 2 > w4j 1 > w4j,

and if fℓ Fi, then

Li : w4j 3 > w4j 1 > w4j 2 > w4j.

Note that for all j [m] in all votes up to v 2k in the linear order Li candidate a2i j is ranked above a2i 1 j and candidate x2i j is ranked above x2i 1 j , whereas in all votes from v1 onwards candidate a2i 1 j is ranked above a2i j and candidate x2i 1 j is ranked above x2i j for all j [m]. It is straightforward to check that P[Ai] is single-crossing with respect to Li by arguing that for all distinct candidates s, t Ai the set of votes where s is ranked above t is connected in Li, and so is the set of votes where t is ranked above s. We omit this argument due to space constraints; details can be found in the full version of the paper.

6 Conclusions and Future Work This work contributes to our understanding of nearly structured preferences. For two natural notions of distance we have obtained eﬃcient algorithms for identifying preferences that are very nearly single-crossing. We consider our algorithmic result for the local swaps distance to be particularly appealing, because it concerns an operation that only performs small perturbations to voters reported preferences. Indeed, we believe that when preferences are a few local swaps away from

being structured, we can sometimes be justiﬁed in taking the structured version of the proﬁle to be the starting point of the analysis. It is instructive to contrast the local swap distance and the voter deletion distance: while for single-crossing preferences the latter admits an eﬃcient algorithm even when k is part of the input (Bredereck, Chen, and Woeginger 2016), the voter deletion distance forces us to completely ignore some voters preferences; in this sense, the local swaps distance is more egalitarian. The running time of our algorithm for local swaps, whose exponent depends on k, will only be acceptable for small k (and moderate values of n and m). However, this is the practically relevant case: we are presumably not interested in proﬁles that can be made structured by very large perturbations, since then the structure does not explain much anyway. It would be interesting to obtain other positive results of this type, i.e., to design algorithms that can eﬃciently detect if a given preference proﬁle is very close to being structured. In contrast to our tractability results for voter partition and local swaps, we obtain a hardness result for alternative partition. In a sense, this result is not surprising, as for the related measures of voter and alternative deletion, a similar phenomenon is known: the smallest number of voters that need to be deleted to make a proﬁle single-crossing can be computed in polynomial time, whereas for alternative deletion this problem is NP-hard (Bredereck, Chen, and Woeginger 2016). Intuitively, this is because the deﬁnition of singlecrossing preferences focuses on ordering the voters, and therefore computational problems that deal with rearranging the voters are easier than those that deal with rearranging the alternatives. Indeed, for single-peaked preferences, which are deﬁned in terms of an ordering of the alternatives, the alternative deletion problem is easy, but the voter deletion problem is NP-hard (Erdélyi, Lackner, and Pfandler 2017). Our work leaves a number of interesting open questions. In particular, for the local swaps distance, it would be desirable to improve the running time of our algorithm, and to investigate the existence of an FPT algorithm. For the voter partition algorithm, the complexity of partitioning into k > 2 sets remains open. It is also natural to ask if there are analogues of our results for the single-peaked domain. We note that existing NP-completeness results for this domain (Erdélyi, Lackner, and Pfandler 2017), do not rule out tractability of voter partition for k = 2, or an XP result for local swaps. Another research direction is to investigate the complexity of deciding whether a given proﬁle is close to being structured, for more general notions of structure, such as being singlepeaked or single-crossing on graphs other than the line (such as, e.g., trees or cycles). To the best of our knowledge, this topic has not yet been explored. Finally, to make our positive results more practically applicable, it would be desirable to extend tractability results for winner determination of various preference aggregation rules (particularly multiwinner voting rules) from the perfectly structured proﬁles to those that are almost structured. Such results have been obtained for single-peaked or singlecrossing width (Cornaz, Galand, and Spanjaard 2012; 2013; Skowron et al. 2015), and, very recently, for a few other distance measures (Misra, Sonar, and Vaidyanathan 2017).

Results of this type also appear in the literature on manipulation and control (see, e.g., Faliszewski, Hemaspaandra, and Hemaspaandra 2014; Yang and Guo 2015; 2017). Extending this line of research to a wider range of domains and distance measures is a promising direction for future work.

Acknowledgements This work was supported by the European Research Council (ERC) under grant number 639945 (ACCORD). Florian Jaeckle and Dominik Peters are supported by EPSRC.

Arrow, K. J. 1951. Social Choice and Individual Values. John Wiley and Sons. Aziz, H.; Gaspers, S.; Gudmundsson, J.; Mackenzie, S.; Mattei, N.; and Walsh, T. 2015. Computational aspects of multi-winner approval voting. In AAMAS 15, 107 115. Betzler, N.; Slinko, A.; and Uhlmann, J. 2013. On the computation of fully proportional representation. Journal of Artiﬁcial Intelligence Research 47(1):475 519. Black, D. 1948. On the rationale of group decision-making. Journal of Political Economy 56(1):23 34. Bosek, B.; Krawczyk, T.; and Matecki, G. 2013. First-ﬁt coloring of incomparability graphs. SIAM Journal on Discrete Mathematics 27(1):126 140. Bredereck, R.; Chen, J.; and Woeginger, G. J. 2013. A characterization of the single-crossing domain. Social Choice and Welfare 41(4):989 998. Bredereck, R.; Chen, J.; and Woeginger, G. J. 2016. Are there any nicely structured preference proﬁles nearby? Mathematical Social Sciences 79:61 73. Clearwater, A.; Puppe, C.; and Slinko, A. 2015. Generalizing the single-crossing property on lines and trees to intermediate preferences on median graphs. In IJCAI 15, 32 38. Cornaz, D.; Galand, L.; and Spanjaard, O. 2012. Bounded single-peaked width and proportional representation. In ECAI 12, 270 275. Cornaz, D.; Galand, L.; and Spanjaard, O. 2013. Kemeny elections with bounded single-peaked or single-crossing width. In IJCAI 13, 76 82. Doignon, J.-P., and Falmagne, J.-C. 1994. A polynomial time algorithm for unidimensional unfolding representations. Journal of Algorithms 16(2):218 233. Elkind, E.; Faliszewski, P.; and Slinko, A. 2012. Clone structures in voters preferences. In ACM EC 12, 496 513. Elkind, E.; Lackner, M.; and Peters, D. 2017. Structured preferences. In Endriss, U., ed., Trends in Computational Social Choice. AI Access. chapter 10, 187 207. Erdélyi, G.; Lackner, M.; and Pfandler, A. 2017. Computational aspects of nearly single-peaked electorates. Journal of Artiﬁcial Intelligence Research 58:297 337. Faliszewski, P.; Skowron, P.; Slinko, A.; and Talmon, N. 2017. Multiwinner voting: A new challenge for social choice theory. In Endriss, U., ed., Trends in Computational Social Choice. AI Access. chapter 2, 27 47.

Faliszewski, P.; Hemaspaandra, E.; and Hemaspaandra, L. 2014. The complexity of manipulative attacks in nearly single-peaked electorates. Artiﬁcial Intelligence 207:69 99. Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. Inada, K. 1964. A note on the simple majority decision rule. Econometrica 32(4):525 531. Lackner, M.-L., and Lackner, M. 2017. On the likelihood of single-peaked preferences. Social Choice and Welfare 48(4):717 745. List, C.; Luskin, R. C.; Fishkin, J. S.; and Mc Lean, I. 2012. Deliberation, single-peakedness, and the possibility of meaningful democracy: Evidence from deliberative polls. Journal of Politics 75(1):80 95. Lu, T., and Boutilier, C. 2011. Budgeted social choice: From consensus to personalized decision making. In IJCAI 11, 280 286. Mattei, N., and Walsh, T. 2013. Preﬂib: A library for preferences. In ADT 13, 259 270. http://www.preﬂib.org. Mirrlees, J. A. 1971. An exploration in the theory of optimum income taxation. Review of Economic Studies 38(2):175 208. Misra, N.; Sonar, C.; and Vaidyanathan, P. R. 2017. On the complexity of Chamberlin Courant on almost structured proﬁles. In ADT 17, 124 138. Papadimitriou, C. H. 1993. Computational complexity. Pearson. Peters, D., and Elkind, E. 2016. Preferences single-peaked on nice trees. In AAAI 16, 594 600. Peters, D., and Lackner, M. 2017. Preferences single-peaked on a circle. In AAAI 17, 649 655. Roberts, K. W. 1977. Voting over income tax schedules. Journal of Public Economics 8(3):329 340. Saporiti, A. 2009. Strategy-proofness and single-crossing. Theoretical Economics 4(2):127 163. Skowron, P.; Yu, L.; Faliszewski, P.; and Elkind, E. 2015. The complexity of fully proportional representation for singlecrossing electorates. Theoretical Computer Science 569:43 57. Skowron, P.; Faliszewski, P.; and Lang, J. 2016. Finding a collective set of items: From proportional multirepresentation to group recommendation. Artiﬁcial Intelligence 241:191 216. Yang, Y., and Guo, J. 2015. How hard is control in multipeaked elections: A parameterized study. In AAMAS 15, 1729 1730. Yang, Y., and Guo, J. 2017. The control complexity of r-approval: from the single-peaked case to the general case. Journal of Computer and System Sciences 89:432 449. Yu, L.; Chan, H.; and Elkind, E. 2013. Multiwinner elections under preferences that are single-peaked on a tree. In IJCAI 13, 425 431.