# preferences_singlepeaked_on_a_circle__31716653.pdf

Journal of Artiﬁcial Intelligence Research 68 (2020) 463-502 Submitted 09/2019; published 06/2020

Preferences Single-Peaked on a Circle

Dominik Peters dominikp@cs.cmu.edu Carnegie Mellon University Computer Science Department 5000 Forbes Avenue, Pittsburgh, PA 15213, USA

Martin Lackner lackner@dbai.tuwien.ac.at TU Wien Databases and Artiﬁcial Intelligence Group Favoritenstraße 9-11, 1040 Vienna, Austria

We introduce the domain of preferences that are single-peaked on a circle, which is a generalization of the well-studied single-peaked domain. This preference restriction is useful, e.g., for scheduling decisions, certain facility location problems, 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 polynomial-time computable on this domain. In particular, we prove that Proportional Approval Voting can be computed in polynomial time for proﬁles that are single-peaked on a circle. In contrast, Kemeny s rule remains hard to evaluate, and several impossibility results from social choice theory can be proved using only proﬁles in this domain.

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, & Peters, 2016, 2017). For example, winner determination problems that are computationally hard in the general case tend to be easy when restricted to single-peaked proﬁles (Betzler, Slinko, & Uhlmann, 2013; Brandt, Brill, Hemaspaandra, & Hemaspaandra, 2015), and the single-peaked domain guarantees the existence of Condorcet winners

c 2020 AI Access Foundation. All rights reserved.

Peters & Lackner

a b c d e f g h

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

as well as transitivity of the majority relation and thus admits a strategyproof voting rule (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 one-dimensional, 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, & Elkind, 2013; Peters & 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 diﬀer 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 eﬃ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.

1.1 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 (also known as single-dipped) on the line, is still single-peaked on the same circle. Thus, our new preference restriction

Preferences Single-Peaked on a Circle

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. Indeed, an analysis of Tangian (2020) shows that the parties participating in the 2017 Bundestag elections in Germany can be sensibly aligned on a left-right axis if this axis is rolled into a horsehoe-like form, i.e., in a circular arrangement. On a lighter note, 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, diﬀerent 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 oﬃ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.

1.2 Contributions

The main contributions of this paper can be summarised as follows:

We formally deﬁne single-peakedness on circles and immediately extend this deﬁnition to preferences with ties, and to dichotomous (approval) preferences. Thus, our proposed domain is strictly larger than the class of possibly single-peaked preferences (Lackner, 2014; Fitzsimmons & Lackner, 2020) and candidate interval dichotomous preferences (Faliszewski, Hemaspaandra, Hemaspaandra, & Rothe, 2011; Elkind & Lackner, 2015).

We show that it is possible to eﬃ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 lineartime 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 famous im-

Peters & Lackner

possibility result by Gibbard and Satterthwaite) 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 eﬃciently computed if preferences are single-peaked on a circle; this algorithm also improves upon the state-ofthe-art when it comes to preferences single-peaked on a line. In contrast, we show that Kemeny s rule is NP-hard to compute even in this restricted domain.

Finally, we show that several multi-winner voting rules are eﬃciently computable in our restricted case, speciﬁcally all that are included in the large class of so-called OWAbased rules. This class includes, e.g., the Chamberlin Courant rule and Proportional Approval Voting (PAV). It is noteworthy that some of these algorithmic results have not yet been established even for single-peaked proﬁles (such as the one for PAV). This general result relies on using total unimodularity and integer programming.

1.3 Outline of the Paper

In Section 2, we introduce and deﬁne single-peakedness on a circle. In Section 3, we discuss the algorithmic recognition of these preferences; proof details are delegated to the appendix, Section A. Building on these results, we prove a characterization of this preference class in Section 4, with proof details in the appendix, Section B. We then take the perspective of social choice theory in Section 5 and revisit classical impossibility results. The algorithmic usefulness of preferences that are single-peaked on a circle is the focus of the following two sections: Section 6 for the single-winner rules Kemeny and Young, and Section 7 for several multi-winner rules including Chamberlin Courant and Proportional Approval Voting. Open problems are discussed in Section 8.

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 indiﬀerence 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 one-dimensional 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

Preferences Single-Peaked on a Circle

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 stated above is sometimes known as possible single-peakedness (Lackner, 2014; Fitzsimmons & Lackner, 2020), 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. A weak order is dichotomous if there is a partition of A into sets A1 and A2 such that a b if and only if a A1 and b A2. A voter whose preferences are given by is said to approve the alternatives in A1. Note that, according to our deﬁnition, a proﬁle of dichotomous (approval) preferences is SPOC if and only if there is a circle C such that every voter s approval set is an interval of C.

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.

0 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 1 0

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 1-entries form an interval of . The matrix shown on the right is an example. 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

Peters & Lackner

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 & 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 & 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 The algorithm works by reducing the SPOC recognition problem for linear orders to the recognition problem of single-peaked proﬁles for weak orders, in such a way that we can apply an algorithm of Fitzsimmons and Lackner (2020). 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 indiﬀerence class. The lower part vl i ranks all alternatives a such that z i a in reverse order of i, and again puts all remaining alternatives into a least-preferred indiﬀerence 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 leastpreferred 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 singlepeaked 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). Fitzsimmons and Lackner (2020) give an O(mn) time algorithm that decides whether a proﬁle of weak orders

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

Preferences Single-Peaked on a Circle

containing at least one linear order is single-peaked. In Appendix A, for completeness, we include a description of the algorithm of Fitzsimmons and Lackner (2020), and the relevant parts of its correctnes proof. 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, & Woeginger, 2013), but no ﬁnite characterisation exists for d-Euclidean proﬁles (Chen, Pruhs, & Woeginger, 2017; 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. For sets B, C A of 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. Suﬃ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.

Peters & Lackner

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 the full proof appears in Appendix B. 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 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 & Haeringer, 2011; Bredereck et al., 2013; Cornaz, Galand, & 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. It is onto if for every alternative x, there exists a SPOC proﬁle P with f(P) = x. 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.

Preferences Single-Peaked on a Circle

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 & Vohra, 2002). It can also be shown that, with these Euclidean orders, the random dictatorship rule is group-strategyproof (Alon, Feldman, Procaccia, & Tennenholtz, 2010b), and there is an intriguing randomised mechanism that is strategyproof and provides a 3/2-approximation to the egalitarian social welfare (Alon, Feldman, Procaccia, & Tennenholtz, 2010a).

Another interesting subdomain that we mentioned in the introduction is the combination of single-peaked and single-dipped (single-caved) orders with respect to the same underlying axis. This subdomain is particularly useful to model facility location, where the public facility may be perceived as a good or bad by diﬀerent voters. Achuthankutty and Roy (2018) prove that the Gibbard Satterthwaite Theorem holds for this subdomain. Alcalde Unzu and Vorsatz (2018) also consider this kind of facility location problem, with the additional assumption that voters pivotal points (their peak or dip) are public knowledge. For this model, they show that strategy-proof facility location mechanisms exist. When assuming Euclidean preferences that may be single-peaked or single-dipped, Feigenbaum and Sethuraman (2015) and Zou and Li (2015) also ﬁnd strategy-proof mechanisms.

We conjecture that many other impossibility theorems from social choice theory will continue to apply after restricting to SPOC proﬁles. As an example, we will prove a celebrated result of Moulin (1988) in the SPOC context. He showed that every Condorcet-consistent voting rule fails participation. A voting rule f is Condorcet-consistent if for every proﬁle P that admits a Condorcet winner a, we have f(P) = a. Participation states that no voter can strictly beneﬁt by abstaining from an election. Formally, f satisﬁes participation if for all proﬁles P, and all linear orders , we have f(P + ) f(P), where P + denotes the proﬁle obtained from P by adding a voter with preferences given by . We will also write P + k for the proﬁle obtained from P by adding k voters with preferences .

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

The proof is a straightforward adaptation of the proofs of Moulin (1988) and Brandt, Geist, and Peters (2017): most of the proﬁles in those proofs are SPOC. Somewhat more care needs to be taken while lifting the impossibility for m = 4 to m > 4 while maintaining the SPOC property.

Proof of Theorem 5. Let m 4 and write A = {a1, . . . , am 3, b, c, d}. Consider the circle C = a1 am 3 b c d a1. In the following, for brevity, we write abcd for the

Peters & Lackner

linear order a1 am 3 b c d. The following proﬁles are all SPOC on C:

P0 = 2 abcd + 3 bcd a + 3 d abc + 2 cd ab

