# a_characterization_of_the_singlepeaked_singlecrossing_domain__baf88fdc.pdf

A Characterization of the Single-Peaked Single-Crossing Domain

Edith Elkind University of Oxford, UK elkind@cs.ox.ac.uk

Piotr Faliszewski AGH University, Poland faliszew@agh.edu.pl

Piotr Skowron University of Warsaw, Poland p.skowron@mimuw.edu.pl

We investigate elections that are simultaneously singlepeaked and single-crossing (SPSC). We show that the domain of 1-dimensional Euclidean elections (where voters and candidates are points on the real line, and each voter prefers the candidates that are close to her to the ones that are further away) is a proper subdomain of the SPSC domain, by constructing an election that is single-peaked and singlecrossing, but not 1-Euclidean. We then establish a connection between narcissistic elections (where each candidate is ranked first by at least one voter), single-peaked elections and single-crossing elections, by showing that an election is SPSC if and only if it can be obtained from a narcissistic singlecrossing election by deleting voters. We show two applications of our characterization.

1 Introduction Arrow s impossibility theorem (Arrow 1951) shows that there is no perfect method of aggregating a collection of votes (represented as preference orders over some candidate set). In other words, there is no perfect voting rule that one could always use, independently of the circumstances. However, this result holds under the assumption that there are no constraints on the voters preferences. Thus, a common strategy to circumvent Arrow s theorem is to consider restricted preference domains, i.e., assume that the voters preferences have additional structure. It may then be possible to show that various negative consequences of Arrow s theorem do not hold. Perhaps the best-known example of such a domain is the set of elections where voters preferences are singlepeaked (Black 1948). Informally, in single-peaked elections all candidates can be ordered along a single axis, each voter has a most preferred point on this axis, and each voter ranks all candidates so that if candidate a lies between candidate b and the voter s most preferred point then this voter prefers a to b (see Section 2). The single-peaked domain has a number of attractive properties: every single-peaked election has a (weak) Condorcet winner (i.e., a candidate preferred to every other candidate by a (weak) majority of voters), its majority relation is transitive (i.e., if a majority of voters prefer a to b and a majority of voters prefer b to c, then a majority

Copyright 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

of voters prefer a to c) (Inada 1969), and it admits a nonmanipulable voting rule (Moulin 1980). Another well-studied restricted domain is that of elections with single-crossing preferences (Mirrlees 1971; Roberts 1977). In such elections, the voters can be ordered so that for every pair of candidates their trajectories in the voters preferences intersect at most once, i.e., for every pair of candidates a, b it holds that if the first voter in the ordering ranks a above b then the voters who prefer a to b form a prefix of the ordering. Single-crossing elections share some of the desirable properties of single-peaked elections (e.g., every single-crossing election has a (weak) Condorcet winner), but neither of the restrictions implies the other. Singlecrossing preferences play an important role in the analysis of income redistribution (Mirrlees 1971; Roberts 1977; Meltzer and Richard 1981), coalition formation (Demange 1994), and strategic voting (Saporiti and Tohm e 2006; Barber a and Moreno 2011; Saporiti 2009). Computational complexity considerations provide another reason to focus on restricted preference domains: such domains may admit efficient algorithms for social choice problems that are hard for general preferences. This observation has recently led to a new wave of interest in restricted domains within the computational social choice community (Conitzer 2009; Walsh 2007; Faliszewski et al. 2011; Brandt et al. 2010; Faliszewski, Hemaspaandra, and Hemaspaandra 2011; Betzler, Slinko, and Uhlmann 2013; Cornaz, Galand, and Spanjaard 2012; 2013; Skowron et al. 2013). Most of this work focuses on single-peaked elections, though some of the papers (in particular, those of Cornaz et al. (2013) and of Skowron et al. (2013)) also discuss singlecrossing elections. The goal of this paper is to develop an understanding of the interplay between the single-peaked domain and the single-crossing domain by investigating elections that are both single-peaked and single-crossing; we refer to the resulting domain as the SPSC domain. We are also motivated by complexity considerations: it seems plausible that SPSC domain should be regular enough to admit efficient algorithms for many computational problems, and we would like to understand if this is indeed the case. Our starting point is the observation (dating back to Grandmont (1978)) that the so-called 1-Euclidean preferences are both single-peaked and single-crossing. Under 1-

Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence

