# preferences_singlepeaked_on_a_circle__ce32d61a.pdf

Preferences Single-Peaked on a Circle

Dominik Peters and Martin Lackner Department of Computer Science University of Oxford, UK {dominik.peters, martin.lackner}@cs.ox.ac.uk

We introduce the domain of preferences that are singlepeaked on a circle, which is a generalization of the wellstudied single-peaked domain. This preference restriction is useful, e.g., for scheduling decisions, and for one-dimensional decisions in the presence of extremist preferences. We give a fast recognition algorithm of this domain, provide a characterisation by ﬁnitely many forbidden subproﬁles, and show that many popular singleand multi-winner voting rules are polynomialtime computable on this domain. In contrast, Kemeny s rule remains hard to evaluate, and several impossibility results from social choice theory can be proved using only proﬁles that are single-peaked on a circle.

1 Introduction A central problem in the study of multi-agent systems is the aggregation of agents preferences in order to make group decisions. Impossibility theorems and computational hardness result make this problem a hard one to solve. However, a successful line of research going back to Black s (1948) seminal article has managed to circumvent many problems in (computational) social choice for the special case when agents preferences are single-peaked. Under this preference restriction, we assume that agents have preferences over the possible values of a one-dimensional quantity such as the timing of a deadline, a tax rate, a thermostat setting, or the price of a new product. A preference ordering is single-peaked if an agent has a certain most-preferred value of the quantity and derives less and less satisfaction from values that are further away from the subjective optimum. Another popular application of this setting is in political elections, where it is often held that candidates can be ordered on a left-to-right spectrum making the voters preferences single-peaked. Preference proﬁles that consist solely of single-peaked preference orderings have attractive properties, both algorithmically and in terms of their social choice behaviour (Elkind, Lackner, and Peters 2016). For example, winner determination problems that are computationally hard in the general case tend to be easy when restricted to single-peaked proﬁles (Brandt et al. 2015; Betzler, Slinko, and Uhlmann 2013), and the single-peaked domain admits a strategyproof voting rule

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

a b c d e f g h

Figure 1: Example of preferences single-peaked on a circle.

and guarantees the existence of Condorcet winners as well as transitivity of the majority relation (Moulin 1991). The usefulness of results of this type is limited by the extent to which proﬁles in practice actually happen to be single-peaked. One way of dealing with this is to consider less restrictive generalisations of single-peakedness. Maybe the structure of the alternative space is not quite onedimensional, and in this case it might be useful to consider preferences that are single-peaked on a tree (Demange 1982). This domain is notably larger, yet still retains many desirable properties in social choice terms; however, its algorithmic usefulness is more mixed (Yu, Chan, and Elkind 2013; Peters and Elkind 2016). In this paper, we identify a new preference restriction: being single-peaked on a circle. Here we assume that alternatives can be placed on a circle, with agents preferences again being decreasing on both sides of their peaks. See Figure 1 for some example shapes that preference curves might have in this setting; higher points are more preferred. Note that the circle wraps around, and so h and a are adjacent. Intuitively, a preference proﬁle is single-peaked on a circle if, for every agent, we can cut the cycle once so that the agent s preferences are single-peaked on the resulting line. Crucially, the location of the cutting point may differ for each agent. The aim of this paper is to explore this new preference domain in detail. We will ﬁnd that this domain is algorithmically useful (it often allows for efﬁcient winner determination), but it performs less convincingly in terms of axiomatic properties (since voting paradoxes still occur and impossibility results can still be proven). Interestingly, this is precisely opposite to how the results turned out for single-peakedness on trees.

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