P1 = 2 abdc + 2 abcd + 3 bcd a + 3 d abc + 2 cd ab

P2 = 2 abcd + 3 bcd a + 3 d abc + 2 cd ab + 2 cdb a

P3 = 2 abdc + 2 abcd + 3 bcd a

P4 = 2 abdc + 2 abcd + 3 d abc + 2 cd ab

P5 = 2 abcd + 3 bcd a + 2 cd ab + 2 cdb a

P6 = 3 d abc + 2 cd ab + 2 cdb a

Let f be a voting rule deﬁned on SPOC proﬁles satisfying Condorcet-consistency and participation. By Condorcet-consistency, we have f(P3) = a1, f(P4) = d, f(P5) = b, and f(P6) = c. Write A a = {a1, . . . , am 3}. Consider P0, and assume for now that f(P0) A a {b}. Then, since f satisﬁes participation, also f(P1) A a {b}. By Condorcet-consistency, f(P3) = a1. Since P1 can be obtained from P3 by adding d abc and cd ab voters, participation implies that f(P1) {c, d, a1}. Hence f(P1) = a1. But, by Condorcet-consistency, f(P4) = d; and since P1 can be obtained from P4 by adding bcd a voters, participation implies f(P1) {b, c, d}, a contradiction. Since we arrived at a contradiction, we must have f(P0) A a {b}, and so f(P0) {c, d}. Thus, by participation, also f(P2) {c, d}. By Condorcet-consistency, f(P5) = b, and thus by participation, f(P2) A a {d, b}, and thus f(P2) = d. But by Condorcet-consistency, f(P6) = c and thus by participation, f(P2) A a {b, c}, a contradiction. Since either case leads to a contradiction, there can be no voting rule f with the desired properties.

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, & Trick, 1989; Rothe, Spakowski, & Vogel, 2003; Hemaspaandra, Spakowski, & 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 X

i N |{(x, y) A A : x i y and x r y}|,

the number of pairwise agreements of r with P. A Kemeny ranking is a linear order r with maximum Kemeny score. (Equivalently, one can deﬁne a Kemeny ranking as a

Preferences Single-Peaked on a Circle

linear order that minimises the number of pairwise disagreements.) While it is NP-hard to ﬁnd a Kemeny ranking (Bartholdi III et al., 1989), this problem is easy for singlepeaked 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, as we now show, SPOC does not guarantee anything at all about the majority relation, which will imply that the SPOC restriction does not make the problem of computing Kemeny rankings easier. If P is a proﬁle of linear orders, and x, y A, we write nx,y = |i N : x i y| for the number of voters who prefer x to y. The majority margin of x over y is mx,y = nx,y ny,x. Note that mx,y > 0 if and only if a strict majority of voters prefer x to y. Note that mx,y Z has the same parity as |N| (since mx,y = nx,y (n nx,y) = 2nx,y n), and so either all majority margins are even, or all are odd. The collection (mx,y)x,y A is known as a weighted majority tournament. Mc Garvey s (1953) theorem (and its reﬁnement by Debord, 1987) states that any such collection of integers, all of the same parity, is induced as the weighted majority tournament of some proﬁle P of linear orders. We can show that the same result holds when we additionally require that P is SPOC.

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 xi, xj A consider the proﬁle Pxi,xj consisting of the following two votes which are single-peaked on C, with subscripts taken modulo m:

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

The proﬁle Pxi,xj induces a majority tournament with all margins 0 except that mxi,xj = mxj,xi = 2. Suppose we are given a collection (mx,y)x,y A of even integers. Then consider the proﬁle P which contains, for each pair xi, xj with mxi,xj > 0, exactly mxi,xj/2 copies of the proﬁle Pxi,xj. Then P induces (mx,y)x,y A, and P is SPOC on C. Suppose we are given a collection (mx,y)x,y A of odd integers. Then consider the proﬁle P containing one voter with x1 xm, and also for each pair xi, xj with i < j, if mxi,xj > 0 then (mxi,xj 1)/2 copies of Pxi,xj, and if mxi,xj < 0 then (mxi,xj + 1)/2 copies of Pxj,xi. Then P induces (mx,y)x,y A, and P is SPOC on C.

Now, the Kemeny score of a ranking r as deﬁned above is clearly equal to P x,y A:x ry nx,y. Since nx,y = (mx,y + n)/2, we see that the Kemeny score is a function of the weighted majority tournament 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. Given a SPOC proﬁle of linear orders and a number k, it is NP-complete to decide whether there exists a linear order with Kemeny score at least k.

Peters & Lackner

Proof. Containment in NP is clear. We reduce from the unconstrained problem of deciding whether in a given proﬁle P, there exists a linear order with Kemeny score at least k, which is known to be NP-complete (Bartholdi III et al., 1989). Given such an instance, use the construction of Lemma 6 to produce a SPOC proﬁle P such that the majority margins for any pair x, y of alternatives are the same in P and P . Write n for the number of voters in P, and n for the number of voters in P . Let r be some linear order. Its Kemeny score in P is P x,y A:x ry n P x,y = P x,y A:x ry(mx,y + n )/2 = P x,y A:x ry n P x,y + m 2 (n n)/2.

Hence, there exists a linear order with Kemeny score r + m 2 (n n)/2 in P if and only there exists a linear order with Kemeny score r in P.