Euclidean preferences, both voters and candidates are identified with points on the real line, and each voter prefers the candidates that are closer to her to ones that are further away. 1-Euclidean preferences form a natural, rich domain, and thus supply evidence that considering preferences that are both single-peaked and single-crossing is worthwhile. Yet, we show that there are SPSC elections that are not 1-Euclidean. Nonetheless, we do obtain a complete characterization of the SPSC domain, by relating it to the domain of narcissistic elections, i.e., ones where each candidate is ranked first at least once (Bartholdi and Trick 1986). Namely, we prove that SPSC elections are exactly those that can be obtained from narcissistic single-crossing elections by deleting voters. We believe that this characterization is quite surprising, as it shows that requiring an election to be both single-peaked and single-crossing is quite restrictive. Even more importantly, this characterization is easy to work with and turns out to be very useful. As examples of its applications, we show the following two results. First, we consider the problem of identifying possible winners in single-crossing elections, in a scenario where new voters may still be added to the election, but the election has to remain single-crossing. For Plurality and the Condorcet rule, we show that a singlecrossing election is an SPSC election if and only if every candidate c is a possible winner in this scenario. Second, we show a polynomial-time algorithm for winner determination under the egalitarian version of Monroe s rule. This result illustrates that our characterization can be useful for deriving efficient algorithms: it extends the work of Skowron et al. (2013), whose algorithm applies to narcissistic singlecrossing elections only. Our algorithm improves upon theirs both in terms of the larger domain of applicability and in terms of having a better running time. We omit many of our proofs due to space restrictions, but all the proofs (and extended discussions) are available as supplementary material.

2 Preliminaries

Given a positive integer s, we write [s] to denote the set {1, . . . , s}. An election is a pair (C, V ), where C = {c1, . . . , cm} is a set of candidates and V = (v1, . . . , vn) is a list of voters. Each voter v V is described by her preference order, or vote, v, which is a linear order over C. Given a voter v V and a candidate c C, we denote by pos(v, c) the position of c in v: we have pos(v, c) = 1 if c is v s most preferred candidate and pos(v, c) = m if c is v s least preferred candidate. Voter v s most preferred candidate is denoted by top(v). We refer to the list ( v)v V as the preference profile. In what follows, we use the terms election , preferences , and profile interchangeably. Given an election E = (C, V ) and a subset of candidates D C, let V |D denote the profile obtained by restricting the preference order of each voter in V to D. The concatenation of two voter lists U and V is denoted by U + V ; if U consists of a single vote u, we simply write u + V . We say that a list U is a sublist of a list V (and write U V ) if U can be obtained from V by deleting voters. An election

(C , V ) is said to be a subelection of an election (C, V ) if C C and there exists a U V such that V = U|C . Single-crossing (or intermediate or order-restricted) preferences, first studied by Mirrlees (1971) and Roberts (1977), capture settings where the voters can be ordered along a single axis according to their beliefs.

Definition 1 An election E = (C, V ) with C = {c1, . . . , cm}, V = (v1, . . . , vn) is single-crossing (SC) (with respect to the given order of voters) if for every pair of candidates a, b such that a v1 b, there exists a t [n] such that {i [n] | a vi b} = [t].

Intuitively, as we sweep from left to right through the list of voters of a single-crossing election, the relative order of every pair of candidates changes at most once. We emphasize that we define single-crossing preferences with respect to a fixed order of the voters. Alternatively, one could define an election to be single-crossing if the voters can be ordered so that the condition in Definition 1 is satisfied. Computationally, these two approaches are essentially equivalent: given an election, one can efficiently check whether there exists an ordering of the voters satisfying the condition in Definition 1, and, if so, find such an ordering (Elkind, Faliszewski, and Slinko 2012; Bredereck, Chen, and Woeginger 2012). While single-crossing elections are defined in terms of an ordering of the voters, the definition of single-peaked elections (Black 1948) refers to an ordering of the candidates.

Definition 2 The preference order of a voter v with top(v) = c in an election E = (C, V ) is single-peaked with respect to an order over C if for every pair of candidates a, b such that a b c or c b a it holds that c v b v a. An election E = (C, V ) is single-peaked with respect to if every vote in V is single-peaked with respect to ; in this case, is called a societal axis for E. E is single-peaked (SP) if it is single-peaked with respect to some societal axis .

There are polynomial-time algorithms that given an election E decide if it is single-peaked and, if so, compute a societal axis such that E is single-peaked with respect to (Bartholdi and Trick 1986; Escoffier, Lang, and Ozt urk 2008). Thus we can assume without loss of generality that when we are given a single-peaked election, we are also provided a societal axis that witnesses this.

3 Euclidean Preferences We start our pursuit of a characterization of the SPSC domain by considering the so-called d-Euclidean elections.

Definition 3 An election E = (C, V ) is d-Euclidean if there is a mapping x : C V Rd such that for every v V and every pair of candidates a, b C it holds that a v b if and only if ||x(v) x(a)||d < ||x(v) x(b)||d, where || ||d is the Euclidean norm on Rd.