Motivating Examples. There are many practical scenarios where we might expect preferences to be single-peaked on a circle. This is even the case when, on ﬁrst sight, there seems to be no circle anywhere. Indeed, suppose that alternatives are naturally ordered on a line; we may pretend this line is a circle by joining up its endpoints. Of course, every order that is single-peaked on the line is also single-peaked on the circle. But crucially, the reverse of such an order, now single-caved on the line, is still single-peaked on the same circle. Thus, our new preference restriction allows us to combine single-peaked and single-caved votes (as shown on the right). One interpretation is that this move allows us to accommodate extremists . For example, while most people have a sweet spot somewhere on the left-right political axis, some people might dislike centrist options and prefer the extremes. When planning a vacation, some might have an optimal climate in mind, while others like it both very cold (skiing) and very hot (beaches), but dislike compromises (England). Other examples of alternative spaces are more explicitly cyclic. Consider, for example, ﬁnding a good time for a daily event (such as a day or night shift, or a meeting, or the timing of backups) where possibilities are arranged in a 24 hour cycle. A similar structure exists when scheduling an international phone call; here, different time zones are arranged along the equator, and lead to cyclic preferences. But perhaps the most appealing example of preferences that can be expected to be single-peaked on a circle come from problems inspired by facility location. Rather many structures have a boundary that is (roughly) isomorphic to a cycle, including most cities and countries. The problem of deciding where to locate a new airport for a city would be one example, since airports are usually positioned on the boundary. Similarly, where should a company build new ofﬁce space? To which coastal region should a family move? Where do we want to sit in a football stadium? Another plausible application could be inspired by security concerns, if we consider the placement of border security checkpoints. Contributions. We formally deﬁne single-peakedness on circles and immediately extend this deﬁnition to preferences with ties, and to dichotomous (approval) preferences. We show that it is possible to efﬁciently recognise whether a given preference proﬁle is single-peaked on some circle, and if so return a suitable circle. For the case of preferences without ties, we give a recognition algorithm that runs in linear time, matching the performance in the case for the line. We characterise the domain of preferences single-peaked on a circle through a list of ﬁnitely many forbidden subproﬁles with 2 voters and 5 alternatives, and with 3 voters and 4 alternatives. The proof of this characterisation implies that our linear-time recognition algorithm can certify its negative answers by exhibiting a forbidden subproﬁle. While single-peakedness on a line serves as a way to circumvent many impossibility results in social choice, we show that such impossibilities (including the Gibbard Satterthwaite theorem) can still be proven when preferences

are allowed to be single-peaked on a circle. We then study the algorithmic properties of our new preference extension. We show that Young s voting rule (and also Young scores) can be efﬁciently computed if preferences are single-peaked on a circle; this algorithm also improves upon the state-of-the-art when it comes to preferences singlepeaked on a line. We also show that several multi-winner voting rules are efﬁciently computable in our restricted case, including the Chamberlin Courant rule and Proportional Approval Voting (PAV). These results rely on a recent technique using total unimodularity and integer programming (Peters 2016). On the other hand, we show that Mc Garvey s theorem (Mc Garvey 1953) can be proven using only preferences single-peaked on a circle; thus, Kemeny s rule remains NPhard to evaluate even in this setting.

2 Deﬁnition Let A be a ﬁnite set of alternatives (or candidates). A weak order (or preference relation) is a binary relation over A which is complete and transitive. A linear order is a weak order that is antisymmetric, and so does not allow preference ties; a strict linear order is the irreﬂexive part of a linear order. A proﬁle P = (v1, . . . , vn) over A is a list of weak orders over A. The elements of N = {1, . . . , n} are called voters, and we associate voter i N with the order vi, which we call the vote of voter i. For convenience, we write a i b whenever (a, b) vi, i.e., when voter i weakly prefers alternative a to alternative b. We also use i and i for the strict and indifference parts of i. We will always write m for the number of alternatives and n for the number of voters. If vi is a linear order, we write top(vi) for i s most-preferred alternative. An axis is a strict linear order of the alternatives. We usually think of an axis as describing the underlying onedimensional structure of the alternative space. A linear order vi is single-peaked with respect to the axis if for each pair of alternatives a, b A with top(vi) b a or a b top(vi) it holds that b i a. Let us also give another, equivalent deﬁnition. An interval I A of an axis is any set such that for all a, b, c A, if we have a, c I and a b c, then b I. Then a vote vi is single-peaked with respect to the axis if and only if for every c A, the top-initial segment {a A : a i c} is an interval of . This deﬁnition in terms of intervals immediately gives a deﬁnition of the single-peaked property for weak orders as well. There are several possible deﬁnitions of single-peakedness for weak orders; the one we use here is often referred to as possible single-peakedness (Lackner 2014), since it is equivalent to saying that there exists a linearisation of the weak order which is single-peaked. We say that two axes and are cyclically equivalent if there is l [m] such that we can write a1 a2 a3 am and al al+1 am a1 al 1. For an axis , we then deﬁne the circle C( ) of to be the set of axes cyclically equivalent to . Any set C of axes that can be written as C = C( ) for some we call a circle. For example, C = {a b c, b c a, c a b} is a circle. Note that cutting a circle C at a point yields an axis C. We say that starts in a A if a b for all b A \ {a}.

Deﬁnition. Let C be a circle. A vote vi is single-peaked on C if there is an axis C such that vi is single-peaked with respect to . A preference proﬁle P is single-peaked on a circle (SPOC) if there exists a circle C such that every vote vi P is single-peaked on C.

Intuitively, a vote vi is single-peaked on C if C can be cut so that vi is single-peaked on the resulting line.