For the same reason, essentially all negative (axiomatic or computational) results about voting rules based on (weighted) tournaments (see Brandt, Brill, & Harrenstein, 2016; Fischer, Hudry, & 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 diﬀerent 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 given alternative.2 Note that precise deﬁnitions of Young scores diﬀer 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. Figure 2 illustrates the situation: For each voter i, an arc indicates the set Ii. The red arcs on the right belong to voters from N1, and the blue arcs on the left belong to voters from N2.

2. Fitzsimmons and Hemaspaandra (2020, Theorem 10) give an algorithm for calculating Dodgson scores in single-peaked proﬁles.

Preferences Single-Peaked on a Circle

Figure 2: Illlustration of the proof of Theorem 8, for a proﬁle with eight voters. For each voter, an arc indicates the set of alternatives preferred to a.

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 studied voting rules that select not a single winner, but a committee W A of candidates, where |W| = k has some desired size k (see, e.g., a recent survey by Faliszewski, Skowron, Slinko, & Talmon, 2017). Depending on the context, we may wish this committee to have diﬀerent properties. For example, we may aim for a representative committee in which as many voters as possible have a good representative, or we may aim

Peters & Lackner

for a proportional committee in which subgroups of the voters are represented by committee members in proportion to the subgroup size. Many of the commonly-studied multi-winner rules optimise an objective function over the set of all committees. Unsurprisingly, many of them are NP-hard to evaluate. In this section, we show that several popular rules can be evaluated in polynomial time when preferences are single-peaked on a circle. Chamberlin and Courant (1983) introduced a rule that aims for a committee that represents as many voters as well as possible. It is usually deﬁned for proﬁles of linear orders. According to this rule, each voter i is represented by i s favourite (highest-ranked) alternative in W; suppose this is ci W. Then, we take the utility of voter i to be the Borda score (i.e., position counting from the bottom) of ci in i s ranking. The Chamberlin Courant rule selects a committee of size k that maximises the sum of voter utilities. By replacing Borda scores by other scoring vectors, we obtain a whole family of rules. The class of OWA-based rules, as deﬁned below, is a further generalization of this idea. Finding a winning committee under the Chamberlin Courant rule is known to be NPhard for Borda scores (Lu & Boutilier, 2011). Betzler et al. (2013) showed that this problem becomes easy when the input proﬁle is single-peaked. Their algorithm starts by running a recognition algorithm for single-peakedness on the input to obtain an underlying axis on which the proﬁle is single-peaked. Then, they run a dynamic programming algorithm which constructs an optimal committee. Roughly, this dynamic program successively considers left preﬁxes of the axis , and constructs an optimal committee using only candidates from the preﬁx. Unfortunately, it is unclear how to extend this approach to preferences singlepeaked on a circle, since a circle does not have a left endpoint where we could start the dynamic program. Thus, we follow a diﬀerent approach: We design an integer linear programming (ILP) formulation encoding the winner determination problem. We then show that the matrix of coeﬃcients appearing in the constraints of this ILP is totally unimodular whenever the input proﬁle is SPOC. A well-known result states that ILPs with totally unimodular constraint matrices are optimally solved by their LP relaxations (Hoﬀman & Kruskal, 1956), and can thus be solved in polynomial time. As a preview, for the Chamberlin Courant rule based on Borda scores, our general ILP formulation looks as follows:

r [m] xi,r (CC-ILP)

subject to X

c C yc = k (2)

c : rank(c) r yc for i N, r [m] (3)

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

yc {0, 1} for c C

This formulation has one binary variable yc for each candidate c C, indicating whether candidate c is part of the committee. Constraint (2) requires that the committee contains

Preferences Single-Peaked on a Circle

exactly k candidates. The binary variables xi,r indicate whether voter i N ranks some committee member in rank r or better; this interpretation is implemented by the constraints (3) together with the fact that the program is maximising the sum of all xi,r. Note that if the best candidate for voter i N in the committee described by the variables (yc)c C is in rank 4, say, then the program will set xi,1 = = xi,3 = 0 and xi,4 = = xi,m = 1. Thus, the contribution of voter i to the objective function is m 4 + 1, which is the Borda score (plus one) of i s representative. Thus, the objective function of this program correctly encodes Chamberlin Courant. Our approach works not only for the Chamberlin Courant rule, but for a large class of rules introduced by Skowron, Faliszewski, and Lang (2016), called OWA-based rules (OWA stands for ordered weighted average). An example of such a rule is Chamberlin Courant, but deﬁned so that voter i s utility is the sum of the Borda scores of i s best two members of the committee. Let us formally describe this class of rules. We will give a deﬁnition that works for weak order inputs, and so this class includes rules that work for linear order proﬁles, and for approval proﬁles. Given a preference proﬁle, as a ﬁrst step the rule converts preferences into numerical scores, using a positional scoring system. Suppose that is a weak order over A. Then we can uniquely partition A = A1 Aq into disjoint non-empty sets such that A1 Aq and such that a b for all a, b Ar for r [q]. The sets Ar are called the indiﬀerence classes of the weak order . Now, for an alternative a A, if a Ar, the rank of a in is r, and we write rank (a) = r. Thus, the alternatives with rank 1 are the most-preferred alternatives. If we are given a proﬁle P, then we write ranki(a) for i N and a A for the rank of a in voter i s preferences. A score vector is a vector s Rm such that s1 s2 sm. Common examples are s = (m 1, m 2, . . . , 0) for Borda scores and s = (1, 0, . . . , 0) for plurality scores. Given such a score vector s, we say that voter i N assigns the score sranki(a) to alternative a A, and we write s(i, a) = sranki(a). This is the standard deﬁnition when preferences are given by linear orders.3 If a voter submits an approval ballot, and we use plurality scores, then the voter assigns score 1 to all approved alternatives and score 0 to the remaining alternatives. Note that whenever a i b then s(i, a) s(i, b). The utility a voter derives from a committee under an OWA-based rule will be a linear combination of the scores assigned to the candidates in the committee, and these values are calculated using an OWA operator. A weight vector α Rk deﬁnes an ordered weighted average (OWA) operator as follows: Given any vector x Rk, ﬁrst sort the entries of x into non-increasing order, so that xσ(1) . . . xσ(k); second, apply the weights: the ordered weighted average of x with weights α is given by α(x) := Pk i=1 αixσ(i). For example, if α = (1, 0, . . . , 0), then α(x) = xσ(1) = maxi [k] xi, so that this operator returns the maximum of the vector x. Alternatively, if α = (1, 1, . . . , 1), then α(x) = Pk i=1 xσ(i) = Pk i=1 xi, so that this operator gives the sum of the numbers in x.

3. Often, it will be unnatural to use the same scoring system both for linear orders and other weak orders (such as approval ballots). For example, one might adjust the deﬁnition of Borda scores when weak orders are submitted (Chebotarev & Shamis, 1998). It is straightforward to adjust our algorithm to allow for diﬀerent scoring systems for diﬀerent order types, or even for diﬀerent scoring systems for each agent; all that s needed is to adjust the coeﬃcients in the objective function of the ILP. Often, it will also be natural to restrict the input of the rule to just linear orders, or to just approval ballots. We have chosen the current formulation for ease of presentation.

Peters & Lackner

Given a proﬁle P, a scoring vector s, and an OWA operator α, we deﬁne the utility of a committee W = {c1, . . . , ck} as

U(s, α, W) = X

i N α(s(i, c1), . . . , s(i, ck)).

Then the OWA-based multi-winner rule based on s and α outputs a committee W of size k for which U(s, α, W) is maximum. For example, choosing α = (1, 0, . . . , 0) and s = (m 1, m 2, . . . , 0) (Borda scores) gives us the Chamberlin Courant rule, where each voter derives as utility the score of their favourite committee member. Choosing α = (1, 1, 0, . . . , 0) gives us the analogue of Chamberlin Courant mentioned above, where voters obtain as utility the sum of the scores of their favourite two members of the committee (this rule is sometimes known as 2-Borda (Faliszewski, Skowron, Slinko, & Talmon, 2017)). When we restrict our attention on dichotomous weak orders, then the OWA-based rule applied to proﬁles with approval votes with α = (1, 1

2, . . . , 1

k) and scores s = (1, 0) gives us Proportional Approval Voting (PAV), a voting rule that has received much attention in the recent literature (Aziz, Brill, Conitzer, Elkind, Freeman, & Walsh, 2017; Janson, 2016; Lackner & Skowron, 2018). Deﬁning it more explicitly, PAV returns the committee W C with |W| = k maximising P i N 1 + 1

2 + + 1 |Ai W|, where Ai is the set of candidates that voter i approves. For the special case of PAV, the ILP formulation we will give for general OWA-based rules looks as follows:

1 ℓ xi,ℓ (PAV-ILP)

subject to X

c C yc = k (2)

ℓ [k] xi,ℓ X

c Ai yc for i N (3)

xi,ℓ {0, 1} for i N, ℓ [k] (4)

yc {0, 1} for c C

Again, this formulation has one binary variable yc for each candidate c C. The binary variables xi,ℓindicate whether voter i N approves of at least ℓcandidates in the committee; this interpretation is implemented by the constraints (3) together with the fact that the coeﬃcients of xi,ℓin the objective function decrease with ℓ. Our most general ILP formulation will merge the ideas behind (PAV-ILP) and (CC-ILP). Our polynomial-time result will only work for non-increasing OWA vectors α with α1 αk. For example, this excludes the rule where voters are represented by their least-favourite committee member, or by their median committee member. While such rules may be sensible in some settings (Skowron, 2015), this restriction seems mild for most contexts. Next, let us give an overview about total unimodularity. A matrix A = (aij)ij Zm n

with aij { 1, 0, 1} is called totally unimodular if every square submatrix B of A has

Preferences Single-Peaked on a Circle

det B { 1, 0, 1}. (The rows and columns of B need not occur contiguously in A.) The following results are well-known. Proofs and much more about their theory can be found in the textbook by Schrijver (1998).

Theorem 9 (see Schrijver, 1998, Theorem 19.1). Suppose A Zm n is a totally unimodular matrix, b Zm is an integral vector of right-hand sides, and c Qn is an objective vector. Then the linear program max c T x subject to Ax b (LP)

has an integral optimum solution, which is a vertex of the polyhedron {x : Ax b}. Thus, the integer linear program

max c T x subject to Ax b, x Zn (ILP)

is solved optimally by its linear programming relaxation (LP).

An optimum solution to (ILP) can be found in polynomial time (Maurras, Truemper, & Akg ul, 1981; Tardos, 1986). We will now state some elementary results about totally unimodular matrices, which allows us to build new matrices from old.

Proposition 10 (see Schrijver, 1998, chapter 19). If A is totally unimodular, then so is

1. its transpose AT ,

2. the matrix [A | A] obtained from A by appending the negated columns of A,

3. the matrix [A | I] where I is the identity matrix,

4. any matrix obtained from A through permuting or deleting rows or columns.

In particular, from (3) and (4) it follows that appending a unit column (0, . . . , 1, . . . , 0)T

will not destroy total unimodularity. Further, using these transformations, we can see that Theorem 9 remains true even if we add to (P) constraints giving lower and upper bounds to some variables, if we replace some of the inequality constraints by equality constraints, or change the direction of an inequality. Recall that a binary matrix A = (aij) {0, 1}m n has the consecutive ones property if its columns can be permuted such that the 1-entries of each row form an interval. The key result that will allow us to connect single-peaked preferences to total unimodularity is as follows:

Proposition 11 (see Schrijver, 1998, page 279). Every binary matrix with the consecutive ones property is totally unimodular.

We remark that by a celebrated result of Seymour (1980), it is possible to decide in polynomial time whether a given matrix is totally unimodular, though we do not use this fact. We are now ready to prove our main result, that OWA-based rules are easy to compute for SPOC proﬁles.

Peters & Lackner

Theorem 12. Given a SPOC proﬁle P, and an OWA-based rule speciﬁed by a scoring vector s and a non-increasing OWA operator α, a winning committee can be found in polynomial time.

Proof. We begin by showing the result for single-peaked proﬁles, and later show how to modify the argument for SPOC proﬁles. Let P be a preference proﬁle, and let k be the target committee size. Consider the following integer linear program, whose optimal solutions correspond to winning committees under the OWA-based rule with operator α and scoring vector s. In the program, we write s m = sm, and for each r = 1, . . . , m 1, we write s r = sr sr+1 0. Thus, for every r [m], we have that sr = Pm p=r s p.

r [m] αℓ s r xi,ℓ,r (OWA-ILP)

subject to X

c A yc = k (2)

ℓ [k] xi,ℓ,r X

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

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

yc {0, 1} for c A

Every feasible solution ((xi,ℓ,r)i,ℓ,r, (yc)c) to the ILP corresponds to a committee W = {c A : yc = 1}. Due to the constraint P c A yc = k, we have that |W| = k, so this is a committee of the required size. Next suppose that S = ((xi,ℓ,r)i,ℓ,r, (yc)c) is an optimal solution to the ILP. We may assume that under S, all constraints (3) are satisﬁed with equality, since otherwise we could set additional variables xi,ℓ,r to 1 without aﬀecting feasibility, and without lowering the objective value of the solution (because the coeﬃcient αℓ s r of xi,ℓ,r is non-negative). Further, this operation does not change the committee W. Now ﬁx a voter i N and a rank r [m]. Suppose that there are L candidates in W which voter i places in rank r or better, i.e., L = |W {c A : ranki(c) r}|.

By our assumption that the constraint (3) is satisﬁed in S with equality, exactly L of the variables xi,ℓ,r for ℓ [k] are set to 1 in S. By our assumption that the vector α is nonincreasing, the coeﬃcients αℓ s r of xi,ℓ,r in the objective function are non-increasing as ℓ goes from 1 to k. Hence, we may assume without loss of generality that in S, we have

xi,1,r = = xi,L,r = 1 and xi,L+1,r = xi,k,r = 0.

Then it follows that for i N, ℓ [k], r [m], we have

xi,ℓ,r = 1 if and only if W contains at least ℓcandidates c with ranki(c) r.

Fix i N and ℓ [k]. Write W = {c1, . . . , ck} so that c1 i i ck. Then it follows that, for every r [m], xi,ℓ,r = 1 if and only if ranki(cℓ) r.

Preferences Single-Peaked on a Circle

(If xi,ℓ,r = 1, then W contains at least ℓcandidates c with ranki(c) r, and so in particular c1, . . . , cℓmust have rank r or better. Conversely, if ranki(cℓ) r then c1, . . . , cℓall have rank r or better, so there are at least ℓcandidates in W with rank r or better, and so xi,ℓ,r = 1.) Hence, the utility of voter i in committee W is

α(sranki(c1), . . . , sranki(ck)) = X

ℓ [k] αℓ sranki(cℓ)

ℓ [k] αℓ Pm r=ranki(cℓ) s r

r [m] αℓ s r xi,ℓ,r.

Summing over all i N, we see that the objective value of solution S to the ILP equals U(s, α, W), the total utility of the committee W under the OWA-based rule. Thus, the ILP correctly encodes the winner determination problem. Next suppose that the proﬁle P is single-peaked. Consider the matrix M of coeﬃcients in the constraints of the ILP. Let M be the submatrix consisting only of the columns corresponding to the variables (yc)c A. Then M has one row consisting of only 1s (corresponding to constraint (2)), and for each i N and r [m] a row whose 1-entries encode the set {c A : ranki(c) r}. Note that each of these sets is a top-initial segment of the preference order of i, and hence (see Section 2) an interval of the axis on which P is single-peaked. Therefore M is a consecutive ones matrix (with the columns ordered according to the axis). Thus M is totally unimodular by Proposition 11. Now, the matrix M is obtained from M

by appending columns corresponding to the variables xi,ℓ,r. Each of these variables occurs in only 1 constraint of type (3) with coeﬃcient 1 (the sign depends on how we rearrange constraint (3) to bring all variables to one side). Thus, the column of the variable xi,ℓ,r is a (negative) unit column, and so by Proposition 10, the matrix remains totally unimodular after appending it. Thus, M is totally unimodular. (Technically, we also need to include the constraints 0 xi,ℓ,r 1 and 0 yc 1, but these are unit rows which can again be added without destroying total unimodularity.) Thus, by Theorem 9, the ILP can be solved in polynomial time. The above argument for total unimodularity does not go through if P is SPOC but not single-peaked, because then the matrix M only has the circular ones property. However, we can rearrange the ILP in such a way that we can show total unimodularity. This is a standard technique described in a useful survey by Dom (2009, Sec 4.1.4). Before we begin, let us note the following general fact: suppose we are given a system of constraints

f(x) = 0 and gj(x) 0 for j = 1, . . . , J.

If in this system we replace one or more of the constraints gj(x) 0 by gj(x) f(x) 0, then the set of feasible solutions x to the system does not change. Let P be a SPOC preference proﬁle. Using the algorithms from Section 3, ﬁnd a circle C such that P is single-peaked on C, and take some C arbitrarily. For i N and r [m], write Ti,r = {c A : ranki(c) r}. Then Ti,r is a top-initial segment of i s vote. Since P is single-peaked on C, Ti,r is an interval of C. Thus, either Ti,r or A \ Ti,r is an

Peters & Lackner

interval of . Deﬁne the sets

Γ1 = {(i, r) : i N, r [m] such that Ti,r is an interval of },

Γ2 = {(i, r) : i N, r [m] such that A \ Ti,r is an interval of } \ Γ1.

Then Γ1 and Γ2 form a partition of N [m]. Now consider the following integer linear program:

r [m] αℓ s r xi,ℓ,r (OWA-ILP-SPOC)

subject to X

c A yc k = 0 (2 )

ℓ [k] xi,ℓ,r X

c : ranki(c) r yc for i N, r [m] with (i, r) Γ1 (3 )

ℓ [k] xi,ℓ,r X

c : ranki(c)>r yc + k for i N, r [m] with (i, r) Γ2 (3 )

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

yc {0, 1} for c A

The program (OWA-ILP-SPOC) is very similar to the original program (OWA-ILP). Note that constraint (2 ) is the same as (2) after rearranging. The constraints (3 ) are a selection of the constraints (3). Finally, constraints (3 ) are obtained from constraints (3) after subtracting constraint (2 ). Since (2 ) is an equality constraint, by the earlier mentioned general fact, we see that (OWA-ILP-SPOC) and (OWA-ILP) have the same set of feasible solutions. They also have the same objective function, and therefore (OWA-ILP-SPOC) also correctly encodes the problem of ﬁnding a winning committee. Finally, we can prove that (OWA-ILP-SPOC) is totally unimodular, establishing the result that a winning committee can be found in polynomial time for SPOC proﬁles. Again take the constraint matrix M and consider the submatrix M corresponding to the variables (yc)c A. If we rearrange the columns of M according to , then each row of M consists of either of an interval of +1s surrounded by 0s, or of an interval of 1s surrounded by 0s (the latter arising from constraints (3 )). Combining Propositions 11 and 10, we see that M

is totally unimodular. As before, M is obtained from M by adding columns with a single non-zero entry, so M is also totally unimodular.

We obtain immediately the following two corollaries:

Corollary 13. For SPOC proﬁles, Chamberlin Courant can be computed in polynomial time.

Corollary 14. For SPOC proﬁles, PAV can be computed in polynomial time.

Corollaries 13 and 14 clearly also apply to single-peaked proﬁles. For Chamberlin Courant, a corresponding results has already been established using dynamic programming

Preferences Single-Peaked on a Circle

(Betzler et al., 2013), but to the best of our knowledge this is the ﬁrst polynomial-time algorithm for PAV on single-peaked proﬁles.4

An interesting question is whether the method of Theorem 12 can be further generalised. A possible generalization would be towards participatory budgeting, by introducing costs for candidates and replacing the committee size k by a budget limit. Does winner determination of OWA-based rules remain easy on single-peaked or SPOC proﬁles in this setting? Since totally unimodular matrices can only include coeﬃcients from { 1, 0, 1}, it seems unlikely that the packing constraint for non-unit costs can be implemented in this approach. However, we are not aware of a hardness result for this problem. It would also be interesting to see whether rules not part of the OWA-based family can be computed eﬃciently with single-peaked or SPOC proﬁles. Fluschnik, Skowron, Triphaus, and Wilker (2019) study the smoothed Nash product rule (which behaves similar to PAV but allows for non-binary utilities), and show that it is hard to compute even for single-peaked utilities. The ILP formulation (OWA-ILP) from the proof of Theorem 12 is of independent interest for computing OWA-based rules; for example, it seems to have proven useful in the empirical study of Faliszewski, Szufa, and Talmon (2018). Indeed, the algorithm that we propose for computing OWA-based rules (i.e., solving the program (OWA-ILP) using an ILP solver) is correct for general preferences, and comes with a polynomial-time guarantee in case the algorithm s input is single-peaked. This is in contrast to other winner determination algorithms that exploit preference structure: most such algorithms are specialised, and do not work at all if their input fails to be appropriately structured.

8. Discussion and Open Problems

Our results show that restricted preference domains that behave unfavorably in terms of axiomatic properties might still be very useful for algorithmic purposes. Indeed, our algorithms for Young s rule and OWA-based committee selection rules demonstrate that it is possible to move to a larger class than single-peaked preferences while maintaining polynomial-time runtime bounds.5 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 super-polynomial algorithms? One open problem of this type asks whether Dodgson s rule can be evaluated in polynomial time for SPOC 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.

4. As PAV is based on dichotomous preferences, single-peakedness corresponds to the candidate interval restriction (Faliszewski et al., 2011; Elkind & Lackner, 2015). 5. However, a recent study showed in numerical experiments that calculating OWA-based rules is computationally more expensive on random SPOC proﬁles than on random single-peaked proﬁles (Szufa, Faliszewski, Skowron, Slinko, & Talmon, 2020).

Peters & Lackner

The SPOC domain is strictly larger the single-peaked domain. To quantify the actual gain in generality or the increase in likelihood it would be of interest to know the number of SPOC proﬁles for a given number of voters and candidates. This line of work has been pursued by Durand (2003), Lackner and Lackner (2017), and Chen and Finnendahl (2018) for single-peaked proﬁles and thus could be compared with results for SPOC. We note that there is a one-to-one correspondence between SPOC proﬁles with two voters and square permutations,6 which can be used to obtain enumerative results. 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 diﬃcult since little is known even about extensions of single-peakedness on a line to two or more dimensions (see Sui, Francois-Nienaber, & Boutilier, 2013). Further generalizations can be realised by considering almost SPOC proﬁles, mirroring the literature on almost single-peaked proﬁles (Elkind, Faliszewski, & Slinko, 2012; Cornaz et al., 2012; Cornaz, Galand, & Spanjaard, 2013; Faliszewski, Hemaspaandra, & Hemaspaandra, 2014; Bredereck, Chen, & Woeginger, 2016; Erd elyi, Lackner, & Pfandler, 2017).

Acknowledgements

This paper is based on the two conference publications Preferences Single-Peaked on a Circle (Peters & Lackner, 2017) and Single-Peakedness and Total Unimodularity: New Polynomial-Time Algorithms for Multi-Winner Elections (Peters, 2018). We thank the anonymous reviewers of previous conference versions for useful suggestions and pointing out a mistake in one of our algorithms. We thank Edith Elkind for helpful discussions. Much of the work on this paper was performed while the authors were at the University of Oxford, supported by the European Research Council (ERC) under grant number 639945 (ACCORD). Martin Lackner was also supported by the Austrian Science Foundation FWF, grant P31890.

Appendix A. Recognition Algorithm

In this section, we describe the algorithm of Fitzsimmons and Lackner (2020) for deciding whether a proﬁle consisting of weak orders, at least one of which is a linear order, is singlepeaked. This algorithm is the basis of Theorem 2 (showing that SPOC proﬁles of linear orders can be recognised in linear time) and is also the basis of the proof of Theorem 3 (characterisation by forbidden subproﬁles), as we will see in Appendix B. Algorithm 1 (also called the guided algorithm) takes as input a proﬁle P of weak orders, at least one of which (the guiding vote vg) is a linear order. The algorithm then attempts to construct an axis on which P is single-peaked. The axis is constructed from the outside in. The process is guided by vg: the algorithm scans the alternatives in the ranking vg from

6. This correspondence can be seen by using the connection between proﬁles with two voters and permutations (as described in Lackner & Lackner, 2017). Condition 1 in Theorem 3 then corresponds to avoiding the set of permutations {14325, 14352, 15324, 15342, 24315, 24351, 25314, 25341, 41325, 41352, 42315, 42351, 51324, 51342, 52314, 52341}, which characterises square permutations (Waton, 2007; Duchi & Poulalhon, 2008; Albert, Linton, Ruˇskuc, Vatter, & Waton, 2011; Duchi, 2019). We thank Alexander Karpov for pointing out this connection.

Preferences Single-Peaked on a Circle

bottom to top, and decides at each step whether to place the alternative to the left or to the right. Let us introduce some notation for understanding Algorithm 1. The algorithm labels alternatives so that cm g cm 1 g g c1. We write C>i = {ci+1, . . . , cm}. The algorithm represents the axis under construction as a list of alternatives. For two disjoint lists AL, AR of alternatives, AL, AR is the concatenation of the lists. Similarly, we write ci, AR and AL, ci for preprending and appending an alternative to a list. For a collection A of alternatives, and a vote vk, we write maxk(A ) for an arbitrary alternative such that maxk(A ) a for all a A , and we write mink(A ) for an arbitrary alternative such that a mink(A ) for all a A . When deciding how to place alternatives, the algorithm checks whether some of the conditions (R1), (R2), (L1), or (L2) apply to a speciﬁc voter vk. These conditions are deﬁned as follows:

ci k mink(C>i) and maxk(AL) k mink(C>i) (R1)

maxk(C>i) k ci and maxk(AR) k ci (R2)

ci k mink(C>i) and maxk(AR) k mink(C>i) (L1)

maxk(C>i) k ci and maxk(AL) k ci (L2)

Algorithm 1 Recognising SP Input: a proﬁle P = (v1, v2, . . . , vn) of weak orders, where vg is a linear order Output: Is P single-peaked?

1: Label alternatives such that cm g cm 1 g g c1 2: Set AL and AR c1

3: for i = 2, . . . , m do

4: if for no voter vk = vg we have either (R1) or (R2) then

5: place ci on the right: AR ci, AR

6: else if for no voter vs = vg we have either (L1) or (L2) then

7: place ci on the left: AL AL, ci

9: (for some vk we have (R1) or (R2) and for some vs we have (L1) or (L2))

10: return P is not single-peaked

12: end for

13: return P is single-peaked on the axis = AL, AR

To prove that Algorithm 1 is correct, we need to prove that (i) when it returns an axis , then P is single-peaked on , and that (ii) when it returns that P is not singlepeaked, then P is not single-peaked on any axis. This is shown by Fitzsimmons and Lackner (2020). Below, for completeness, we prove part (i). Part (ii) is not formally required for our purposes, since the correctness of the SPOC recognition algorithm only relies on (i).

Proposition 15 (Fitzsimmons & Lackner, 2020). Let P be a proﬁle of weak orders, containing at least one linear order. If Algorithm 1 returns an axis , then P is single-peaked on .

Peters & Lackner

Proof. It is easy to see that the guiding vote vg is single-peaked on , since any top-initial segment {ci, ci+1, . . . , cm} of vg is an interval of by construction. Suppose some other vote vk = vg is not single-peaked on . Then there must be alternatives a, b, c A such that a b c and a k b and c k b (a valley). We may assume without loss of generality that c g a (otherwise we can rename alternatives so that the axis is reversed). We perform a case analysis on the preferences of the guiding vote vg, i.e., on the order in which Algorithm 1 has placed the alternatives:

a g b g c (alternatives are placed a ﬁrst then b then c): Consider the iteration when b was placed, i.e., when ci = b. At this point, a has already been placed, and since a b c, we have a AL. Note that condition (L2) is now satisﬁed for vk since a k b and c k b. Hence, b must have been placed on the right. So the algorithm returns an axis with a c b, a contradiction.

a g c g b (alternatives are placed a ﬁrst then c then b): Consider the iteration when c was placed, i.e., when ci = c. As before, we have a AL. Note that (R1) is satisﬁed for vk and so c is placed on the left. So the algorithm returns an axis with a c b, a contradiction.

b g a g c (alternatives are placed b ﬁrst then a then c): If alternatives are placed in this order, the algorithm cannot obtain an axis with a b c, where b is between a and c, a contradiction.

Since each case leads to a contradiction, vk must in fact be single-peaked on .

Appendix B. Characterisation by Forbidden Subproﬁles

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}.