Such preferences are typical, e.g., in facility location problems, where voters choose a location for a new facility, such as a bus stop or a library, and want it as close to themselves as possible. From our point of view, 1-Euclidean

v1 : 1 a1 a2 a3 2 b1 b2 b3 3 c1 c2 c3 d1 d2 d3 4 5 v2 : a2 a1 a3 2 b1 b2 b3 3 1 c1 c2 c3 d1 d2 d3 4 5 v3 : b2 b1 b3 3 c1 c2 c3 d1 d2 d3 4 2 a3 a2 a1 1 5 v4 : c2 c1 c3 d1 d2 d3 4 3 b3 b2 b1 2 a3 a2 a1 1 5 v5 : d2 d1 d3 c3 c2 c1 4 5 3 b3 b2 b1 2 a3 a2 a1 1 v6 : 5 4 d3 d2 d1 c3 c2 c1 3 b3 b2 b1 2 a3 a2 a1 1

Table 1: The profile used in the proof of Proposition 4. We omit the symbols between the candidates for clarity.

elections are of particular interest because they are both single-peaked and single-crossing (this observation is due to Grandmont (1978), and is easy to check). Yet, we show that the converse does not hold, i.e., there are SPSC elections that are not 1-Euclidean (a stronger version of this result was obtained recently by Chen, Pruhs, and Woeginger (2014)).

Proposition 4 There is an election E that is SPSC, but is not 1-Euclidean.

Proof Consider the election E from Table 1. There are 6 voters, v1, . . . , v6, and 17 candidates, 1, 2, 3, 4, 5, a1, a2, a3, b1, b2, b3, c1, c2, c3, d1, d2, d3. It is single-crossing with respect to the given order of the voters and it is single-peaked with respect to the order of the candidates given by v1. We now show that it is not 1-Euclidean. Assume for the sake of contradiction that all voters and candidates can be mapped to points on the real line R so that voters preferences are determined by the Euclidean distance. Note that the order of candidates on the line must provide a societal axis that witnesses the single-peakedness of E. Since the preference orders of v1 and v6 are opposites of each other, the only admissible societal axes for E are given by the preference orders of v1 and v6; this follows from the fact that candidates 1 and 5 have to appear at different endpoints of the societal axis (see, e.g., (Escoffier, Lang, and Ozt urk 2008)). By symmetry, we can conclude without loss of generality that the order of the candidates on the real line is given by v1. In what follows, we identify voters and candidates with their positions on the line. For c, c {1, 2, 3, 4, 5}, let dc,c denote the distance between c and c . Voter v2 must lie between a1 and a3, and thus before 2. Since we have 2 v2 3 v2 1, it follows that d1,2 > d2,3. Similarly, by considering v3 we get d2,3 > d3,4, and by considering v5 we get d3,4 > d4,5. Combining these inequalities, we get d1,3 = d1,2 + d2,3 > d2,3 + d3,4 > d3,4 + d4,5 = d3,5. For voter v4, we have 3 v4 1 v4 5, and hence d1,3 < d3,5, a contradiction. 2

4 Characterization of SPSC

Our main result the characterization of the SPSC domain is based on the concept of narcissistic singlecrossing elections. An election is narcissistic if every candidate is ranked first by at least one voter; this happens, e.g., when candidates are allowed to vote for themselves. This notion was introduced by Bartholdi and Trick (1986), and was used by Cornaz et al. (2012; 2013) and Skowron et al. (2013) in the context of voting rules with computationally hard

winner-determination procedures. Interestingly, the narcissistic domain turns out to be closely related to the two domains that are the focus of this paper: every narcissistic single-crossing (NSC) election is single-peaked (this observation follows from the discussion of top-monotonicity by Barber a and Moreno (2011)).

Proposition 5 A narcissistic single-crossing election is single-peaked with respect to the axis given by the preference order of the first voter.

Naturally, the intersection of the single-peaked domain and the single-crossing domain contains elections that are not narcissistic single-crossing. To see this, it suffices to note that SPSC is closed under voter deletion: Given an SPSC election and some candidate c in it, we can delete all voters that rank c first to obtain an SPSC election that is not narcissistic. This observation motivates us to study the closure of the narcissistic single-crossing domain under voter deletion.

Definition 6 An election E = (C, V ) is pre-narcissistic single-crossing (pre-NSC) if there exists a narcissistic single-crossing election E = (C, V ) such that V V .

Clearly, pre-NSC elections are single-crossing and singlepeaked. The main result of this paper is that the converse is also true: every SPSC election is pre-NSC. The following two lemmas will be useful in our discussion. The first one provides a characterization of votes that can be inserted into a single-crossing profile so that it remains single-crossing.

Lemma 7 Consider a single-crossing election E = (C, V ), where C = {c1, . . . , cm} and V = (v1, . . . , vn).