Again let us state another equivalent deﬁnition. An interval I A of a circle C is a set that is an interval of one of the axes C of the circle. Then a vote is single-peaked on a circle C if and only if each top-initial segment {a A : a i c} is an interval of C. Note that the complement A \ I of an interval I of C is again an interval. Thus, a weak order is single-peaked on C if and only if its reverse

= {(b, a) : (a, b) } is also single-peaked on C. A vote is single-caved if its reverse is single-peaked. It follows, then, that mixtures of single-peaked and single-caved orders (on the same axis) are SPOC. However, not all SPOC proﬁles have this form; one such example is the proﬁle shown in Figure 1, where the circle cannot be cut so as to make every preference curve either single-peaked or single-caved.

3 Recognition Algorithms

In this section we design algorithms that decide whether a given proﬁle is single-peaked on some circle, and if so, return a suitable circle C. A matrix M = (aij) with aij {0, 1} has the consecutive ones property if the columns of M can be put into a linear order so that for every row of M, the columns with 1entries form an interval of . The matrix M has the circular ones property if its columns can be arranged in a circle C so that the 1-entries of each row form an interval of C. Given our deﬁnitions in terms of intervals above, it is straightforward to translate a proﬁle P of weak orders into an mn m matrix M so that P is single-peaked [single-peaked on a circle] if and only if M has the consecutive [circular] ones property (Bartholdi III and Trick 1986): Take one column for each alternative, and one row for every top-initial segment of every voter in P; the row is the incidence vector of the segment. Since it is possible to check in linear time whether a matrix A has the consecutive or circular ones property (Booth and Lueker 1976), this gives us an O(m2n) algorithm to recognise proﬁles that are single-peaked on a circle. In the remainder of this section, we design a more explicit algorithm that runs in time O(mn) when the input proﬁle consists of linear orders.1 Suppose P = (v1, . . . , vn) is a proﬁle of linear orders over A, and ﬁx some alternative z A. We will build another proﬁle P = (vu 1 , vl 1, . . . , vu n, vl n) of 2n weak orders by slicing each vote vi at z into an upper part vu i and a lower part vl i. The upper part vu i ranks all alternatives a such that a i z in order of i, and puts all remaining alternatives into a least-preferred indifference class. The lower part vl i ranks all alternatives a such that z i a in reverse order of i, and

1Actually, the algorithm works whenever P contains at least one linear order.

again puts all remaining alternatives into a least-preferred indifference class. Example. Slicing the order a b c z d e f at z yields the upper part a u b u c u z u d u e u f and the lower part f l e l d l z l a l b l c. The notion of slicing reduces SPOC to single-peakedness: Proposition 1. Suppose a proﬁle P of weak orders is obtained by slicing each vote of a proﬁle P of linear orders at some ﬁxed z A. Then P is SPOC if and only if the proﬁle P is single-peaked.

Proof. Suppose P is SPOC on C, and let C be an axis starting in z. Since z is least-preferred by all voters in P , z is not contained in any top-initial segment of any voter in P . However, all top-initial segments of votes in P are intervals of C. Since they do not contain z, they must also be intervals of . Thus, P is single-peaked with respect to . Suppose P is single-peaked with respect to . We show that P is SPOC on C = C( ). Take a top-initial segment S of a vote vi in P; we prove that S is an interval of C. If z S, then S is a top-initial segment of vu i in P . Thus, S is an interval of and so an interval of C. If however z S, then the complement A\S is a top-initial segment of vl i in P , hence an interval of , and so A \ S is an interval of C. But the complement of an interval of a circle is again an interval, and so S is an interval of C. Hence P is SPOC.

Thus, we can use an algorithm that decides whether a proﬁle of weak orders is single-peaked to decide whether a proﬁle of linear orders is SPOC. Next, note that if we select z A to be the alternative that is ranked last by v1 (say), then the proﬁle P obtained by slicing P at z contains a linear order (namely the upper part of v1). Lackner (2014) has given a O(mn) time algorithm that decides whether a proﬁle of weak orders containing at least one linear order is single-peaked. Since P can be constructed from P in time O(mn), by Proposition 1, we obtain the following. Theorem 2. There is an O(mn) time algorithm that decides whether a proﬁle of linear orders is single-peaked on a circle.