Preferences Single-Peaked on a Circle

Proof. Suﬃciency was proven in Section 4. Here, we prove necessity. Suppose that P is a proﬁle of linear orders which is not SPOC. Then the recognition algorithm of Theorem 2, run on input P, will return that P is not SPOC (this follows from Propositions 1 and 15). We prove that if the algorithm gives a negative answer, then P must contain one of the forbidden subproﬁles. The algorithm of Theorem 2 ﬁrst constructs the proﬁle P obtained from P by slicing at some alternative z, where z is an alternative which is ranked last by some voter (say v1) in P. Then the upper part resulting from slicing v1 is the same as v1, and hence is a linear order. Call the voter in P corresponding to this upper part g. We label alternatives such that cm g cm 1 g g c2 g z. After constructing the sliced proﬁle P, the algorithm of Theorem 2 invokes Algorithm 1 from Appendix A and runs it on P to determine whether P is single-peaked. From Proposition 1, we know that P is single-peaked if and only if P is SPOC. Since we assumed that P is not SPOC, P is not single-peaked, and hence Algorithm 1 will return that P is not single-peaked (by Proposition 15). We will analyse all possible scenarios under which Algorithm 1 can give a negative answer, and show that in each case one of the three conditions of Theorem 3 applies. These conditions all refer to the proﬁle P rather than P, and it will be convenient to transform them into statements about P, which we do in two steps. First, note that the conditions of Theorem 3 are closed under reversing some of the votes in the condition. We formalise this observation in Lemma 16 below. For a voter vj, we write x1 j x2 j j xk if either x1 j x2 j j xk or xk j j x2 j x1. Where we do not care about the relative order of some alternatives, we write sets as before: A1 j A2 j A3 means that either A1 j A2 j A3 or A3 j A2 j A1.