1. The election E = (C, V ) obtained from E by inserting a vote v right after a vote vi, i [n 1], is singlecrossing if and only if v has the following property: for every pair of candidates cj, cℓ C it holds that if cj v cℓthen cj vi cℓor cj vi+1 cℓ. 2. The election E+ = (C, V +) obtained from E by inserting a vote v+ right after vn (i.e., V + = V + v+) is singlecrossing if and only if v+ has the following property: for every pair of candidates cj, cℓ C it holds that if cj v+ cℓthen either cj vn cℓor cℓ vi cj for all i [n]. 3. The election E = (C, V ) obtained from E by inserting a vote v right before v1 (i.e., V = v + V ) is singlecrossing if and only if v has the following property: for every pair of candidates cj, cℓ C it holds that if cj v cℓthen either cj v1 cℓor cℓ vi cj for all i [n].

Our second lemma relates an order of the voters witnessing that the election is single-crossing and an axis witnessing that the election is single-peaked.

Lemma 8 Suppose that election E = (C, V ) with C = {c1, . . . , cm}, V = (v1, . . . , vn) is single-crossing and single-peaked with respect to the candidate order c1 . . . cm. Suppose that the top-ranked candidate in v1 is ci and the top-ranked candidate in vn is cj for some i j. Then the most preferred candidate of each voter lies between ci and cj, i.e., if cℓis the top-ranked candidate in some vk in V , then i ℓ j.

Proof Suppose that for some vote vk, k [n], the topranked candidate in vk is cℓfor some ℓ< i. Since vj is single-peaked with respect to , ci appears above cℓin vn. Therefore, the pair of candidates (ci, cℓ) and the triple of votes (v1, vk, vn) provide a witness that E is not singlecrossing. Similarly, suppose that for some vote vk, k [n], the top-ranked candidate in vk is cℓfor some ℓ> j. Since vi is single-peaked with respect to , cj appears above cℓin v1. Therefore, the pair of candidates (cj, cℓ) and the triple of votes (v1, vk, vn) provide a witness that E is not singlecrossing. 2

We are now ready to prove our main result.

Theorem 9 An election is SPSC if and only if it is pre-NSC.

Proof We have already argued that every pre-NSC election is SPSC. For the converse direction, we proceed in two steps: First, we argue (Lemma 10) that we can take an SPSC election E and prepend a vote that orders the candidates in the same way as some axis witnessing that E is single-peaked, so that the resulting election remains singlecrossing. To complete the proof, we then describe a procedure that takes an SPSC election where the axis is given by the first vote, and adds new votes so that each candidate receives at least one first-place vote and the election remains SPSC. Given an axis for an election E = (C, V ), let v be the vote that corresponds to , i.e., for every ck, cℓ C it holds that ck is ranked above cℓin v if and only if ck cℓ.

Lemma 10 Suppose that election E = (C, V ) with C = {c1, . . . , cm}, V = (v1, . . . , vn) is SPSC. Then there exists some axis such that E is single-peaked with respect to and the election (C, v + V ) is also SPSC.

Proof Clearly, for every axis such that E is singlepeaked with respect to the election (C, v + V ) is singlepeaked. To show that can be chosen so that (C, v + V ) is single-crossing, we proceed as follows. We pick an arbitrary axis witnessing that E is single-peaked, and try to prepend it to V . If this turns out to lead to an election that is not single-crossing, we find a minimal pair of candidates that violates the single-crossing property, and modify based on this pair. We then show that our modification is legal, i.e., it results in another axis witnessing that our election is single-peaked. Further, we show that this modification step can be executed at most m times. It follows that eventually we obtain a single-crossing election. The details follow. Suppose that the top-ranked candidate in v1 is ci and the top-ranked candidate in vn is cj. Consider some axis such that E is single-peaked with respect to and ci cj. We say that a pair of candidates (ck, cℓ) is violating for if ck cℓ, cℓ v1 ck, and ck vn cℓ. By the third claim of Lemma 7, the election (C, v + V ) is not single-crossing if and only if there exists some violating pair for . Observe that if a pair (ck, cℓ) is violating for then ck ci and cj cℓ. Indeed, if ck = ci or ci ck, then v and v1 agree on (ck, cℓ), and if cℓ= cj or cℓ cj then v and vn disagree on (ck, cℓ).

Let S be the set of all violating pairs for . Given a pair (ck, cℓ) S , let:

δ (ck, cℓ, ) = |{c | ck c ci}|,

δ+(ck, cℓ, ) = |{c | cj c cℓ}|.