4 Characterisation by Forbidden Subproﬁles Ballester and Haeringer (2011) have characterised the domain of single-peaked proﬁles of linear orders by a ﬁnite collection of forbidden subproﬁles. More precisely, they gave forbidden proﬁles with 3 voters and 3 alternatives, and with 2 voters and 4 alternatives such that a proﬁle P is not single-peaked if and only if it is possible to obtain one of their forbidden proﬁles from P by deleting and reordering voters, and deleting and renaming alternatives. A similar characterisation exists for single-crossing proﬁles (Bredereck, Chen, and Woeginger 2013), but no ﬁnite characterisation exists for d-Euclidean proﬁles (Chen, Pruhs, and Woeginger 2015; Peters 2017). Here, we prove that a proﬁle is SPOC unless it contains certain forbidden subproﬁles with 2 voters and 5 alternatives and with 3 voters and 4 alternatives. Let us write B i C to mean that b i c for all b C and c C. Theorem 3. A proﬁle P of linear orders on A is not SPOC if and only if one of the following three cases occurs.

1. There are distinct alternatives a, b, c, d, e A and voters vi and vj in P such that

{a, b} i {c} i {d, e}, {a, e} j {c} j {d, b}.

2. There are distinct alternatives a, b, c, d A and voters vi, vj, and vk in P such that

{a, b} i {c, d}, {a, c} j {b, d}, {a, d} k {b, c}.

3. There are distinct alternatives a, b, c, d A and voters vi, vj, and vk in P such that

{a, b} i {c, d}, {b, c} j {a, d}, {c, a} k {b, d}.

Proof. Sufﬁciency. We prove that if one of the three cases occurs, then P is not SPOC. Since SPOC is closed under alternative deletion, in each case, we may assume wlog that P only involves alternatives mentioned in the forbidden condition. Suppose P was single-peaked on the circle C.

1. Considering top-initial segments of size 2, we see that a must have neighbours b and e in C. Considering top-initial segments of size 3, and taking complements, we see that d must have neighbours b and e in C. But this uniquely determines a circle with a b d e a; yet this circle does not include c, a contradiction. 2. Considering top-initial segments of size 2, we see that a must have neighbours b, c, and d in C. But no vertex of a circle has three neighbours, a contradiction. 3. Since P is single-peaked on C, so is P with every order reversed. But after reversing every order, we are again in case 2: d must have three neighbours.

Necessity. This direction is much more involved, and we leave the details to the full version of this paper. The proof strategy is as follows: if P is not SPOC, then the recognition algorithm of Theorem 2, run on input P, will return a negative answer. We analyse every way the algorithm of Lackner (2014) could answer negatively, and in each case construct a witnessing forbidden structure from among those identiﬁed in the theorem statement.

For the beneﬁt of future research, let us brieﬂy describe how we obtained Theorem 3. We ﬁrst implemented a recognition algorithm for SPOC proﬁles (Theorem 2) and then iterated through all possible proﬁles of certain sizes (up to isomorphism), checking for each whether they were minimal counterexamples: not SPOC, but every proﬁle obtained by deleting a voter or an alternative is SPOC. We analysed the resulting list by hand to come up with the compact representation in Theorem 3. The proof strategy of case analysis of the no -conditions of a recognition algorithm is (implicitly) also the approach used in previous characterisations (Ballester and Haeringer 2011; Bredereck, Chen, and Woeginger 2013; Cornaz, Galand, and Spanjaard 2012).

5 Impossibility Theorems One of the major advantages of the traditional single-peaked domain is the existence of a non-manipulable voting rule on this domain: The well-known median voter procedure sorts voters most preferred alternatives according to the axis and then returns the median alternative a. This alternative is, in fact, a (weak) Condorcet winner: for any other alternative b, a (weak) majority of voters prefers a to b. One might hope to be able to extend this procedure to circles, but this turns out to be impossible: the Gibbard Satterthwaite theorem can be proven using only proﬁles that are single-peaked on a circle. A resolute voting rule f on SPOC proﬁles is a function assigning a single winning alternative to every SPOC proﬁle of linear orders. The rule f is non-dictatorial if there is no ﬁxed voter i such that f always picks i s top alternative. The proﬁle obtained from P by replacing vote vi by v i is denoted by (P i, v i). A voting rule f on SPOC proﬁles is strategyproof if f(P) i f(P i, v i) for all orders v i such that (P i, v i) is still SPOC.

Theorem 4 (Gibbard Satterthwaite Theorem for SPOC). There is no resolute voting rule on SPOC proﬁles that is non-dictatorial, onto, and satisﬁes strategyproofness.

Proof. This follows immediately from the results of Kim and Roush (1980) and Sato (2010), who prove this result for an even more restricted domain consisting only of the 2m orders which traverse the circle clockwise and counter-clockwise starting from every possible alternative.