Lemma 16. Condition 1 of Theorem 3 is satisﬁed if and only if there are distinct alternatives a, b, c, d, e A and voters vi and vj in P such that

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

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

One of conditions 2 or 3 of Theorem 3 is satisﬁed if and only if 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}.

Proof of Lemma 16. An easy case analysis.

Second, we give conditions on the sliced proﬁle P whose occurrence implies that one of the conditions of Lemma 16 holds. From now on, we will label the voters as P = ( v1, . . . , v2n). The voter corresponding to the upper part of the guiding vote will also be called g. For a voter vi, we write a i b if a is ranked higher than b in vi.

Lemma 17. One of the conditions of Theorem 3 (equivalently, of Lemma 16) is satisﬁed if one of the following suﬃcient conditions is satisﬁed:

Peters & Lackner

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

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

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

2. There are distinct alternatives a, b, c, d A \ {z} 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 A \ {z} and 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}.

4. There are distinct alternatives a, b, c, d A \ {z} and voters vi and vj in P such that

{a, b} i c i d,

{a, c} j b i d.

5. There are distinct alternatives a, b, c A \ {z} and voters vi, vj, and vk in P such that

{a, b} i {c, z},

{a, c} j {b, z},

a k z k b k c.

Proof of Lemma 17. We start with a useful observation: Suppose that vi is a voter in P with x1 i i xk for some x1, . . . , xk A \ {z}. Consider the voter vi in P from which vi was obtained. Then, for vi , we have x1 i i xk i z, by the deﬁnition of slicing. Suppose conditions 1, 2, or 3 of this lemma hold. Then apply the above observation to each of the voters, obtaining one of the cases of Lemma 16. Suppose condition 4 holds. Then consider the voters vi and vj in P from which vi and vj were obtained. Because vi is indiﬀerent between c and d, in the vote vi , the alternatives c and d are separated from a and b by the alternative z (by the deﬁnition of slicing). Thus, we have {a, b} i z i {c, d}. Similarly, we have {a, c} j z j {b, d}. Thus, by the ﬁrst part of Lemma 16, we are done. Suppose condition 5 hold. Consider the voters vi , vj , and vk in P from which vi, vj, and vk were obtained. Then we have {a, b} i {c, z} and {a, c} j {b, z}. Further, in the vote vk , the alternatives b and c are separated from a by the alternative z, and thus a k z k {b, z}. Thus, by the second part of Lemma 16, we are done.