We say that (cp, cq) S is a minimal violating pair for if δ (cp, cq, ) δ (ck, cℓ, ) for all (ck, cℓ) S and δ+(cp, cq, ) δ+(ck, cℓ, ) for all (ck, cℓ) S . If (cp, cq) is a minimal violating pair for , we set δ( ) = δ (cp, cq, ). Now, pick an arbitrary axis such that E is single-peaked with respect to ; assume without loss of generality that c1 . . . cm. If there are no violating pairs for , we are done. Otherwise, let (cp, cq) be a minimal violating pair for . Consider the axis obtained from by swapping the tails (c1, . . . , cp) and (cq, . . . , cm). Formally, is given by

cm cm 1 cq cp+1 cq 1 cp c1.

We now prove that every vote in V is single-peaked with respect to . Indeed, suppose that this is not the case for some vote v V , and let ct be the top-ranked candidate in v. Note that by Lemma 8 we have i t j. Let C = {c1, . . . , cp}, C = {cp+1, . . . , ct 1} C+ = {ct+1, . . . , cq 1}, C++ = {cq, . . . , cm}. Observe that v is not single-peaked with respect to if and only if (a) a v b for some a C , b C+ or (b) c v d for some c C++, d C . We now argue that neither of these cases is possible. Consider first case (a). Since p < i and q > j, v s most preferred candidate in C is cp, and his least preferred candidate in C+ is cq 1, so it has to be the case that v prefers cp to cq 1. On the other hand, v1 prefers cq to cp; since q > i, this implies that he prefers cq 1 to cp. Further, vn prefers cq 1 to cp, since otherwise (cp, cq 1) would be a violating pair with δ+(cp, cq 1, ) < δ+(cp, cq, ), a contradiction with (cp, cq) being a minimal violating pair for . Thus, the pair (cp, cq 1) and the triple (v1, v, vn) provide a witness that E is not single-crossing, a contradiction. The argument for case (b) is similar. Since p < i and q > j, v s most preferred candidate in C++ is cq, and his least preferred candidate in C is cp+1, so it has to be the case that v prefers cq to cp+1. On the other hand, vn prefers cp to cq; since p < j, this implies that he prefers cp+1 to cq. Further, v1 prefers cp+1 to cq, since otherwise (cp+1, cq) would be a violating pair with δ (cp+1, cq, ) < δ (cp, cq, ), a contradiction with (cp, cq) being the minimal violating pair for . Thus, the pair (cp+1, cq) and the triple (v1, v, vn) provide a witness that E is not single-crossing, a contradiction. We have shown that E is single-peaked with respect to . We now argue that if (ck, cℓ) is a violating pair for , then k {m, . . . , q + 1} and hence δ( ) > δ( ). Note first that if (ck, cℓ) is a violating pair for , then ck has to be located to the left of ci with respect to , so either k {m, . . . , q} or k {p + 1, . . . , i 1}. Similarly, cℓhas to be located to the right of cj with respect to , so either ℓ {j + 1, . . . , q 1} or ℓ {p, . . . , 1}. We consider the following cases and conclude that each of them is impossible.

1. k {p + 1, . . . , i 1}, ℓ {j + 1, . . . , q 1}. Then (ck, cℓ) is a violating pair for , a contradiction with our choice of (cp, cq).

2. k {p+1, . . . , i 1}, ℓ {p, . . . , 1}. Since v1 is singlepeaked with respect to and p < i, v1 prefers ck to cℓ, so (ck, cℓ) cannot be a violating pair for .

3. k = q, ℓ {j + 1, . . . , q 1}. Since vn is single-peaked with respect to and j < ℓ< q, vn prefers cℓto ck, so (ck, cℓ) cannot be a violating pair for .

4. k = q, ℓ {p, . . . , 1}. Since (cp, cq) is a violating pair with respect to , v1 prefers ck to cp. Since v1 is singlepeaked with respect to and ℓ p < i, v1 prefers ck to cℓ, so (ck, cℓ) cannot be a violating pair for .

Thus, the only remaining possibility is that k > q and therefore δ( ) > δ( ). We now apply the same argument to . If v + V is single-crossing, we are done, and otherwise we obtain an axis such that E is single-peaked with respect to and δ( ) > δ( ). We then continue in the same manner; since δ( ) m for every axis , after at most m steps we arrive to an axis such that E is single-peaked with respect to and v + V is single-crossing. The proof is complete. 2