Note that the SPOC orders used in this proof are unbalanced , in that the mostand least-preferred alternatives are adjacent on the circle for every agent. Still, a similar dictatorship result can be proved even using orders that are Euclidean on a circle, where preferences decrease uniformly in both directions from the peak (Schummer and Vohra 2002). It can also be shown that, with these Euclidean orders, the random dictatorship rule is group-strategyproof (Alon et al. 2010b), and there is an intriguing randomized mechanism that is strategyproof and provides a 3/2-approximation to the egalitarian social welfare (Alon et al. 2010a). Another desirable axiomatic property is participation, which, intuitively, states that no voter can strictly beneﬁt by abstaining from an election. A celebrated result of Moulin (1988) shows that this property is incompatible with Condorcet-consistency, which requires the voting rule to select the Condorcet winner if one exists. This result can also be proven using only SPOC proﬁles.

Theorem 5 (No-Show Paradox for SPOC). For m 4, there is no resolute voting rule on SPOC proﬁles that is Condorcetconsistent and satisﬁes participation.

Proof. For m = 4 alternatives, one can check that the original proof of Moulin (1988) only uses SPOC preference orders; the same holds for the alternative proofs due to Brandt, Geist, and Peters (2016). More care is needed to extend this to m 5; we leave this to the full version of this paper.

As described in the next section, further impossibilities about tournament-based rules can be deduced from Lemma 6.

6 Kemeny s and Young s Rules In this section, we will consider the problem of determining an election winner according to two well-known voting rules, Young s rule and Kemeny s rule, that are NP-hard to evaluate in general (Bartholdi III, Tovey, and Trick 1989; Rothe, Spakowski, and Vogel 2003; Hemaspaandra, Spakowski, and Vogel 2005). We will be interested to see whether these problems can be solved in polynomial time for SPOC proﬁles. We leave the complexity of Dodgson s rule for SPOC proﬁles for future work. Kemeny s rule is a rank aggregation rule: Given a proﬁle P over A, its aim is to produce a consensus ranking over A. Suppose r is a linear order over A. Its Kemeny score is

i N |vi r|, the number of pairwise agreements of r with P. A Kemeny ranking is a linear order r with maximum Kemeny score. While it is NP-hard to ﬁnd a Kemeny ranking (Bartholdi III, Tovey, and Trick 1989), this problem is easy for single-peaked proﬁles whose transitive majority relation is easily seen to give rise to a Kemeny ranking. For SPOC preferences, the situation is less clear: the Condorcet paradox proﬁle (x 1 y 1 z, y 2 z 2 x, z 3 x 3 y) on 3 alternatives is SPOC, so SPOC does not guarantee a transitive majority relation. In fact, SPOC does not guarantee anything at all about the majority relation.

Lemma 6 (Mc Garvey s theorem for SPOC). All (weighted) majority tournaments are inducible by SPOC proﬁles.

Proof. Fix a circle C with x1 x2 xm. For any arc (xi, xj) of the target tournament, consider the following two votes which are single-peaked on C: (subscripts modulo m)

xi+1 xj 1 xi xj xj+1 xi 1 xx 1 xj+1 xi xj xj 1 xi+1

These two votes induce a majority arc xi xj with weight 2, but all other arcs have weight 0. By combining pairs of such votes, any tournament can be obtained. If odd edge weights are desired, start with an arbitrary single order, and then use pairs as above to adjust the weights as needed.

Recall that Kemeny scores only depend on the weighted majority relation of a proﬁle. Since the proﬁles in the proof of Mc Garvey s theorem above can be produced in polynomial time, the hardness of Kemeny in the general case carries over.

Theorem 7. Finding a Kemeny ranking is NP-hard, even for SPOC preferences.

Indeed, by the same argument essentially all negative (axiomatic or computational) results in the sphere of voting rules based on (weighted) tournaments (see Brandt, Brill, and Harrenstein 2016; Fischer, Hudry, and Niedermeier 2016) still hold restricted to SPOC preferences. Young s rule. Given a proﬁle P over A, an alternative c A is a Condorcet winner if for every b A \ {c}, a majority of voters in P strictly prefers c to b. The Young score of an alternative c A is the minimum number of voters that have to be deleted from P so that c becomes a Condorcet winner. Then, Young s rule selects all alternatives with minimum Young score as winners. It is known that Young winners can

be found in polynomial time for single-peaked preferences (Brandt et al. 2015), since in this case Condorcet winners always exists when the number of voters n is odd; and the case with n even is also handled easily. Because SPOC does not guarantee the existence of a Condorcet winner, a different approach is needed. We will use the interpretation of SPOC in terms of intervals of the underlying circle to give a polynomial-time algorithm that calculates the Young score of every alternative; clearly this algorithm can then be run repeatedly to ﬁnd a Young winner. Of course, our algorithm also works for preferences single-peaked on a line; while the algorithm of Brandt et al. (2015) returns only a Young winner, our algorithm can ﬁnd the Young score of any alternative. Note that precise deﬁnitions of Young scores differ slightly: sometimes it is only required that an alternative be made a weak Condorcet winner through voter deletion; our algorithm can be easily adapted for this alternative deﬁnition.