Preferences Single-Peaked on a Circle

As we said above, because P is not SPOC, P is not single-peaked, and hence Algorithm 1 returns a negative answer when run on P. Thus, line 10 of Algorithm 1 is executed. Inspecting the if-clauses, this means that there is some iteration i (in which we are placing alternative ci on the axis) when

for some vk in P we have (R1) or (R2), and for some vs in P we have (L1) or (L2). ( )

By case analysis, we will prove that ( ) implies that one of the conditions of Lemma 17 holds. This suﬃces to prove the theorem. The cases we consider are:

A. condition R1 and L1 holding for the same voter ( vk = vs),

B. condition R2 and L2 holding for the same voter ( vk = vs),

C. condition R1 and L1 holding for diﬀerent voters ( vk = vs),

D. condition R2 and L2 holding for diﬀerent voters ( vk = vs),

E. condition R1 and L2 holding for the same voter ( vk = vs), and

F. condition R1 and L2 holding for diﬀerent voters ( vk = vs).

Note that R1 and L1 are symmetric; the same holds for R2 and L2. Hence we can omit the analogues of cases E and F for condition R2 and L1. For each of the cases A to F, we need to identify voters and alternatives to which one of the conditions of Lemma 17 apply. To do so, we will repeatedly apply the following rules, which can be proven by inspecting Algorithm 1. These rules are valid for every vi in P, and they hold at each iteration i of Algorithm 1, with AL and AR as deﬁned by the algorithm at the start of the iteration.

(g) We have {ci+1, . . . , cm} g {ci} g (AL AR) \ {z} g {z}, by the choice of vote g, its role in the guiding algorithm, and our labelling of alternatives.

(z) Let a, b A. If a i b, then a i z. Furthermore, if a i b, then a i z. This is because z is ranked last in all votes in P and P contains top orders.

(top) Let a, b, c A with a = b. If a i b and c i a, then c i b. This is because in all votes in P, indiﬀerences only occur among bottom-ranked alternatives (they are top orders).

(ind) Let ℓ AL and a {ci, . . . , cm}. If ℓ i a, then a i r for all r AR. Similarly if left and right are reversed. This follows from the inductive correctness proof of the guided algorithm; the algorithm would not have placed ℓand r in such a way that ℓ, a, r form a valley.

(ind2) Let ℓ1, ℓ2 AL such that ℓ1 is placed left of ℓ2 in AL, and let a {ci, . . . , cm}. Then ℓ2 i ℓ1 or ℓ2 i a. Similarly if left and right are reversed. This follows from the inductive correctness proof of the guided algorithm; otherwise the algorithm would not have placed ℓ2 on the left side as ℓ1, ℓ2, a would form a valley.

Peters & Lackner

We will use pictures to display various relations between alternations. Arrows a b signify that a b; labels on arrows indicate the rule used to deduce this relation. Similarly, a dashed line a b indicates a b. We are now ready to go through our case analysis.

A. Condition R1 holds for voter vk, and condition L1 holds for voter vk.

This case is impossible due to (ind): we have both maxk(AL) k mink(C>i) as well as maxk(AR) k mink(C>i).

B. Condition R2 holds for voter vk, and condition L2 holds for voter vk.

This case is also impossible due to (ind): we have both maxk(AL) k ci and maxk(AR) k ci.

C. Condition R1 holds for voter vk, and condition L1 holds for voter vs, with vk = vs.

Let wk = mink(C>i), let ws = mins(C>i), let ℓk = maxk(AL), and let rs = maxs(AR).

By R1, ci k wk and ℓk k wk. By L1, ci s ws and rs s ws.

C.1. Suppose wk = ws =: w. From (ind), we have w k rs and w s ℓk.

C.1.a. Suppose w k rs and w s ℓk. Then the following relations can be deduced:

sliced vote vk: sliced vote vs:

This corresponds to case 1 in Lemma 17 and thus we encounter case 1 in the theorem statement.