We are now ready to complete the proof of Theorem 9. Consider an SPSC election E = (C, V ) with C = {c1, . . . , cm}, V = (v1, . . . , vn). By Lemma 10 we can assume that E is single-peaked with respect to the candidate order c1 . . . cm, and v1 is given by c1 cm. We now show how to complete E to a single-crossing narcissistic election. For every ci C, let Vi be the list of voters who rank ci first. Consider two candidates ci, cj C such that Vi = , Vj = and i < j. Since E is single-crossing and ci v1 cj, in V all voters from Vi appear before those from Vj. Let cs be the first candidate for which Vs = . Note that s > 1, since c1 is ranked first by v1. We have Vr = for all r < s, and, in particular, Vs 1 = . Let u be the last voter in Vs 1. Since u s preference order is single-peaked with respect to , his vote can be written as cs 1 cs 2 cs ℓ cs . . . for some ℓ 1. Now consider the vote v obtained by moving cs to the top of u without changing the relative order of the remaining candidates. We claim that the election obtained by inserting v right after u remains single-peaked with respect to as well as singlecrossing. Single-peakedness is immediate from the construction: intuitively, when ranking candidates, v starts at cs, then moves one step to the left, then emulates u. We will now show that the new election is single-crossing. Suppose that u = vn, and let w be the voter that appears right after u in V . The most preferred candidate of w is some cq for q > s. Since w is single-peaked with respect to and ranks cq first, v and w agree on all pairs of the form (cs, cs r), r [ℓ]. On the other hand, u and v agree on all other pairs of candidates. By the first claim of Lemma 7, we are done.

Now, suppose that u = vn, i.e., v is the last voter in the new election. The only pairs of candidates that u and v disagree on are (cs, cs 1), . . . , (cs, cs ℓ). On the other hand, both v1 and u (and hence all voters in V ) rank cs below cs r for all r = 1, . . . , ℓ. By the second claim of Lemma 7, we are done. We have successfully added a vote that ranks cs first. By repeating this construction for all candidates that had no first-place votes in the original election, we obtain a narcissistic profile that is single-crossing and single-peaked with respect to . This completes the proof. 2

Theorem 9 is constructive and it implies a polynomialtime algorithm that given an SPSC election E finds an NSC election that can be obtained from E by adding voters. However, we also provide a more efficient, explicit algorithm.

Theorem 11 There exists an algorithm that given an election E = (C, V ) decides whether it is pre-NSC, and, if so, constructs an NSC election E = (C, V ) such that V V , in time O(nm2).

The algorithm given in the proof of Theorem 11 leads to a characterizaton of the SPSC domain that is slightly different from the one provided by Theorem 9.

Corollary 12 An election E = (C, V ) is SPSC if and only if for each candidate c C there exists a vote vc with top(vc) = c such that the election (C, V + vc) is singlecrossing for an appropriate re-ordering of the voters.

5 Applications of the Characterization Possible Winners in Single-Crossing Elections. Let us consider the following incomplete information scenario. We know that voters preferences form a single-crossing preference profile over a given domain. However, we can only observe a subset of the votes, and have no information about the remaining ones (except that the full election is singlecrossing). We want to know which candidates may be the winners of the full election. This setting is similar, but not identical, to the classic possible winner problem of Konczak and Lang (2005) and to the manipulation problem, especially in its optimization variant (Zuckerman, Procaccia, and Rosenschein 2009). It turns out that for Plurality and for the Condorcet rule, every candidate is a potential winner if and only if the observed (incomplete) election is SPSC. Recall that under the Plurality rule, each candidate gets a point from each voter who ranks her first, and the winners are the candidates with the largest number of points. Under the Condorcet rule, we output the candidate that is preferred to every other candidate by a strict majority of the voters (the so-called Condorcet winner) whenever it exists (otherwise we return no winners).

Proposition 13 Suppose that R {Plurality, the Condorcet rule}. Consider a single-crossing election E = (C, V ). Then E is SPSC if and only if for every candidate c C there exists a single-crossing election Ec = (C, Vc) with V Vc, where c is the winner under R.

Proof For the only if direction, suppose that E is SPSC. Then, by Theorem 9 there is an NSC election E = (C, V )

with V V . Let n be the number of voters in E . Consider a candidate c C . Since E is narcissistic, it contains a vote vc with top(v) = c. Consider the election Ec obtained from E by inserting n copies of vc right after vc. Clearly, this election is single-crossing. Further, in Ec candidate c is ranked first by a strict majority of voters, so she is the unique winner under Plurality, and is the Condorcet winner. For the if direction, suppose that E is not SPSC. Corollary 12 implies that there exists a candidate c C such that in every election E = (C, V ) with V V no voter in V ranks c first. This immediately implies that c is not a winner under Plurality. To see that c is not the Condorcet winner in E , suppose that E contains n voters, and let c be the top candidate of voter n

2 + 1. It is easy to see that, since E is single-crossing, at least half of the voters prefer c to c, which implies our claim. 2