Theorem 8. For SPOC proﬁles, the Young score of an alternative can be computed in O(mn2) time.

Proof. We ﬁx an axis C that starts with the alternative a whose Young score we want to compute; let a b c (b is the candidate right of a, c is the rightmost candidate). We partition voters into two sets: N1 = {i N : b i a} and N2 = N \ N1. Since P is SPOC, for any voter i, the set Ii := {d A : d i a} forms an interval of . Voters in N1 correspond to intervals containing b; voters in N2 correspond to intervals containing c but not b, and to empty intervals. The idea behind our algorithm is that if there are voters i and j with Ii Ij, then it is at least as proﬁtable (for purposes of making a the Condorcet winner) to remove voter j as to remove voter i. Now note that the intervals Ii of voters in N1 are nested by set inclusion, and similarly for voters in N2. Thus, we let N r 1 and N s 2 denote the subsets of N1 and N2 obtained by deleting, respectively, the r and s voters from N1 and N2 that have the r and s largest (with respect to set inclusion) intervals Ii. Because of the nesting property, if there is a way of deleting r and s voters from N1 and N2 that makes a the Condorcet winner, then the deletions giving N r 1 and N s 2 also make a the Condorcet winner. These observations suggest the following simple algorithm: For every pair (r, s) with 0 r |N1| and 0 s |N2|, we check whether a is the Condorcet winner in N r 1 N s 2 . We return a pair (r , s ) with r + s minimum for which this is the case. Then the Young score of a is r + s . If no such pair exists, the Young score of a is inﬁnite. To see that this algorithm can be run in O(mn2) time, we show how to check in O(m) time whether a is the Condorcet winner in N r 1 N s 2 . To do so, we precompute for every x A \ {c}, 0 r |N1|, and 0 s |N2| the numbers

d1 r(x) = |{i N r 1 : a i x}| |{i N r 1 : x i a}|,

d2 s(x) = |{i N s 2 : a i x}| |{i N s 2 : x i a}|.

Note that a is a Condorcet winner in N r 1 N s 2 if and only if for all x A \ {c} it holds that d1 r(x) + d2 s(x) > 0. The quantities d1 r(x) and d2 s(x) can be precomputed in O(mn2) time. Verifying whether d1 r(x)+d2 s(x) > 0 requires constant time and hence O(m) time for every x A \ {c}.

7 Multi-Winner Elections Much recent work has focussed on voting rules that select a committee W A of candidates, where |W| = k has some desired size k. A particularly inﬂuential rule for this task is due to Chamberlin and Courant (1983). According to their rule, each voter i is represented by their favourite (highestranked) alternative in W, say ci W. Voter i then derives her Borda score (i.e., position counting from the bottom) of ci in her ranking as her utility. The Chamberlin Courant rule selects a committee of size k that maximises total utility. By replacing Borda scores by other scoring vectors, we obtain a whole family of rules. Finding a winning committee under the Chamberlin Courant rule is known to be NP-hard for Borda scores (Lu and Boutilier 2011); however, this problem can be solved by dynamic programming in polynomial time if the input proﬁle is single-peaked (Betzler, Slinko, and Uhlmann 2013). An alternative method for single-peaked preferences proceeds via integer programming with totally unimodular constraints (Peters 2016). This method can be extended to also work for SPOC using a technique described in a useful survey by Dom (2009, Sec 4.1.4). Theorem 9. For SPOC proﬁles, a winning committee for the Chamberlin Courant rule can be found in polynomial time for any scoring vector.

Proof. Let P be a SPOC preference proﬁle, and k the target committee size. Our algorithm adapts the approach of Peters (2016), where the following integer-programming formulation for calculating an optimal Chamberlin Courant committee is introduced:

r [m] wr xi,r (CC-IP)

c C yc = k (S)

c : ranki(c) r yc for i N, r [m] (Pi,r)

xi,r {0, 1} for i N, r [m]

yc {0, 1} for c C

Here, (S) and (Pi,r) are labels for the constraints. In the IP, the binary variables yc encode the k committee members, and in optimum we have xi,r = 1 if and only if there is a committee member c who is ranked in position r or higher by voter i. The coefﬁcients wr in the objective function determine the scoring vector used; choosing wr = 1 for all r yields Borda scores. Using the algorithms from Section 3, ﬁnd a circle C such that P is single-peaked on C, and take some C arbitrarily. We now split constraints of form (Pi,r) into two types. Set Ti,r = {c : ranki(c) r} to be the rth top-initial segment of i. Deﬁne