C.1.b. Suppose w k rs and w s ℓk. Then

sliced vote vk: sliced vote vs:

w C.1.b. rs

w C.1.b. ℓk

This corresponds to case 4 in Lemma 17.

C.1.c. Suppose w k rs and w s ℓk.

Preferences Single-Peaked on a Circle

sliced vote vk: sliced vote vs: guiding vote g:

w C.1.c. ℓk

This corresponds to case 2 in Lemma 17. C.1.d. Suppose w k rs and w s ℓk. Then, symmetrically to C.1.c.,

sliced vote vk: sliced vote vs: guiding vote g:

w C.1.d. rs

This corresponds to case 2 in Lemma 17.

C.2. Suppose wk = ws. By deﬁnition of ws and wk, we have ws k wk and wk s ws.

C.2.a. Suppose ws k wk and wk s ws. Then we have

sliced vote vk: sliced vote vs: guiding vote g:

This corresponds to case 3 in Lemma 17. C.2.b. Suppose ws k wk and wk s ws. Then we have

sliced vote vk: sliced vote vs:

wk C.2.b. ws

wk C.2.b. ws

This corresponds to case 4 in Lemma 17.

Peters & Lackner

C.2.c. Suppose ws k wk and wk s ws. Since ℓk k wk by R1, we have wk k rs by (ind), and thus ℓk k rs by transitivity. Similarly we obtain the other arrows labelled (ind) below, each involving a use of transitivity.

sliced vote vk: sliced vote vs: guiding vote g:

This corresponds to case 2 in Lemma 17. The arrows labeled with L1+C.2.c. are obtained by using L1 for ci s ws and rs s ws and the assumption of case C.2.c., wk s ws. C.2.d. Suppose ws k wk and wk s ws. Then, symmetric to 2.c.,

sliced vote vk: sliced vote vs: guiding vote g:

This corresponds to case 2 in Lemma 17.

D. Condition R2 holds for voter vk, and condition L2 holds for voter vs, with vk = vs.

Let bk = maxk(C>i), let bs = maxs(C>i), let ℓk = maxk(AL), and let rs = maxs(AR).

By R2, bk k ci and ℓk k ci. By L2, bs s ci and rs s ci.

D.1. Suppose bk = bs =: b. The case D.1. is similar to case C.1.; we present it for completeness.

D.1.a. Suppose ci k rs and ci s ℓk. Then:

sliced vote vk: sliced vote vs:

This corresponds to case 1 in Lemma 17.

Preferences Single-Peaked on a Circle

D.1.b. Suppose ci k rs and ci s ℓk. Then

sliced vote vk: sliced vote vs:

ci D.1.b. rs

ci D.1.b. ℓk

This corresponds to case 4 in Lemma 17.

D.1.c. Suppose ci k rs and ci s ℓk.

sliced vote vk: sliced vote vs: guiding vote g:

ci D.1.c. ℓk

This corresponds to case 2 in Lemma 17.

D.1.d. Suppose ci k rs and ci s ℓk. This case is symmetric to D.1.c.

D.2. Suppose bk = bs.

D.2.a. Suppose that either (i) ci k bs or (ii) ci s bk. Then we can deduce one of the ﬁrst two depicted relations ( vk or vs) as well as the guiding vote g:

sliced vote vk: sliced vote vs: guiding vote g:

If ci k bs, then k and g correspond to case 1 in Lemma 17; if ci s bk, then s and g correspond to case 1 in Lemma 17.

D.2.b. Now suppose that (i) ci k bs or (ii) ci s bk. As ℓk k ci (from R2), by (ind) we have ci k rs. Analogously, since rs s ci (from L2), by (ind) we have ci s ℓk. Thus:

Peters & Lackner

sliced vote vk: sliced vote vs: guiding vote g:

R2 {ci, rs}

L2 {ci, ℓk}

In case (i), this corresponds to case 2 in Lemma 17 when considering {bs, ci, ℓk, rs}. In case (ii), this corresponds to case 2 in Lemma 17 when considering {bk, ci, ℓk, rs}.

D.2.c. Otherwise, we have ci k bs and ci s bk. By (ind), from ℓk k ci (R2), and the fact that vk is a top order, we have ci k bs k rs. Analogously, by (ind), from rs s ci (L2), and the fact that vs is a top order, we have ci s bk s ℓk.

sliced vote vk: sliced vote vs:

R2 bs D.2.c ci ind rs

L2 bk D.2.c ci ind ℓk

We see that vk and vs hold little information. Thus, we consider their opposite sliced part, i.e., if vk is a sliced upper part, then we consider the lower part, or vice versa. Let v k and v s be the corresponding opposite parts. Now suppose that a candidate y = z is in the lowest level of vk. Then y is not in the lowest level of v k. Also, if x k y, then x is in the lowest level of v k, and hence y k x. Call this observation (opp). From this we get:

opposite sliced vote v k: opposite sliced vote v s: guiding vote g:

This corresponds to case 3 in Lemma 17.

E. Condition R1 holds for voter vk, and condition L2 holds for voter vk.

Let w = mink(C>i), let b = maxk(C>i), let ℓ= maxk(AL).

By R1, ci k w and ℓ k w. By L2, b k ci and ℓ k ci. Note that b k ci k w and so b = w. We have

Preferences Single-Peaked on a Circle

sliced vote vk: guiding vote g:

This corresponds to case 1 in Lemma 17.

F. Condition R1 holds for voter vk, and condition L2 holds for voter vs, with vk = vs.

Let wk = mink(C>i), let bs = maxs(C>i), let ℓk = maxk(AL), and let ℓs = maxs(AL).

By R1, ci k wk and ℓk k wk. By L2, bs s ci and ℓs s ci.

F.1. Suppose ci s wk. Since then bs s ci s wk, we have bs = wk. Then we have

sliced vote vs: guiding vote g:

This corresponds to case 1 in Lemma 17.

F.2. Suppose wk s ci. Since vs is a top order, and bs s ci s wk, we must have bs = wk.

F.2.a. Suppose bs k wk. Then we have

sliced vote vk: sliced vote vs: guiding vote g:

wk F.2. ci z z

This corresponds to case 5 in Lemma 17. F.2.b. Suppose wk k bs. Claim: There is ℓ {ℓs, ℓk} for which both vs and vk agree that ℓis not in the bottom layer

If ℓs = ℓk, we are done by R1 and L2. So suppose ℓs = ℓk. Now, by choice of ℓs and ℓk, we have ℓs s ℓk and ℓk k ℓs. But vs and vk are top orders, and ℓs s ci and ℓk k wk, so actually ℓs s ℓk and ℓk k ℓs.

Peters & Lackner

Next we show that it is not possible that both ℓk is in s s bottom layer and ℓs is in k s bottom layer. Suppose this was so. Suppose ℓs is placed by the algorithm to the left of ℓk. Then vs has a valley: ℓs s ℓk s bs. Otherwise, ℓk is placed by the algorithm to the left of ℓs. Then vk has a valley: ℓk k ℓs k ci. Both possibilities contradict (ind2).

With this choice of ℓ, we have

sliced vote vk: sliced vote vs:

wk F.2.b. bs

This corresponds to case 4 in Lemma 17.

F.2.c. Suppose wk k bs. This is impossible by choice of wk = mink(C>i).

F.3. Suppose wk s ci. (Note we do not consider bs in the following subcases, so it does not matter if bs = wk or not.)

F.3.a. Suppose ℓs = ℓk =: ℓ. Then we have

sliced vote vk: sliced vote vs: guiding vote g:

This corresponds to case 3 in Lemma 17.

F.3.b. Suppose ℓk lies to the left of ℓs (within AL). By (ind2) it holds that ℓs k ℓk or ℓs k ci. As ℓk k wk and ci k wk (both by R1), we can conclude that ℓs k wk. So we have

Preferences Single-Peaked on a Circle

sliced vote vk: sliced vote vs: guiding vote g:

g }z This corresponds to case 3 in Lemma 17. F.3.c. Suppose ℓs lies to the left of ℓk (within AL). By (ind2) it holds that ℓk s wk or ℓk s ℓs. As wk s ci (by F.3.) and ℓs s ci (by L2), we can conclude that ℓk s ci. So we have

sliced vote vk: sliced vote vs: guiding vote g:

g }z This corresponds to case 3 in Lemma 17.

We have shown that in all possible situations where the guided algorithm may return no, Lemma 17 is applicable and thus the theorem holds.

Achuthankutty, G., & Roy, S. (2018). Dictatorship on top-circular domains. Theory and Decision, 85(3-4), 479 493.