Fully Proportional Representation. For some election problems, the SPSC assumption leads to algorithms that are much faster than those known under the SP assumption or under the SC assumption alone. Here we show this effect through a highly efficient winner determination algorithm for the egalitarian Monroe voting rule. For further discussion of this rule, related rules, and the SP/SC domains, we point the readers to the papers of Monroe (1995), Betzler et al. (2013), Skowron et al. (2013), and Yu et al. (2013) The goal of the egalitarian Monroe rule is to elect a committee that represents the voters (e.g., a parliament). If there are n voters and we seek a committee of size k, then the rule picks k candidates and assigns each of them to n

k voters, so that each voter has a candidate assigned (if k does not divide n, then some candidates are assigned to n

k voters each, and the remaining ones are assigned to n

k voters each). The quality of an assignment is measured in terms of a dissatisfaction function α : [m] N. We require α to be non-decreasing; the most typical function α is α(i) = i. The dissatisfaction of a voter v from having a candidate c assigned is α(pos(v, c)); the higher the dissatisfaction of a voter, the less happy this voter is with the assigned candidate. The global dissatisfaction of the voters is the dissatisfaction of the worst-off voter (in the utilitarian variant of the rule, defined by Monroe (1995), the global dissatisfaction is the sum of voters dissatisfactions). We seek an assignment that minimizes the global dissatisfaction. The problem of finding winners of the egalitarian Monroe rule is computationally hard in the unrestricted domain (Procaccia, Rosenschein, and Zohar 2008; Betzler, Slinko, and Uhlmann 2013); for the utilitarian version, the hardness holds even for single-crossing preferences (Skowron et al. 2013), and it is conjectured that the same holds for the single-peaked domain. On the positive side, for the egalitarian version there is an algorithm for single-peaked preferences (Betzler, Slinko, and Uhlmann 2013) that runs in time O(n3m3k3), and there is an algorithm for narcissistic single-crossing preferences (Skowron et al. 2013) that runs in time O(nm2k). We extend the result of Skowron et al. by proving the following result.

Theorem 14 There is an algorithm that given a SPSC election E with m candidates, a positive integer k m, and a

dissatisfaction function α, finds a set of k egalitarian Monroe winners for E. This algorithm runs in time O(m2n).

The main idea of our algorithm is similar to that of Skowron et al. s, yet using our characterizaton of the SPSC domain and a more efficient dynamic programming formulation, we obtain a more general algorithm with better running time. One can also compare our algorithm to that of Betzler et al. (2013) for single-peaked preferences: While the latter algorithm works for a larger domain, its running time is substantially worse. We omit most details of the proof of Theorem 14, but the following lemma is particularly important for our algorithm (and we believe that it will prove useful for many other applications of our SPSC characterization).

Lemma 15 For every election E = (C, V ) with C = {c1, . . . , cm}, V = (v1, . . . , vn) that is SPSC with respect to the voter order (v1, . . . , vn) and for every candidate c C there exists a voter vℓ V such that for every pair of voters vi, vj satisfying j < i ℓor ℓ i < j it holds that pos(vj, c) pos(vi, c).

Proof If an election E has the property described in the statement of the lemma, then any election obtained from E by deleting voters also has this property. Thus, it suffices to prove the lemma for the case when E is narcissistic singlecrossing. Fix a candidate c C and let vℓbe some voter that ranks c first. Consider two voters, vj and vi, such that j < i ℓ. If pos(vj, c) < pos(vi, c), there exists a candidate c such that vj prefers c to c , but vi prefers c to c. However, vℓranks c first, so she also prefers c to c , and this is a contradiction with the assumption that E is single-crossing. The case ℓ i < j can be handled similarly. 2

The lemma says that in an SPSC election the trajectory of each candidate in voters preferences has a single peak, i.e., each candidate first rises in the rankings and then descends.

6 Conclusions

We have explored the domain of all elections that are simultaneously single-peaked and single-crossing. We refuted a natural conjecture concerning such elections, namely, that every SPSC election can be embedded into the real line so that the voters preferences over the candidates are determined by simple geometric considerations. We then established a connection between narcissistic elections, singlecrossing elections, and single-peaked elections that led to a characterization of the SPSC domain. We used our characterization to show that an SC election has the property that each candidate can become a winner after adding some voters (while maintaining the single-crossing property of the election) if and only if it is SPSC. Further, we have shown an efficient algorithm for the problem of computing the winners under the egalitarian Monroe s rule for the SPSC domain. It would be interesting to see if there are other natural problems in computational social choice that can be solved in polynomial time for SPSC preferences, but remain hard if the preferences are either only single-peaked or only singlecrossing.