R1 = {(Pi,r) : Ti,r is an interval of }, R2 = {(Pi,r) : C \ Ti,r is an interval of } \ R1.

Since P is single-peaked on C, every Ti,r is an interval of C. Thus, either Ti,r or C \Ti,r is an interval of . It follows that

R1 and R2 partition the set of all the constraints of type (Pi,r). We now modify (CC-IP) by subtracting the constraint (S) (in the form 0 =

c C yc k) from each constraint (Pi,r) R2. In this way, we obtain the following constraints:

c Ti,r yc for (Pi,r) R1 (P i,r)

c Ti,r yc + k for (Pi,r) R2 (P i,r)

We write (CC-IP ) for the program obtained by replacing (Pi,r) by (P i,r) in (CC-IP). It is easy to see that a solution vector (x, y) is feasible in (CC-IP) if and only if it is feasible in (CC-IP ), since both systems include the constraint

c C yc = k. Hence the two formulations are equivalent. We now claim that the constraint matrix of (CC-IP ) is totally unimodular, and thus this integer program can be solved in polynomial time by solving its LP relaxation (Conforti et al. 2014, p. 183). To see this, consider ﬁrst the constraint matrix Ay of only the variables {yc : c C}. If we order its columns in the order given by , then a row corresponding to a constraint in R1 consists of a block of consecutive 1s surrounded by 0s, and a constraint from R2 consists of a block of consecutive 1s surrounded by 0s. Constraint (S) is a row consisting only of 1s. Hence Ay is an interval matrix and thus totally unimodular (Schrijver 1998, Sec 19.3 4). To obtain the full constraint matrix Ax,y of (CC-IP ), we need to add columns to Ay corresponding to xi,r-variables. But each such variable occurs in exactly 1 constraint, and thus each column to be added contains just a single 1, and 0s otherwise. Since totally unimodular matrices are closed under appending (positive or negative) unit columns (Schrijver 1998, Sec 19.4), we see that Ax,y is also totally unimodular.

The other algorithms via total unimodularity discussed by Peters (2016) can be adapted using the same kind of argument; in particular this gives a polynomial-time algorithm for egalitarian Chamberlin Courant, for Proportional Approval Voting (PAV), and certain OWA-based rules.

8 Discussion and Open Problems Our results show that restricted preference domains that behave unfavourably in terms of axiomatic properties might still be very useful for algorithmic purposes. Indeed, our algorithm for Young s rule demonstrates that it is possible to move to a larger class than single-peaked preferences while maintaining polynomial-time runtime bounds. Thus, our ﬁndings can be seen as a challenge to established algorithmic results based on restricted preferences: to which degree can their application domain be extended without resorting to superpolynomial algorithms? A speciﬁc open problem: what is the complexity of computing Dodgson scores for SPOC proﬁles? This seems to be open even for single-peaked proﬁles. Our deﬁnition of SPOC is not the only sensible deﬁnition. One alternative deﬁnition that would ﬁt into the generalised notion of single-peakedness introduced by Nehring and Puppe (2007) is based on shortest paths: it requires that for every voter i and for every alternative x, there is a shortest

path between top(i) and x along which i s preferences are decreasing. (Without the word shortest this is equivalent to SPOC.) The impact of this alternative deﬁnition is that every voter s least-preferred alternative needs to be antipodal to the voter s peak; this is strictly more restrictive than SPOC. It would be interesting to see whether this smaller domain allows for a wider range of positive results than SPOC. Another direction for future work would be to extend the SPOC concept to two (and more) dimensions preferences single-peaked on a sphere but this may be difﬁcult since little is known even about extensions of single-peakedness on a line to two or more dimensions (see Sui et al. 2013).

Acknowledgements We thank the anonymous reviewers for useful suggestions and pointing out a mistake in one of our algorithms. We thank Edith Elkind for helpful discussions. This work was supported by the European Research Council (ERC) under grant number 639945 (ACCORD). Dominik Peters is supported by EPSRC.