Albert, M. H., Linton, S., Ruˇskuc, N., Vatter, V., & Waton, S. (2011). On convex permutations. Discrete Mathematics, 311(8-9), 715 722.

Alcalde-Unzu, J., & Vorsatz, M. (2018). Strategy-proof location of public facilities. Games and Economic Behavior, 112, 21 48.

Alon, N., Feldman, M., Procaccia, A. D., & 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., & Tennenholtz, M. (2010b). Walking in circles. Discrete Mathematics, 310(23), 3432 3435.

Peters & Lackner

Aziz, H., Brill, M., Conitzer, V., Elkind, E., Freeman, R., & Walsh, T. (2017). Justiﬁed representation in approval-based committee voting. Social Choice and Welfare, 48(2), 461 485.

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

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

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

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

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

Booth, K. S., & 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., Geist, C., & Peters, D. (2017). Optimal bounds for the no-show paradox via SAT solving. Mathematical Social Sciences, 90, 18 27.

Brandt, F., Brill, M., & Harrenstein, P. (2016). Tournament solutions. In Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. (Eds.), Handbook of Computational Social Choice. Cambridge University Press.

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

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

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

Chamberlin, B., & Courant, P. (1983). Representative deliberations and representative decisions: Proportional representation and the Borda rule. American Political Science Review, 77(3), 718 733.

Chebotarev, P. Y., & Shamis, E. (1998). Characterizations of scoring methods for preference aggregation. Annals of Operations Research, 80, 299 332.

Chen, J., & Finnendahl, U. P. (2018). On the number of single-peaked narcissistic or singlecrossing narcissistic preference proﬁles. Discrete Mathematics, 341(5), 1225 1236.

Chen, J., Pruhs, K. R., & Woeginger, G. J. (2017). The one-dimensional Euclidean domain: ﬁnitely many obstructions are not enough. Social Choice and Welfare, 48(2), 409 432.

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

Preferences Single-Peaked on a Circle

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

Debord, B. (1987). Caract erisation des matrices des pr ef erences nettes et m ethodes d agr egation associ ees. Math ematiques et sciences humaines, 97, 5 17.

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.

Duchi, E. (2019). A code for square permutations and convex permutominoes. Discrete Mathematics & Theoretical Computer Science, 21(2). Permutation Patterns 2018, ar Xiv:1904.02691.

Duchi, E., & Poulalhon, D. (2008). On square permutations. In DMTCS Proceedings of the 5th Colloquium on Mathematics and Computer Science, pp. 207 222.

Durand, S. (2003). Finding sharper distinctions for conditions of transitivity of the majority method. Discrete Applied Mathematics, 131(3), 577 595.

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

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

Elkind, E., Lackner, M., & Peters, D. (2016). Preference restrictions in computational social choice: Recent progress. In Proceedings of the 25th International Joint Conference on Artiﬁcial Intelligence (IJCAI), pp. 4062 4065.

Elkind, E., Lackner, M., & Peters, D. (2017). Structured preferences. In Endriss, U. (Ed.), Trends in Computational Social Choice, chap. 10, pp. 187 207. AI Access.

Erd elyi, G., Lackner, M., & Pfandler, A. (2017). Computational aspects of nearly singlepeaked electorates. Journal of Artiﬁcial Intelligence Research, 58, 297 337.

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

Faliszewski, P., Skowron, P., Slinko, A., & Talmon, N. (2017). Multiwinner rules on paths from k-Borda to Chamberlin Courant. In Proceedings of the 25th International Joint Conference on Artiﬁcial Intelligence (IJCAI), pp. 192 198.

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

Faliszewski, P., Skowron, P., Slinko, A., & Talmon, N. (2017). Multiwinner voting: A new challenge for social choice theory. In Endriss, U. (Ed.), Trends in Computational Social Choice, chap. 2, pp. 27 47. AI Access.

Peters & Lackner

Faliszewski, P., Szufa, S., & Talmon, N. (2018). Optimization-based voting rule design: The closer to utopia the better. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 32 40.

Feigenbaum, I., & Sethuraman, J. (2015). Strategyproof mechanisms for one-dimensional hybrid and obnoxious facility location models. In Incentive and Trust in E-Communities: Papers from the 2015 AAAI Workshop. ar Xiv:1412.3414.

Fischer, F., Hudry, O., & Niedermeier, R. (2016). Weighted tournament solutions. In Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. (Eds.), Handbook of Computational Social Choice. Cambridge University Press.

Fitzsimmons, Z., & Hemaspaandra, E. (2020). Election score can be harder than winner. In Proceedings of the 24th European Conference on Artiﬁcial Intelligence (ECAI). To appear.

Fitzsimmons, Z., & Lackner, M. (2020). Incomplete preferences in single-peaked electorates. Journal of Artiﬁcial Intelligence Research (JAIR), 67, 797 833.

Fluschnik, T., Skowron, P., Triphaus, M., & Wilker, K. (2019). Fair knapsack. In Proceedings of the 33rd AAAI Conference on Artiﬁcial Intelligence (AAAI), pp. 1941 1948.

Hemaspaandra, E., Spakowski, H., & Vogel, J. (2005). The complexity of Kemeny elections. Theoretical Computer Science, 349(3), 382 391.

Hoﬀman, A. J., & Kruskal, J. B. (1956). Integral boundary points of convex polyhedra. In Kuhn, H. W., & Tucker, A. W. (Eds.), Linear Inequalities and Related Systems, pp. 223 246. Princeton University Press.

Janson, S. (2016). Phragm en s and Thiele s election methods. Tech. rep. ar Xiv:1611.08826 [math.HO], ar Xiv.org.

Kim, K. H., & Roush, F. W. (1980). Special domains and nonmanipulability. Mathematical Social Sciences, 1(1), 85 92.

Lackner, M., & Skowron, P. (2018). Consistent approval-based multi-winner rules. In Proceedings of the 19th ACM Conference on Economics and Computation (ACM-EC), pp. 47 48. ar Xiv:1704.02453.

Lackner, M.-L., & Lackner, M. (2017). On the likelihood of single-peaked preferences. Social Choice and Welfare, 48(4), 717 745.

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

Lu, T., & Boutilier, C. (2011). Budgeted social choice: From consensus to personalized decision making. In Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence (IJCAI), pp. 280 286.

Maurras, J. F., Truemper, K., & Akg ul, M. (1981). Polynomial algorithms for a class of linear programs. Mathematical Programming, 21(1), 121 136.

Mc Garvey, D. C. (1953). A theorem on the construction of voting paradoxes. Econometrica, 21(4), 608 610.

Moulin, H. (1991). Axioms of Cooperative Decision Making. Cambridge University Press.

Preferences Single-Peaked on a Circle

Moulin, H. (1988). Condorcet s principle implies the no show paradox. Journal of Economic Theory, 45(1), 53 64.

Nehring, K., & 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. (2017). Recognising multidimensional Euclidean preferences. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence (AAAI), pp. 642 648.

Peters, D. (2018). Single-peakedness and total unimodularity: New polynomial-time algorithms for multi-winner elections. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence (AAAI), pp. 1169 1176.

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

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

Rothe, J., Spakowski, H., & 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., & Vohra, R. V. (2002). Strategy-proof location on a network. Journal of Economic Theory, 104(2), 405 428.

Seymour, P. (1980). Decomposition of regular matroids. Journal of Combinatorial Theory, Series B, 28(3), 305 359.

Skowron, P. (2015). What do we elect committees for? A voting committee model for multi-winner rules. In Proceedings of the 24th International Conference on Artiﬁcial Intelligence (IJCAI), pp. 1141 1147.

Skowron, P., Faliszewski, P., & Lang, J. (2016). Finding a collective set of items: From proportional multirepresentation to group recommendation. Artiﬁcial Intelligence, 241, 191 216.

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

Szufa, S., Faliszewski, P., Skowron, P., Slinko, A., & Talmon, N. (2020). Drawing a map of elections in the space of statistical cultures. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). To appear.

Tangian, A. (2020). Policy representation across the political spectrum. In Analytical Theory of Democracy, pp. 405 446. Springer.

Tardos, E. (1986). A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research, 34(2), 250 256.

Peters & Lackner

Waton, S. D. (2007). On permutation classes deﬁned by token passing networks, gridding matrices and pictures: three ﬂavours of involvement. Ph.D. thesis, University of St Andrews.

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

Zou, S., & Li, M. (2015). Facility location games with dual preference. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 615 623.