Acknowledgements Part of this work was done while the first author was employed by Nanyang Technological University, Singapore, and supported by National Research Foundation (Singapore) grant NRF2009-08. The second author was supported by NCN grants 2012/06/M/ST1/00358 and 2011/03/B/ST6/01393, and by AGH University grant 11.11.230.015. The third author was supported by Polish National Science Center grant Preludium UMO2013/09/N/ST6/03661. The authors would like to thank the anonymous AAAI reviewers for their very useful feedback.

References Arrow, K. 1951. Social Choice and Individual Values. John Wiley and Sons. Barber a, S., and Moreno, B. 2011. Top monotonicity: A common root for single peakedness, single crossing and the median voter result. Games and Economic Behavior 73(2):345 359. Bartholdi, III, J., and Trick, M. 1986. Stable matching with preferences derived from a psychological model. Operations Research Letters 5(4):165 169. Betzler, N.; Slinko, A.; and Uhlmann, J. 2013. On the computation of fully proportional representation. Journal of Artificial Intelligence Research 47:475 519. Black, D. 1948. On the rationale of group decision-making. Journal of Political Economy 56(1):23 34. Brandt, F.; Brill, M.; Hemaspaandra, E.; and Hemaspaandra, L. 2010. Bypassing combinatorial protections: Polynomialtime algorithms for single-peaked electorates. In Proceedings of the 24th AAAI Conference on Artificial Intelligence, 715 722. Bredereck, R.; Chen, J.; and Woeginger, G. 2012. A characterization of the single-crossing domain. Social Choice and Welfare. To appear. Chen, J.; Pruhs, K.; and Woeginger, G. 2014. Characterizations of the one-dimensional Euclidean domain. In preparation. Conitzer, V. 2009. Eliciting single-peaked preferences using comparison queries. Journal of Artificial Intelligence Research 35:161 191. Cornaz, D.; Galand, L.; and Spanjaard, O. 2012. Bounded single-peaked width and proportional representation. In Proceedings of the 20th European Conference on Artificial Intelligence, 270 275. Cornaz, D.; Galand, L.; and Spanjaard, O. 2013. Kemeny elections with bounded single-peaked or single-crossing width. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, 76 82. Demange, G. 1994. Intermediate preferences and stable coalition structures. Journal of Mathematical Economics 23(1):45 58. Elkind, E.; Faliszewski, P.; and Slinko, A. 2012. Clone structures in voters preferences. In Proceedings of the 13th ACM Conference on Electronic Commerce, 496 513.

Escoffier, B.; Lang, J.; and Ozt urk, M. 2008. Single-peaked consistency and its complexity. In Proceedings of the 18th European Conference on Artificial Intelligence, 366 370. Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L.; and 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.; Hemaspaandra, E.; and Hemaspaandra, L. 2011. The complexity of manipulative attacks in nearly single-peaked electorates. In Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, 228 237. Grandmont, J. 1978. Intermediate preferences and the majority rule. Econometrica 46(2):317 330. Inada, K. 1969. The simple majority decision rule. Econometrica 37(3):490 506. Konczak, K., and Lang, J. 2005. Voting procedures with incomplete preferences. In Proceedins of the Multidisciplinary IJCAI-05 Worshop on Advances in Preference Handling, 124 129. Meltzer, A. H., and Richard, S. F. 1981. A rational theory of the size of government. Journal of Political Economy 89(5):914 927. Mirrlees, J. 1971. An exploration in the theory of optimal income taxation. Review of Economic Studies 38:175 208. Monroe, B. 1995. Fully proportional representation. American Political Science Review 89(4):925 940. Moulin, H. 1980. On strategy-proofness and single peakedness. Public Choice 35(4):437 455. Procaccia, A.; Rosenschein, J.; and Zohar, A. 2008. On the complexity of achieving proportional representation. Social Choice and Welfare 30(3):353 362. Roberts, K. W. S. 1977. Voting over income tax schedules. Journal of Public Economics 8(3):329 340. Saporiti, A., and Tohm e, F. 2006. Single-crossing, strategic voting and the median choice rule. Social Choice and Welfare 26(2):363 383. Saporiti, A. 2009. Strategy-proofness and single-crossing. Theoretical Economics 4(2):127 163. Skowron, P.; Yu, L.; Faliszewski, P.; and Elkind, E. 2013. The complexity of fully proportional representation for single-crossing electorates. In Proceedings of the 6th International Symposium on Algorithmic Game Theory, 1 12. Walsh, T. 2007. Uncertainty in preference elicitation and aggregation. In Proceedings of the 22nd National Conference on Artificial Intelligence, 3 8. AAAI Press. Yu, L.; Chan, H.; and Elkind, E. 2013. Multiwinner elections under preferences that are single-peaked on a tree. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, 425 431. Zuckerman, M.; Procaccia, A.; and Rosenschein, J. 2009. Algorithms for the coalitional manipulation problem. Artificial Intelligence 173(2):392 412.