References Alon, N.; Feldman, M.; Procaccia, A. D.; and Tennenholtz, M. 2010a. Strategyproof approximation of the minimax on networks. Mathematics of Operations Research 35(3):513 526. Alon, N.; Feldman, M.; Procaccia, A. D.; and Tennenholtz, M. 2010b. Walking in circles. Discrete Mathematics 310(23):3432 3435. Ballester, M. A., and Haeringer, G. 2011. A characterization of the single-peaked domain. Social Choice and Welfare 36(2):305 322. Bartholdi III, J., and Trick, M. A. 1986. Stable matching with preferences derived from a psychological model. Operation Research Letters 5(4):165 169. Bartholdi III, J.; Tovey, C. A.; and Trick, M. A. 1989. Voting schemes for which it can be difﬁcult to tell who won the election. Social Choice and Welfare 6(2):157 165. 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. The Journal of Political Economy 56(1):23 34. Booth, K. S., and Lueker, G. S. 1976. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences 13(3):335 379. Brandt, F.; Brill, M.; Hemaspaandra, E.; and Hemaspaandra, L. A. 2015. Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates. Journal of Artiﬁcial Intelligence Research 53:439 496. Brandt, F.; Brill, M.; and Harrenstein, P. 2016. Tournament solutions. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A., eds., Handbook of Computational Social Choice. Cambridge University Press. Brandt, F.; Geist, C.; and Peters, D. 2016. Optimal bounds for the no-show paradox via SAT solving. In AAMAS 16, 314 322. Bredereck, R.; Chen, J.; and Woeginger, G. J. 2013. A characterization of the single-crossing domain. Social Choice and Welfare 41(4):989 998. Chamberlin, B., and Courant, P. 1983. Representative deliberations and representative decisions: Proportional representation and the Borda rule. American Political Science Review 77(3):718 733.

Chen, J.; Pruhs, K.; and Woeginger, G. J. 2015. The onedimensional Euclidean domain: Finitely many obstructions are not enough. ar Xiv preprint ar Xiv:1506.03838. Conforti, M.; Cornu ejols, G.; and Zambelli, G. 2014. Integer programming, volume 271. Springer. Cornaz, D.; Galand, L.; and Spanjaard, O. 2012. Bounded singlepeaked width and proportional representation. In ECAI 12, 270 275. Demange, G. 1982. Single-peaked orders on a tree. Mathematical Social Sciences 3(4):389 396. Dom, M. 2009. Algorithmic aspects of the consecutive-ones property. Bulletin of the European Association for Theoretical Computer Science 98:27 59. Elkind, E.; Lackner, M.; and Peters, D. 2016. Preference restrictions in computational social choice: Recent progress. In IJCAI 16, 4062 4065. Fischer, F.; Hudry, O.; and Niedermeier, R. 2016. Weighted tournament solutions. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A., eds., Handbook of Computational Social Choice. Cambridge University Press. Hemaspaandra, E.; Spakowski, H.; and Vogel, J. 2005. The complexity of Kemeny elections. Theoretical Computer Science 349(3):382 391. Kim, K. H., and Roush, F. W. 1980. Special domains and nonmanipulability. Mathematical Social Sciences 1(1):85 92. Lackner, M. 2014. Incomplete preferences in single-peaked electorates. In AAAI 14, 742 748. Lu, T., and Boutilier, C. 2011. Budgeted social choice: From consensus to personalized decision making. In IJCAI 11, 280 286. Mc Garvey, D. C. 1953. A theorem on the construction of voting paradoxes. Econometrica 21(4):608 610. Moulin, H. 1988. Condorcet s principle implies the no show paradox. Journal of Economic Theory 45(1):53 64. Moulin, H. 1991. Axioms of Cooperative Decision Making. Cambridge University Press. Nehring, K., and Puppe, C. 2007. The structure of strategy-proof social choice, Part I: General characterization and possibility results on median spaces. Journal of Economic Theory 135(1):269 305. Peters, D., and Elkind, E. 2016. Preferences single-peaked on nice trees. In AAAI 16, 594 600. Peters, D. 2016. Single-peakedness and total unimodularity: Efﬁciently solve voting problems without even trying. ar Xiv preprint ar Xiv:1609.03537. Peters, D. 2017. Recognising multidimensional Euclidean preferences. In AAAI 17. ar Xiv preprint ar Xiv:1602.08109. Rothe, J.; Spakowski, H.; and Vogel, J. 2003. Exact complexity of the winner problem for Young elections. Theory of Computing Systems 36(4):375 386. Sato, S. 2010. Circular domains. Review of Economic Design 14(3-4):331 342. Schrijver, A. 1998. Theory of linear and integer programming. John Wiley & Sons. Schummer, J., and Vohra, R. V. 2002. Strategy-proof location on a network. Journal of Economic Theory 104(2):405 428. Sui, X.; Francois-Nienaber, A.; and Boutilier, C. 2013. Multidimensional single-peaked consistency and its approximations. In IJCAI 13, 375 382. Yu, L.; Chan, H.; and Elkind, E. 2013. Multiwinner elections under preferences that are single-peaked on a tree. In IJCAI 13, 425 431.