# incomplete_preferences_in_singlepeaked_electorates__34babdab.pdf

Journal of Artiﬁcial Intelligence Research 67 (2020) 797-833 Submitted 07/2019; published 04/2020

Incomplete Preferences in Single-Peaked Electorates

Zack Fitzsimmons zfitzsim@holycross.edu College of the Holy Cross Department of Mathematics and Computer Science One College Street, Worcester, MA 01610, USA

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

Incomplete preferences are likely to arise in real-world preference aggregation scenarios. This paper deals with determining whether an incomplete preference proﬁle is single-peaked. This is valuable information since many intractable voting problems become tractable given singlepeaked preferences. We prove that the problem of recognizing single-peakedness is NP-complete for incomplete proﬁles consisting of partial orders. Despite this intractability result, we ﬁnd several polynomial-time algorithms for reasonably restricted settings. In particular, we give polynomial-time recognition algorithms for weak orders, which can be viewed as preferences with indiﬀerence.

1. Introduction

Both human and automated decision making often have to rely on incomplete information. The same issue arises in collective decision making voting in multi-agent systems. Konczak and Lang (2005) distinguish two main sources of incompleteness: The ﬁrst one is intrinsic incompleteness where a voter is unable or unwilling to give complete information. The second one is epistemic incompleteness where voters are able to provide complete information but at the time of decision making the required information is not fully available. Clearly, also a combination of these two scenarios may arise. Incomplete qualitative preferences are often modeled as partial orders (see, e.g., the survey by Boutilier & Rosenschein, 2016). For example, if voters provide some pairwise comparisons between alternatives, then partial orders arise naturally as the transitive closure of these comparisons. In this sense, partial orders can be viewed as the most general model for (qualitative) incomplete preferences while maintaining transitivity as a rationality assumption. A further standard assumption in this setting (Boutilier & Rosenschein, 2016) is that voters have a true, complete preference order, modeled as a total order. This total order is not available (due to intrinsic or epistemic incompleteness), but the known partial order is compatible with the underlying total order, i.e., it can be extended to this total order. Real-world preferences whether they are incomplete or not tend to possess an underlying structure, as they are formed by an implicit or explicit rationale. In this paper, we consider a particularly advantageous structural property: single-peaked preferences (Black, 1948). The single-peaked domain is one of the most commonly studied preference restrictions in social choice theory (Gaertner, 2002). Single-peaked preferences arise if preferences are formed based on an underlying ordering of alternatives, a so-called axis. It is assumed that voters have a most-

c 2020 AI Access Foundation. All rights reserved.

Fitzsimmons & Lackner

preferred alternative, their peak, and alternatives farther away on this axis are increasingly less preferred.

Single-peaked preference proﬁles enjoy many positive properties (see, e.g., surveys by Elkind, Lackner, & Peters, 2016, 2017), both for algorithmic purposes and from the axiomatic point of view from classical social choice. For example, the problem of determining if a candidate is a winner for Dodgson, Kemeny, and Young elections is computationally hard to compute (Bartholdi, Tovey, & Trick, 1989; Hemaspaandra, Hemaspaandra, & Rothe, 1997; Hemaspaandra, Spakowski, & Vogel, 2005; Rothe, Spakowski, & Vogel, 2003), but eﬃcient, polynomialtime algorithms exist when preferences are single-peaked (Brandt, Brill, Hemaspaandra, & Hemaspaandra, 2015). Another example of a desirable property is that single-peaked proﬁles are guaranteed to possess a transitive majority relation and thus a (weak) Condorcet is guaranteed to exist (Black, 1948, 1958). Furthermore, for single-peaked proﬁles there exist nondictatorial strategyproof voting rules (Moulin, 1984, 1991) (e.g., selecting a Condorcet winner); such rules do not exist for arbitrary preference proﬁles by the Gibbard Satterthwaite Theorem (Gibbard, 1973; Satterthwaite, 1975).

If only incomplete preference information is available, it is a challenge to determine whether voters preferences can be explained by a single-peaked axis. This is the main goal of this paper: to investigate the algorithmic problem of recognizing whether an incomplete preference proﬁle may be single-peaked, i.e., whether the voters underlying complete preference orders are singlepeaked. The motivation to obtain this information is twofold: First, to know that incomplete preferences may be explainable by a single-peaked axis provides fundamental understanding about the nature of the given preference data set, since the preferences of all voters can be explained by optimal points (peaks) on such an axis. Second, the single-peaked combinatorial structure is highly advantageous for algorithmic purposes, also in the case of incomplete preferences. This claim has been corroborated by recent work, which we discuss below in Section 1.2. In contrast to these two positive aspects, the axiomatic beneﬁts of the single-peaked domain do not fully extend to incomplete preferences. In particular, a transitive majority relation is no longer guaranteed (as we discuss later in Section 6.1). It thus deserves special attention that the algorithmic usefulness of incomplete single-peaked preferences is not an immediate consequence of their social choice-theoretic properties.

We now give an overview of the main results in this paper.

1.1 Results

This paper deals with the question of how to determine whether an incomplete preference proﬁle (e.g., a preference proﬁle comprised of partial orders) is single-peaked. This requires a deﬁnition of single-peakedness that is applicable to more general types of orders than total orders, i.e., partial orders. To this end, we propose the notion of possibly single-peakedness, which is satisﬁed if given an incomplete preference proﬁle there exist a compatible complete proﬁle that is single-peaked. To be more precise, we ask whether a given proﬁle of partial orders can be extended to total orders such that the resulting complete proﬁle is single-peaked (according to the usual deﬁnition). Based on this deﬁnition, we analyze the corresponding algorithmic recognition problem. In the following, let n denote the size of the preference proﬁle (number of voters) and let m denote the number of candidates. Our main computational results are as follows:

Incomplete Preferences in Single-Peaked Electorates

We prove that determining whether an incomplete preference proﬁle is single-peaked is NP-complete. This is in contrast to the case of complete preferences for which singlepeakedness can be determined in linear time (Escoﬃer, Lang, & Ozt urk, 2008). Furthermore, we strengthen this result by showing that NP-completeness still holds if one voter completely speciﬁes his or her preferences, and also for the case of local weak orders.

Apart from these hardness results, we present polynomial-time algorithms for recognizing single-peakedness in relevant subcases:

First, we consider the problem of determining whether a proﬁle of partial orders is singlepeaked for a given axis. We prove this problem to be polynomial-time solvable even for incomplete proﬁles consisting of partial orders.

Our most general polynomial-time algorithm is based on the consecutive ones problem. By providing a reduction from single-peaked recognition to the consecutive ones problem, we obtain an O(m2 n) algorithm for proﬁles of weak orders, i.e., rankings with ties. We have implemented this algorithm; see the discussion section (Section 7) for further details.

We also provide a direct O(m n) algorithm for single-peaked consistency for weak orders, with the requirement that the preference proﬁle contains at least one implicitly speciﬁed total order. This algorithm is an improvement over the single-peaked recognition algorithm by Escoﬃer et al. (2008) since it is applicable to a broader class of preference proﬁles (weak orders instead of total orders) while maintaining its runtime.

Furthermore, we present a 2-SAT-based algorithm, which also requires an implicitly speciﬁed total order, but is applicable to local weak orders (a generalization of weak orders). This more general algorithm requires O(m3 n) time.

For the case of top orders (weak orders with all incomparable candidates ranked last), we provide another direct, combinatorial algorithm with a runtime of O(m2 n). This algorithm does not rely on solving consecutive ones instances and thus is conceptually simpler, in particular for implementations.

These algorithms diﬀer in their worst-case runtime estimates, which range from O(m n) to O(m3 n). Note that these runtime estimates diﬀer only with respect to the number of candidates. In particular in scenarios with a large number of candidates (e.g., when aggregating web search results, as studied by Betzler, Bredereck, & Niedermeier, 2014), the actual runtime of these algorithms can be expected to vary.

Finally, we consider the case that voters are unable to provide total orders because their true preferences include some form of indiﬀerence. This gives another perspective on weak orders: viewing them not as incomplete but as rankings with ties. We compare our deﬁnition of possibly single-peaked preferences to other applicable single-peaked concepts, highlighting beneﬁts and drawbacks of our more general approach.

1.2 Related Work

As mentioned before, the single-peaked property is highly advantageous for algorithmic purposes. This has been demonstrated for many social choice problems based on total (linear)

Fitzsimmons & Lackner

order preferences, e.g., in the work of Betzler, Slinko, and Uhlmann (2013), Brandt et al. (2015), and Elkind and Ismaili (2015). Recent work has shown that similar beneﬁts also hold for possibly single-peaked preferences, in particular for proﬁles of weak orders. Peters (2018) shows that several rules that are NP-hard otherwise can be computed in polynomial time for possibly singlepeaked proﬁles of weak orders. This holds for multi-winner rules such as Chamberlin-Courant, Proportional Approval Voting, and the very general class of OWA-based rules. Furthermore, Young s rule is also polynomial-time computable for possibly single-peaked proﬁles of weak orders; this follows from work of Peters and Lackner (2017), who prove this result for the more general domain of preferences that are single-peaked on a circle. If we restrict weak orders to two equivalence classes, i.e., we only distinguish between good (approved) and bad (disapproved) candidates, we obtain the class of dichotomous preferences. The notion of possibly single-peakedness directly translates to this setting. Liu and Guo (2016) have shown that Minimax Approval Voting, although NP-hard in general (Le Grand, Markakis, & Mehta, 2007), can be solved in polynomial time for possibly single-peaked dichotomous preferences (see the work of Elkind & Lackner, 2015 containing a detailed discussion of single-peakedness and dichotomous preferences). Overall, the notion of possibly single-peaked preferences has been shown to be beneﬁcial for many algorithmic purposes. Another interesting eﬀect of single-peaked preferences is that the complexity of manipulative actions (such as manipulation and control) often decreases for single-peaked preferences (Faliszewski, Hemaspaandra, Hemaspaandra, & Rothe, 2011; Hemaspaandra, Hemaspaandra, & Rothe, 2016). When we instead consider more general types of preference orders than total orders we get diﬀerent behavior depending on the model of single-peakedness used. In general, the model of possibly single-peakedness does not yield such a reduction in complexity compared to the general case for diﬀerent manipulative actions (Fitzsimmons & Hemaspaandra, 2015, 2016; Menon & Larson, 2017). This is in contrast to the algorithmic beneﬁts mentioned in the last paragraph. However, here a decrease in complexity would not necessarily be desirable. In particular, if one seeks to reduce insincere behavior by choosing voting rules that are computationally hard to manipulate, then a reduction in computational complexity removes this kind of protection (Faliszewski et al., 2011). We also mention that Fitzsimmons and Hemaspaandra (2016) consider the complexity of manipulative actions of the models of single-peakedness discussion in Section 6 as well as another related restriction, single-peaked preferences with outside options (Cantala, 2004). Recognition algorithms for restricted preference domains are also indispensable for characterization results. The single-peaked domain (Ballester & Haeringer, 2011), the single-crossing domain (Bredereck, Chen, & Woeginger, 2013), and the group-separable domain (Ballester & Haeringer, 2011) have all been characterized by a set of forbidden subproﬁles. These characterizations are obtained by analyzing under which conditions recognition algorithms certify that a proﬁle is not contained in a preference domain. The Unguided Algorithm, as presented in this paper, was used for characterizing preferences that are single-peaked on a circle (Peters & Lackner, 2017). This was possible by relating the problem of recognizing preferences that are single-peaked on a circle to the problem of recognizing possibly single-peaked preferences. Such characterizations do not always exist, e.g., the Euclidean domain cannot be characterized by a ﬁnite set of forbidden subproﬁles (Chen, Pruhs, & Woeginger, 2017). Our deﬁnition of possibly single-peaked preferences resembles that of a possible winner (Konczak & Lang, 2005): A candidate is a possible winner if given an incomplete preference proﬁle there exists a compatible complete proﬁle in which this candidate is a winner. The possible

Incomplete Preferences in Single-Peaked Electorates

winner problem is a central, well-studied problem in computational social choice (Walsh, 2007; Betzler, Hemmann, & Niedermeier, 2009; Betzler & Dorn, 2010; Pini, Rossi, Venable, & Walsh, 2011; Xia & Conitzer, 2011; Baumeister & Rothe, 2012; Dery, Kalech, Rokach, & Shapira, 2014), see also the survey by Boutilier and Rosenschein (2016). The single-peaked domain is far from the only well-studied preference domain; many other domains have been considered from a computational viewpoint. We refer to the survey of Elkind et al. (2017) for an overview. Here, we brieﬂy mention papers that build upon or are directly related to our work. Another major preference restriction is the single-crossing domain, characterized by an ordering of voters. Elkind, Faliszewski, Lackner, and Obraztsova (2015) analyzed the recognition of incomplete single-crossing preferences. This work studies possibly single-crossing proﬁles (a notion analogously deﬁned to our deﬁnition of possibly single-peaked proﬁles), but found that approaches like consecutive ones and 2-SAT reductions which we use here yield weaker results in the single-crossing domain. In particular, ﬁxing the underlying order appears to have a much weaker eﬀect on the recognition problem. Another notion is topmonotonicity (Barber a & Moreno, 2011), for which questions similar to ours have been studied. The results for top-monotonicity resemble those for single-peaked preferences, although new techniques are required: The recognition problem for partial orders is NP-hard (Aziz, 2014) and solvable in polynomial time for weak orders (Magiera & Faliszewski, 2019). Furthermore, Peters (2017) highlights the inherent complexity of detecting more-dimensional Euclidean preferences and discusses possible deﬁnitions for weak orders. More broadly, recommender systems routinely have to deal with incomplete preferences and therefore this issue has received signiﬁcant attention in the ﬁeld. We refer to the following works for an overview (Schafer, Frankowski, Herlocker, & Sen, 2007; De Gemmis, Iaquinta, Lops, Musto, Narducci, & Semeraro, 2010; Masthoﬀ, 2015).

1.3 Outline of the Paper

In Section 2, we provide basic deﬁnitions from social choice theory. This is followed by Section 3, in which we introduce our notion of possibly single-peaked preferences and study their basic properties. In Section 4, we prove the computational hardness of recognizing possibly single-peaked preferences. All algorithmic results are then presented in Section 5; this section contains the most important contributions of this paper. In Section 6, we discuss indiﬀerence, weak orders, and other models of single-peakedness. A ﬁnal discussion of our results, a note on an implementation of the consecutive ones approach, and suggestions for future research can be found in Section 7. Some proof details (correctness proofs of some algorithms) are delegated to an appendix, Sections A.1, and A.2.

2. Preliminaries

In this paper, preferences are represented by diﬀerent types of orders (see Figure 1 for examples). The most general type are partial orders: a (strict) partial order P on a set X is a binary relation on X that is transitive (x Py and y Pz implies x Pz for all x, y, z X) and asymmetric (if x Py then not y Px for all x, y X). We say that y is ranked above x if x Py holds. If for two elements x, y X neither x Py nor y Px holds, we say that these two elements are incomparable; we write x y. An element x X is minimal if there is no element y X with y Px; maximal elements are deﬁned analogously.

Fitzsimmons & Lackner

A (strict) weak order is a partial order where the incomparability relation is transitive. Weak orders have the same expressiveness as total preorders1 (also known as nonstrict weak orders or preference orders). Since a weak order can be considered a ranking with ties, we refer to also as indiﬀerence in this context (see Section 6, where we discuss several other models of single-peakedness for preferences with indiﬀerence). Weak orders are also referred to as bucket orders (e.g. in Fagin, Kumar, Mahdian, Sivakumar, & Vee, 2006); elements that tie are in the same bucket . A top order is a weak order where incomparability appears only among minimal elements, i.e., if a b then both a and b are minimal elements in a top order. The ranked (i.e., nonminimal) elements of a top order T are those that are not incomparable to any other candidate. We would like to remark that top orders are also known as top lists (Dwork, Kumar, Naor, & Sivakumar, 2001; Fagin, Kumar, & Sivakumar, 2003) and as top-truncated votes (Baumeister, Faliszewski, Lang, & Rothe, 2012). A partial order with no incomparable elements is called total order, or, equivalently, a total order is a complete (x Py or y Px for all x, y X) partial order. Any partial order P can be extended to some total order T such that a Pb implies a Tb; T is then a (not necessarily unique) extension of P. Finally, we deﬁne a local weak order P on a set X to be a partial order on X with the following property: there exist sets X1, X2 with X1 X2 = X such that the elements in X1 are incomparable to all other elements in X and the proﬁle P restricted to X2 is a weak order. Intuitively, a local weak order is a weak order together with some isolated elements for which absolutely no information is available. Throughout the paper, total orders are denoted by c1 > c2 > . . . > ck ; the brackets allow us to unambiguously denote total orders consisting of one or even zero elements, i.e, we use to denote the empty order relation. For top orders, we write c1 > c2 > . . . > ck > to denote a top order where c1, . . . , ck are ranked as stated and all other elements (usually all remaining candidates in C) are ranked last, i.e., are minimal elements. We sometimes use set operators ( , , \) on top orders with the intended meaning that we apply these operators to the corresponding sets of ranked candidates. We describe weak orders with a notation similar to top orders and use to signify incomparability, e.g., c1 > c2 c3 > c4 . We would now like to address the usefulness of these types of orders for expressing preferences. Total orders allow the voter to fully specify a strict ranking of options. Given a large set of options, this might be unfeasible. Partial orders, on the other hand, allow the voter to specify the relative strict order of any pair of options subject to transitivity, which can be viewed as a rationality constraint. Thus they can be seen as a very general formalism for representing incomplete preferences. They are compatible with total orders in the sense that partial orders can always be extended to total orders. Weak orders are less general than partial orders but arise in many natural scenarios. For example every real-valued utility function implies a weak order (candidates with the same utility tie, i.e., are incomparable in our sense). Local weak orders correspond to partial real-valued utility functions and thus arise in scenarios where voters do not have knowledge about all candidates. If the elicitation of preferences is costly, one might ask only for the most important (top ranked) options of each voter; in such a case we obtain top

1. Total preorders are binary relations that are transitive and complete (x Py or y Px for all x, y X). For our algorithmic purposes, it is not relevant whether to use strict weak-orders or total preorders. Our main reason to use strict weak orders as the standard deﬁnition is that total preorders are not necessarily partial orders (they are not asymmetric) and hence do not ﬁt in our hierarchy of orders.

Incomplete Preferences in Single-Peaked Electorates

Total Top Weak Local weak Partial order order order order order

Figure 1: The order zoo: examples of diﬀerent types of orders that are used to describe preferences.

orders. Top orders also are the natural type of order for specifying preferences in some scoring rules. We will further comment on scoring rules and top orders at the end of Section 5.2. Throughout this paper we use C to denote the set of candidates or options. Votes (or preference orders) are considered to be either partial, local weak, weak, top, or total orders. For a vote Vi, we use x i y to denote that x is ranked above y. If there is only one vote under consideration, usually denoted by V , we omit the index and write x y. If Vi is a weak or top order, we write x i y if voter i is indiﬀerent between x and y, x i y if voter i is either indiﬀerent or ranks x above y. A tuple (V1, . . . , Vn) of votes is called a (preference) proﬁle of {partial orders, local weak orders, weak orders, top orders, total orders}, depending on the type of orders. Given a vote V and a set of candidates C C, we deﬁne V [C ] to be the order V restricted to elements in C . Analogously, given a preference proﬁle P = (V1, . . . , Vn), we deﬁne P[C ] to be (V1[C ], . . . , Vn[C ]). We denote the number of candidates with m and the number of votes with n.

3. Single-Peaked Proﬁles

We start by giving a deﬁnition for single-peaked proﬁles of total orders and then extend this deﬁnition to partial orders. A central concept is that of an axis, which is a total order on C. Let A be an axis. Throughout this paper we write x y instead of x Ay. (Note that we use for votes and for axes.) We formally deﬁne single-peakedness for total orders below using triples of candidates, so-called valleys. Valleys will be important for many of the results in our paper.

Deﬁnition 1. Let V be a partial order on C. A vote V contains a v-valley with respect to an axis A if there exist c1, c2, c3 C such that c1 c2 c3, c1 c2 and c3 c2.

The deﬁnition of v-valleys suﬃces to deﬁne single-peakedness for proﬁles of total orders.

Deﬁnition 2. A proﬁle P of total orders is single-peaked with respect to A if no vote V P contains a v-valley with respect to A (and thus every vote has only a single peak ). A proﬁle of total orders is single-peaked consistent (or simply, single-peaked) if there exists some axis A such that P is single-peaked with respect to A.

Note that this is similar to how single-peakedness is deﬁned in (Brandt et al., 2015; Elkind et al., 2017), and easily seen to be equivalent. We now want to extend this deﬁnition to proﬁles of partial orders. A natural way is to consider extensions of partial orders to total orders.

Fitzsimmons & Lackner

v-valley u-valley u-valley

a b c a b c d a c b d

Figure 2: Examples of v-valleys and u-valleys

Deﬁnition 3. Let P = (V1, . . . , Vn) be a proﬁle of partial orders. The proﬁle P is possibly single-peaked with respect to an axis A if for every k {1, . . . , n}, Vk can be extended to a total order V k such that the proﬁle of total orders P = (V 1, . . . , V n) is single-peaked with respect to A. A proﬁle of partial orders is possibly single-peaked consistent if it is possibly single-peaked with respect to some axis.

While it is also conceivable to require that every extension is single-peaked ( necessarily instead of possibly ), this would yield an extremely restrictive deﬁnition, basically requiring that the proﬁle of partial orders already contains almost total orders. We consider this deﬁnition at the end of Section 6. Apart from that, we focus our attention on the more general deﬁnition of possibly single-peaked proﬁles. We now deﬁne an equivalent deﬁnition for possibly single-peakedness based on valleys. For this, we ﬁrst need the following deﬁnition of u-valleys.

Deﬁnition 4. Let V be a partial order on C. The vote V contains a u-valley with respect to A if there exist distinct elements a, b, c, d C with a b d and a b as well as a c d and d c.

In Figure 2 a graphical comparison of vand u-valleys is shown. In the following, we see that these two types of valleys characterize possibly single-peaked incomplete proﬁles.

Lemma 1. Let P = (V1, . . . , Vn) be a proﬁle of partial orders and A an axis. The following two statements are equivalent.

(i) The proﬁle P is possibly single-peaked with respect to A.

(ii) Every vote V P contains neither a u-valley nor a v-valley with respect to A.

Proof. To see that (i) implies (ii), note that if some Vk contained a u-valley in the sense of Deﬁnition 4 then every extension V k would contain a v-valley. More concretely, if a, b, c, d C form a u-valley in Vk then any extension of Vk either contains a v-valley with respect to A on the candidates a, b, c or on b, c, d. Furthermore, if Vk contained a v-valley then so would every extension. For the other direction, we show that a vote V not containing a valley can be extended to a total order that is single-peaked with respect to A. We recursively deﬁne its extension V

starting with its last ranked candidate. Let V (1) denote the last ranked candidate of V , V (2) the second-to-last, etc. For the deﬁnition we require two functions:

left A(X) is the smallest (leftmost) candidate in X with respect to the axis A.

right A(X) is the largest (rightmost) candidate in X with respect to the axis A.

Incomplete Preferences in Single-Peaked Electorates

We now deﬁne for every i {1, . . . , m},

Xi = C \ {V (1), . . . , V (i 1)} and

( right A (Xi) if right A (Xi) is a minimal element in V [Xi], left A (Xi) otherwise. .

This deﬁnition immediately yields that V is single-peaked with respect to A: By always choosing one of the two outermost candidates on A (that have not yet been chosen) for the next higher ranked candidate, valleys cannot arise. It remains to show that V is indeed an extension of V , i.e., we have to show that for every pair of candidates a, b C, a b implies a b. Towards a contradiction assume that a b and b a. Let i {1, . . . , m} such that V (i) = a. We have to consider two cases: a = left A(Xi) and a = right A(Xi). Let a = left A(Xi) and d = right A(Xi). Since V (i) = a, we know that there has to exist a c Xi with d c. Observe that a c d has to hold. Furthermore, either a b d or b = d holds. If a b d holds then a, b, c, d for a u-valley. If b = d then a c b, a b and b c holds: a v-valley. Both cases contradict our assumption that V does not contain valleys with respect to A. Now, let a = right A(Xi). This immediately yields a contradiction to the deﬁnition of V (i), since b Xi, a b and hence a is not a minimal element in V [Xi].

This lemma immediately yields a polynomial-time algorithm for checking whether an incomplete proﬁle is possibly single-peaked with respect to a given axis:

Proposition 1. Verifying whether a proﬁle of partial orders is single-peaked with respect to a given axis can be done in O(m4 n) time.

Proof. For every quadruple of candidates and every vote, an algorithm has to check whether a uor v-valley arises (by Lemma 1).

Let T {partial order, local weak order, weak order, top order, total order} be a type of order. The remainder of the paper is dedicated to a more challenging computational problem:

T Single-peaked Consistency

Instance: A proﬁle P of type T and a set of candidates C. Question: Is P possibly single-peaked consistent?

Note that in contrast to the problem in Proposition 1, the input of this problem does not include an axis. The Total Order Single-peaked Consistency problem is known to be solvable in polynomial time as witnessed by several algorithms. Historically, the ﬁrst algorithm to solve this problem was due to Bartholdi and Trick (1986) and is based on the consecutive ones problem, which we will encounter in Section 5.1. This approach yields a runtime of O(m2 n), which was improved by direct, combinatorial algorithms ﬁrst to O(m n + m2) by Doignon and Falmagne (1994) and ﬁnally to O(m n) by Escoﬃer et al. (2008). In the next section, we show that a polynomial-time result is unlikely to exist for the case of partial orders and even local weak orders.

Fitzsimmons & Lackner

4. Hardness Results

Theorem 1. Local Weak Order Single-peaked Consistency is NP-complete.

Proof. We reduce from the NP-complete Betweenness problem (Opatrny, 1979). A Betweenness instance consists of a ﬁnite set S and a set T containing (ordered) triples of distinct elements of S. The decision problem asks whether there is a total order L such that for every triple (a, b, c) T we have either a Lb Lc or c Lb La. Intuitively, a triple (a, b, c) T corresponds to the constraint that b has to lie in between a and c on the total order L. We construct a proﬁle of local weak orders P with a candidate set C = S, i.e., we identify elements in S with candidates in C. The preference proﬁle P consists of two votes for each triple (a, b, c): the partial order {a c, b c} and the partial order {b a, c a}. These two votes form a valley on any axis with c between a and b and on any axis with a between b and c. Thus b has to be between a and c on any single-peaked axis. We are now going to show that P is possibly single-peaked consistent if and only if the Betweenness instance is a yes-instance. Assume that there exists an extension of P, Pext, and an axis, A, such that Pext is single-peaked with respect to A. By Lemma 1 we know that this implies that no v-valleys exist. Since for every triple (a, b, c) T both the vote {a c, b c} and {b a, c a} are contained in P, we have that neither a c b, b c a, b a c, nor c a b can hold. Consequently it has to hold that either a b c or c b a holds and thus b is in between a and c. Assume that there exists a set T such that all constraints in T are satisﬁed. It is easy to verify that P is possibly single-peaked with respect to T.

Corollary 1. Partial Order Single-peaked Consistency is NP-complete.

The proof of Theorem 1 uses preference proﬁles where the votes contain very little information: only two pairs of candidates are comparable in each vote. We know that determining single-peaked consistency is possible in polynomial time if every vote is a total order, i.e., all votes contain complete information. What happens if one voter provides complete information? Having a single completely speciﬁed vote has been found to be helpful in a related context: It allows for the eﬃcient elicitation of single-peaked preferences using only few comparison queries (Conitzer, 2009) and thus the communication complexity of preference elicitation is reduced. However, in our case such a voter does not provide enough additional information for a decrease in (computational) complexity.

Theorem 2. The Partial Order Single-peaked Consistency problem is NP-complete, even if the given preference proﬁle contains a total order.

Proof. We reduce from Set Splitting: Let X be a ﬁnite set. Given a collection Z of subsets of X, is there a partition of X into two subsets X1 and X2 such that no subset of Z is contained entirely in either X1 or X2? This problem is NP-complete even if all sets in Z have cardinality three (Garey & Johnson, 1979). Let X = {c1, . . . , cm}. For the construction, we identify the elements of X with candidates and add an additional candidate x. For each set {ci, cj, ck} Z with i < j < k we introduce one vote: {ci cj, x ck}. In addition, we add the vote x cm c1. We claim that the resulting preference proﬁle P is possibly single-peaked consistent if and only if (X, Z) is a Set Splitting yes-instance. Assume that P is possibly single-peaked with respect to an axis A. We deﬁne X1 to be the candidates on A left of x and X2 those that are right of x. We will show that there is no

Incomplete Preferences in Single-Peaked Electorates

subset of Z entirely contained in X1 or X2. Towards a contradiction assume that {ci, cj, ck} Z with i < j < k are contained in X1. Then it has to hold that, on A, ci, cj, ck are all left of x. Furthermore, from the vote x cm c1 then it follows that the relative order on A of x, ci, cj, ck has to be ci cj ck x. However, then the vote {ci cj, x ck} contains a u-valley with respect to this order. Assuming that {ci, cj, ck} Z are contained in X2 leads to the same contradiction. Thus, X1 and X2 indeed certify that (X, Z) is a yes-instance. For the other direction, assume that (X, Z) is a yes-instance and that X1 and X2 are the corresponding partition. Let an axis A be deﬁned as the elements in X1 with indices in increasing order followed by x followed by the elements in X2 with indices in decreasing order. We claim that A is an axis for P. Clearly, the vote x cm c1 is single-peaked with respect to A. Let us consider a vote {ci cj, x ck} with i < j < k. Since X1 and X2 are a valid partition, at least one of ci, cj, ck has to be left of x and another one right. This rules out that a u-valley is formed and thus all votes are possibly single-peaked with respect to A.

As we will see in the following section, these two hardness results establish the tractability frontier.

5. Algorithms

In this section, we present several polynomial-time algorithms for recognizing possibly singlepeaked proﬁles.

5.1 The Consecutive Ones Approach

Our ﬁrst algorithm in this section solves the Weak Order Single-peaked Consistency problem in polynomial time. It uses a reduction to the problem of detecting the consecutive ones property in a binary matrix, i.e., a matrix consisting of zeros and ones. Such a matrix has the consecutive ones property if its columns can be permuted in such a way that in all rows the ones appear consecutively. The corresponding decision problem is the following:

Consecutive Ones

Instance: A binary matrix M. Question: Does M possess the consecutive ones property, i.e., does there exist a permutation of the columns of M such that in each row all of the ones are consecutive?

The consecutive ones property was originally deﬁned by Fulkerson and Gross (1965) and shown solvable in polynomial time. More speciﬁcally, they showed that given an s t matrix this problem can be solved in O(s t2). Booth and Lueker (1976) improved on this result by ﬁnding an O(s t) algorithm2 through the development and use of the novel PQ-tree data structure. With this data structure it is not only possible to ﬁnd one valid permutation of columns (if it exists), but to compactly represent all possible column permutations that witness the consecutive ones property. Subsequent work has improved these results in various ways (Meidanis, Porto, & Telles, 1998; Habib, Mc Connell, Paul, & Viennot, 2000; Hsu, 2002; Mc Connell, 2004; Raﬃnot, 2011).

2. More precisely, their algorithm has a runtime of O(s+t+f), where f is the number of ones in M. In our case, the matrices obtained from the reduction have Θ(s t) one entries and hence this algorithm has a runtime of O(s t) .

Fitzsimmons & Lackner

Bartholdi and Trick (1986) were the ﬁrst to relate the problem of recognizing single-peaked preferences to the consecutive ones problem. We slightly modify their approach for proﬁles of total orders to be applicable to proﬁles of weak orders, and by that solve the Weak Order Single-peaked Consistency problem. The reduction works as follows:

Construction 1. Let P = (V1, . . . , Vn) be a proﬁle of weak orders over candidate set C with |C| = m. For each Vi we construct an m m binary matrix Xi. We assume that the rows and columns of Xi are indexed by C. For a, b C, the entry of Xi is deﬁned as:

( 0 if a i b 1 if b i a or a i b .

Finally, the matrices X1, . . . , Xn are row-wise concatenated to obtain the mn m matrix XP.

Example 1. Consider the preference proﬁle P = (V1, V2) with V1 = a c b e d f and V2 = a b c e d f . We construct X1 and X2:

a b c d e f

a 1 0 1 0 0 0

b 1 1 1 0 0 0

c 1 0 1 0 0 0

d 1 1 1 1 1 0

e 1 1 1 1 1 0

f 1 1 1 1 1 1

a b c d e f

a 1 0 0 0 0 0

b 1 1 0 0 0 0

c 1 1 1 0 0 0

d 1 1 1 1 1 0

e 1 1 1 1 1 0

f 1 1 1 1 1 1

We then row-wise concatenate X1 and X2 to construct XP.

a b c d e f 1 0 1 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1

b a c d e f 0 1 1 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1

Observe that XP has the consecutive ones property, as witnessed by X P. The corresponding permutation of columns (bacdef) directly corresponds to an ordering of candidates, and indeed P is possibly single-peaked with respect to b a c d e f.

To prove the correctness of Construction 1, we ﬁrst deﬁne a valley-based characterization of possibly single-peaked proﬁles of weak orders, analogous to Lemma 1. We see that for proﬁles of weak orders, u-valleys are not relevant.

Incomplete Preferences in Single-Peaked Electorates

Lemma 2. Let P = (V1, . . . , Vn) be a proﬁle of weak orders and A an axis. The following two statements are equivalent.

(i) The proﬁle P is possibly single-peaked with respect to A.

(ii) Every vote V P does not contain a v-valley with respect to A.

Proof. That statement (i) implies (ii) is a special case of Lemma 1. For the other direction, every u-valley on a b c d (see Figure 2) implies a v-valley either on a b d or on a c d.

Using Construction 1 and Lemma 2, we can now show that:

Theorem 3. The Weak Order Single-peaked Consistency problem can be solved in O(m2 n) time.

Proof. Let P be a preference proﬁle of weak orders. We will show that V is possibly singlepeaked if and only if the matrix XP, as obtained by Construction 1, has the consecutive ones property. This proof closely follows the argument made by Bartholdi and Trick (1986) for total orders, but requires Lemma 2 to relate possible single-peaked weak order to the consecutive ones property. If P is possibly single-peaked with respect to an axis A then by Lemma 2 we know that no preference order V P contains a v-valley with respect to A. When the columns of the matrix XP are permuted with respect to the axis A, no row will contain the sequence 1 0 1 . since this corresponds to a preference order that strictly decreases and then strictly increases along the axis A (a v-valley). Therefore X has the consecutive ones property. For the other direction suppose that V is not possibly single-peaked. Then by Lemma 2 we know that for every possible axis there exists a preference order V P such that V contains a v-valley with respect to that axis. So every permutation of the columns of XP will correspond to an axis where some preference order has a v-valley. As stated in the proof of the other direction, a v-valley corresponds to a row containing the sequence 1 0 1 , so clearly X does not have the consecutive ones property. Since it takes O(m2 n) time to construct XP and O(m2 n) time to solve the corresponding Consecutive Ones problem, we can solve the Weak Order Single-peaked Consistency problem in O(m2 n) time.

As mentioned earlier, the approach using PQ-trees by Booth and Lueker (1976) is able to compute all possible permutations that witness the consecutive ones property. Thus, Theorem 3 actually allows us to compute all possibly single-peaked axes. As these permutations are stored in a compact way, the runtime of O(m2 n) time holds even for a potentially exponential number of axes. To sum up, the consecutive ones approach grants us a simple and quick solution for the Weak Order Single-peaked Consistency problem. The downside is that by relying on the full consecutive ones machinery, any practical implementation has to deal with the nontrivial PQ-tree data structure or related concepts (Meidanis et al., 1998; Habib et al., 2000; Mc Connell, 2004). In the following two sections we present direct, combinatorial algorithms.

Fitzsimmons & Lackner

5.2 The Guided Algorithm

We now present a second polynomial-time algorithm for proﬁles of weak orders. In contrast to consecutive ones approach of Section 5.1, this algorithm requires an additional condition: The input proﬁle must contain at least one total order, the guiding vote, to guide the placement of candidates on the axis. Due to this extra information, we gain two major beneﬁts: First, the algorithm is conceptually simpler than the more complex algorithms for solving the consecutive ones problem. This has clear beneﬁts for implementing the algorithm, and is also necessary for the use in characterization proofs (see, e.g., the work of Peters and Lackner (2017) as discussed in Section 1.2). Second, this algorithm is faster. We achieve a runtime of O(m n) compared to the runtime of O(m2 n) by the consecutive ones approach.

Theorem 4. If the proﬁle contains a total order, the Weak Order Single-peaked Consistency problem can be solved in O(m n) time.

Theorem 4 is based on Algorithm 1, which we refer to as the Guided Algorithm. Without loss of generality, we assume that the guiding vote is cm cm 1 c1 , i.e., we number the candidates based on the guiding vote. The requirement that this guiding vote is part of the input can be weakened considerably. It suﬃces that a guiding vote is implicitly contained in the proﬁle. The following procedure ﬁnds such an implicit guiding vote, if one exists: Look for some vote with a unique last ranked candidate. This candidate is ranked last in the guiding vote. Remove this candidate from the proﬁle and repeat this step to obtain the second-to-last element in the guiding vote, etc. If at some point no vote has a unique last-ranked candidate, no implicit guiding vote exist. As in each step there might be more than one last-ranked candidate to choose from, such a guiding vote is not unique. However, it is straightforward to prove that adding any implicit guiding vote obtained in this way does not change whether the proﬁle is possibly single-peaked. This procedure can be implemented in O(m n) time.

Example 2. Let us consider the proﬁle P = (V1, V2, V3) with V1 = a b c d e , V2 = a b c d e , and V3 = e d b c a . This proﬁle clearly does not contain a total order. However, a guiding vote can be found implicitly: Candidate e is (uniquely) ranked last in V1, so we remove this candidate. In this reduced proﬁle, V2 ranks d last. We again remove this candidate and see that V1 now equals a b c . Thus, we can use a b c d e as our guiding order.

The algorithm has a simple structure: The lowest ranked candidate in the guiding vote, c1, is placed on the rightmost position of the axis (this choice is arbitrary.) Starting with the second lowest ranked candidate in the guiding vote, c2, the candidates are successively placed on the axis either at the leftmost or rightmost still-available position. The lists AL and AR correspond to the left-hand and right-hand side of the axis under construction. For each candidate, we test whether it can be placed on the right-hand side or left-hand side without creating a v-valley; u-valleys can be ignored by Lemma 2. If only one of these options is viable, the candidate is placed accordingly. If both left and right are possible, we place the candidate arbitrarily right. If neither is possible, the preference proﬁle is not single-peaked. Testing whether a vote Vk imposes restrictions on the placement of a candidate is achieved by four conditions. These conditions distinguish four categories of candidates: candidates in AR, candidates in AL, candidates that have not yet been placed (C>i = {ci+1, . . . , cm}), and the candidate that is currently under consideration (ci). We are only checking for valleys that

Incomplete Preferences in Single-Peaked Electorates

AL {ci+1, . . . , cm} ci AR

AL {ci+1, . . . , cm} ci AR

Figure 3: Graphical representation of the conditions testing whether ci can be placed on the right-hand side (R1, R2) or on the left-hand side (L1, L2)

include ci. This gives rise to the following four conditions: (R1) and (R2) test whether placing ci on the right-hand side leads to valleys, (L1) and (L2) do the same for the left-hand side. Figure 3 displays a graphical representation. Note that we do not verify whether a v-valley arises with aℓ ci and ar ci, where aℓ AL and ar AR; such a valley would have already be detected at an earlier stage of the algorithm (cf. correctness proof). Since we are working with weak orders, we do not have to consider every candidate triple possibly fulﬁlling these conditions but have to check only maximal or minimal candidates. More speciﬁcally, checking whether there is a candidate c AL and c C>i with c c is equivalent to whether any maximal element in AL is preferred to some minimal element in C>i (subject to ). For k [n], let mink(X) denote a function that picks an element in X that is minimal with respect to k. The function maxk(X) is deﬁned analogously. Now, we can formally deﬁne the four conditions:

ci k min k (C>i) and max k (AL) k min k (C>i) (R1)

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

ci k min k (C>i) and max k (AR) k min k (C>i) (L1)

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

Using these four deﬁnitions, we can give a succinct description of the Guided Algorithm, (Algorithm 1). For a correctness proof of Algorithm 1, we refer the reader to the appendix, Section A.1.

Example 2 (continued). We apply the Guided Algorithm to P = (V1, V2, V3) with V1 = a b c d e , V2 = a b c d e , and V3 = e d b c a . We use the implicitly found guiding order a b c d e and thus start with AL = and AR = e . We now want to place d on the axis. None of the four conditions is satisﬁed for voters V1 and V2, but V3 satisﬁes condition (L1). Thus, d has to be placed right, i.e., AR d e . We continue with the third-lowest candidate on the guiding order: c. Here, we encounter a problem: when considering V3, we see that c satisﬁes both (R2) and (L1). Thus, the algorithm cannot place c and returns not single peaked. Using other implicitly given guiding orders, e.g., d b c e a , would have yielded the same outcome.

Theorem 4 claims that the Guided Algorithm requires O(m n) time. Note that this is only possible if the conditions (R1, R2, L1, L2) can be checked in constant time. Thus, the minima

Fitzsimmons & Lackner

Input: A set of candidates C, a preference proﬁle of weak orders P = (V1, . . . Vn) including a guiding vote cm cm 1 c1. Output: An axis A or not single peaked.

1 AL , AR c1

2 for i 2 . . . m do

3 right true; left true

4 for k 2 . . . n do

5 if condition (R1) or (R2) holds then

6 right false

7 if condition (L1) or (L2) holds then

8 left false

9 if right = true then

10 AR ci AR

12 if left = true then

13 AL AL ci

15 return not single peaked

16 return AL AR

Algorithm 1: The Guided Algorithm

and maxima have to be computable in constant time. For maxk(AL) and maxk(AR) this is easily possible by storing and updating these two values: if ci is placed left, we update maxk(AL) in case ci is the new maximum (with respect to k); if ci is placed right, we proceed analogously maxk(AR). For computing a minimal value of C>i, observe that the set C>i becomes smaller with increasing i. Thus, a minimal value of C>i might disappear at some point and a new (larger) value has to be chosen. The new minimum is the smallest element (with respect to k) in C>i that is at least as large as the old minimum. If we maintain pointers to the minimum elements, the amortized cost of this update procedure is O(1). A maximal value of C>i can be found analogously.

5.3 The Unguided Algorithm

Our next algorithm is applicable to top orders. As it is not dependent on a guiding vote, we refer to it as the Unguided Algorithm. The Unguided Algorithm has a runtime of O(m2 n), the same as achieved by the consecutive ones approach. We see that from the perspective of worstcase complexity the Unguided Algorithm is inferior to the consecutive ones approach: while having the same worst-case runtime, it is applicable only to a smaller domain (top orders vs. weak orders). However, a point made in favor of the Guided Algorithm also applies here: The main strength of the Unguided Algorithm is its relative simplicity. It can be seen as a solution method for certain consecutive ones instances and due to this specialization does not require the full power of consecutive ones machinery. It is thus easier to implement and can be used in characterization proofs.3

3. Preliminary work with Dominik Peters indicates that the Unguided Algorithm can be used to characterize the single-peaked-or-caved domain: A total order A is single-peaked-or-caved with respect to A if either T

Incomplete Preferences in Single-Peaked Electorates

Input: A set of candidates C and a connected preference proﬁle of top orders P = (V1, . . . Vn). Output: An axis A or not single peaked.

1 foreach cstart C do

3 for i 1 . . . m do

4 foreach vote V P that has ai as its top-ranked candidate do

5 if A V = incompatible then

6 Continue with next cstart C in line 1.

7 else A A V

8 if |A| = i and i < m then

9 V Intersecting Vote(A)

10 if ai / V then

11 Continue with next cstart C in line 1.

12 Let x be a new candidate, distinct from those in C.

13 C {c V | c ai} {ai, x}

14 for k 1 . . . n do

15 V k Rep Top(Vk, C \ (A C ), x)

16 P (V 1, . . . , V n)[C ]

17 A axis returned by Guided Alg. with input (P , V [C ], ai, x)

18 if A = not single peaked then

19 Continue with next cstart C in line 1.

20 else A A A [C \ {x}]

21 return A

22 return not single peaked

Algorithm 2: The Unguided Algorithm

In the description of the algorithm we assume that the input preference proﬁle is connected. Let us consider a simple graph with vertices corresponding to candidates. We connect two vertices with an edge whenever the corresponding two candidates are both ranked in some top order. A proﬁle of top orders is called connected if this graph has only one connected component. This assumption does not limit the applicability: if two or more connected components exist in this graph, we can use the algorithm for each component (i.e., its respective candidates and votes) and concatenate the resulting axes in arbitrary order. The Unguided Algorithm (Algorithm 2) works as follows: First, we choose a candidate cstart which is going to be the leftmost candidate on the axis A. Since we have no guiding vote, each candidate might be placed at the leftmost position. Hence we loop over all candidates (line 1). The corresponding axis under construction is A = cstart . We now aim to complete this axis by adding candidates to the right in such a way that all votes are single-peaked with respect to this axis. To this end we employ the loop in line 3. In this loop (variable i) we infer from the already placed candidate ai (the i-th candidate on A from left) the candidate ai+1 (or even more

or its reverse is single-peaked with respect to A. This domain is clearly more general than the single-peaked domain, but less general than the single-peaked-on-a-circle domain (Peters & Lackner, 2017).

Fitzsimmons & Lackner

candidates farther to the right), or infer that A cannot be extended to a single-peaked axis and thus try another start candidate. Lines 4 to 7 are based on the following observation: Let us assume that at a certain point A = c1 c2 c3 and V = c3 c2 c4 c5 P. Since c3, the peak of V , is already contained in A, there is only one compatible extension of A: c1 c2 c3 c4 c5 . We formalize this extension operation with the operator:

Deﬁnition 5. Let A be an incomplete axis and V a top order. Furthermore, let V [C \ A] = D c 1 c 2 . . . c j E . We deﬁne A V = D A c 1 c 2 . . . c j E if V is possibly singlepeaked with respect to this axis and A V = incompatible otherwise.

The loop in line 4 considers all votes V that have candidate ai as their top-ranked candidate (i.e., their maximal element). If A V = incompatible then A cannot be extended to a complete, single-peaked axis and we consider the next cstart C in line 1. Otherwise, we obtain a new incomplete axis A A V . It might be the case that the (i + 1)st candidate on A has not yet been determined after these steps. The lines 8 to 20 deal with this case. As the input proﬁle is connected, there has to be at least one vote that ranks both a candidate on A and a candidate that has not been placed yet. The procedure Intersecting Vote in line 9 returns such a vote V with A V = and V \ A = . This procedure can be eﬃciently precomputed in such a way that it requires only O(m) time to provide an answer; details can be found in the proof of Theorem 5. Let V be a vote returned by Intersecting Vote. It holds that V s top-ranked candidate is not placed on A yet: If its top-ranked candidate were contained in A, then V would have been already considered in the ﬁrst part of the algorithm (lines 4 to 7). If V does not contain ai (and thus ai is ranked last in V ), A cannot be extended to a single-peaked axis (lines 10 and 11). Now, we employ the Guided Algorithm of Section 5.2 to ﬁnd a further extension of A. The main idea is to use V as a guiding vote and ﬁnd an axis for the candidates in {c V | c ai}. In principle, this axis can be found independently of the existing axis A. However, the leftmost and rightmost candidates have to be chosen with regard to external considerations: The leftmost candidate has to be ai, otherwise A and the newly obtain partial axis A could not be combined. For the rightmost candidate, we have to consider votes with candidates placed on the axis in future steps. The following example illustrates the issue.

Example 3. Let A = a , V1 = b c a and V2 = c d . The vote V1 intersects A and hence C = {a, b, c}. We employ the Guided Algorithm and might obtain A = a c b .4

Now observe that A A = A can no longer be extended in a way that it is single-peaked for V2. This would have been possible if c had been chosen as the rightmost candidate in A .

As we can see from this example, we sometimes have to force the rightmost candidate in A . We do this by adding an additional candidate x to every vote (line 14 to 16). Hence, our candidate set under consideration is at this point C {c V | c ai} {ai, x}. The new candidate x is now placed in each vote at the position of the highest-ranked candidate among those not contained in A C . This is done by the Rep Top function: Rep Top(V, D, x) ﬁnds the one candidate in vote V that is the highest-ranked among the candidates in D and replaces it with candidate x. By forcing this element x to be the rightmost candidate, we ensure that A is chosen with consideration to all votes with ranked candidates not in C .

4. Whether we obtain this axis or a b c depends on whether the algorithm prefers placing candidates to the left or to the right if both choices are possible.

Incomplete Preferences in Single-Peaked Electorates

Example 3 (continued). We apply Rep Top(V, D, x) to the votes V1 and V2 with candidate sets C = {a, b, c, x} and D = {d}. We obtain the votes V 1[C ] = b c a x and V 2[C ] = c x . Now, the Guided Algorithm can only return the axis a b c x .

We obtain a proﬁle P on the candidate set C . We now run the Guided Algorithm with input (P , V [C ], A , ai, x), i.e., we employ the Guided Algorithm for the proﬁle P and guiding vote V [C ]. Furthermore, we require that the leftmost candidate on the axis is ai and the rightmost is x. The Guided Algorithm either returns not single peaked or an axis A . If it returns not single peaked, the next cstart C is considered. Otherwise, we continue with the extended axis A A A [C \ {x}], i.e., candidate x is not placed on A.

Theorem 5. The Top Order Single-peaked Consistency problem can be solved in O(m2 n) time.

We refer the reader to the appendix, Section A.2, for the correctness proof of Algorithm 2 and its runtime calculations.

Example 4. Let us illustrate the Unguided Algorithm with a full example. Let P = (V1, V2, V3, V4) with V1 = b c a (as in Example 3), V2 = c d (also as in Example 3), V3 = f g h e a , and V4 = h g f . We assume that the algorithm starts with cstart = h, as this choice leads to a successful run. We have exactly one vote with h has its top-ranked candidate: V4. Thus, A A V4 = h h g f = h g f . We now look for votes with f as their top-ranked choice; there is again only one: V3. As before, A A V3 = h g f f g h e a = h g f e a . This is by Deﬁnition 5, since V3 is possibly single-peaked with respect to h g f e a . We now have reached the situation described in Example 3. Thus, using the Guided Algorithm, we complete the axis to A = h g f e a b c and see that P = (V1, V2, V3, V4) is possibly single-peaked with respect to this so found axis.

5.4 A 2-SAT-Based Algorithm

Theorem 2, Theorem 3, and Theorem 4 leave open the case of proﬁles of local weak orders which contain at least one total order. Here, we show that this case is also polynomial-time solvable.

Theorem 6. If the given proﬁle contains a total order, the Local Weak Order Singlepeaked Consistency problem can be solved in O(n m3) time.

We encode a Local Weak Order Single-peaked Consistency instance in a 2-SAT instance. The 2-SAT problem asks whether a Boolean formula in conjunctive normal form (a conjunction of disjunctions of literals) where each clause has size two (e.g., (a b) ( a c)) is satisﬁable. Solving 2-SAT requires only linear time (Aspvall, Plass, & Tarjan, 1979). The Boolean variables in our instance correspond to pairs of candidates, i.e., for each a, b C we have a variable ab. The intended meaning of these variables is that ab = true if and only if a is left of b on the axis. Now, for each vote V and triple a, b, c C, if a b and c b (a, b, c may form a v-valley), we add the clauses

(ba cb) and (1)

(ab bc) (2)

Fitzsimmons & Lackner

to the 2-SAT instance. These clauses correspond the requirement that b must not be placed between a and c. Finally, we add for each pair of variables a, b the clauses

(ab ba) ( ab ba), (3)

corresponding to an exclusive or operator. Solving the 2-SAT instance either yields the information that the instance is not satisﬁable or a true/false assignment to the variables. In the ﬁrst case, the proﬁle is not single-peaked (as shown in Lemma 3). In the second case, we obtain a relation A = {(a, b) : ab = true} which is a total order and our desired axis (as shown in Lemma 4). Since the instance contains at most O(n m3) clauses, we obtain the stated runtime.

Lemma 3. If P is single-peaked with respect to an axis A, then the corresponding 2-SAT instance is satisﬁable.

Proof. We construct a valid truth assignment as follows: If a b on A, then ab = true and ba = false. Clauses of the form (1) and (2) are satisﬁed because no v-valleys occur on A; Clauses of the form (3) are satisﬁed because v-valleys cannot occur (P is single-peaked with respect to an axis A).

Lemma 4. The relation A = {(a, b) : ab = true}, as returned by the 2-SAT algorithm, is a total order and P is single-peaked with respect to A.

Proof. First, we want to show that A is a total order. Asymmetry and totality follow immediately from (3). Towards a contradiction assume that A is not transitive, i.e., there exist three candidates x, y, z such that {(x, y), (y, z), (z, x)} A. Thus, xy = yz = zx = true and yx = zy = xz = false. Let V be a total order contained in P (there exists at least one). We distinguish three cases:

The last ranked candidate of x, y, z in V is y: By (1), it has to hold that (yx zy), which is not the case.

The last ranked candidate of x, y, z in V is x: By (2), it has to hold that (yx xz), which is not the case.

The last ranked candidate of a, b, c in V is c: By (1), it has to hold that (zy xz), which is not the case.

Thus, A is transitive. It remains to show that P is single-peaked with respect to A. Assume that there is a valley a b, c b in some vote and it holds that {(a, b), (b, c)} A. Due to this valley, our 2-SAT instance contains the clause (ba cb). Thus, (b, a) A or (c, b) A and ba = true or cb = true. Hence, ab = false or bc = false, which contradicts our assumption that {(a, b), (b, c)} A.

6. Other Single-Peaked Concepts for Weak Orders

We now turn to three other models of single-peaked preferences for weak orders Black singlepeaked and single-plateaued preferences, and at the end of the section, necessarily single-peaked preferences. For weak orders, it is more common to view a b as indiﬀerence instead of missing information (i.e., incompleteness). From the algorithmic point of view, which we had taken so

Incomplete Preferences in Single-Peaked Electorates

a b c d e f g

(a) Single-Plateaued

a b c d e f g

(b) Black Single-Peaked

a b c d e f g

(c) Possibly Single-Peaked

Figure 4: Overview of Single-Peakedness Models for Weak Orders

far, this distinction is irrelevant. From a conceptional point of view, it clearly makes a diﬀerence, in particular for the underlying assumption of voters true preferences. It may even be that both incompleteness and indiﬀerence are simultaneously be present in a voter s preference information; we however disregard this possibility. Let us start with the deﬁnition of single-peaked preferences as introduced by Black, which applies to weak orders as well.

Deﬁnition 6. A preference proﬁle P of weak orders is Black single-peaked with respect to an axis A if for every V P, A can be split at the most-preferred candidate (peak) of V into two segments X and Y (one of which can be empty) such that V has strictly increasing preferences along X and strictly decreasing preferences along Y .

In other words, for a weak preference order to be Black single-peaked it must have a single most-preferred candidate and can only contain indiﬀerence between at most two candidates at each position in the order. Otherwise the segments X and Y referred to in Deﬁnition 6 would not be strictly increasing/decreasing. A slightly weaker restriction than Black single-peakedness for weak orders is the singleplateaued restriction (Black, 1958, Chapter 5), which extends Black single-peakedness to allow voters to state multiple most-preferred candidates (i.e., a single plateau instead of a single peak).5 The model of possibly single-peaked preferences considered in this paper generalizes both single-plateaued and Black single-peaked preferences. Examples and visualizations of these three restrictions can be found in Figure 4. In this section, we have three main goals: In Section 6.1 we diﬀerentiate single-peakedness models with respect to the axiomatic properties they guarantee. In Sections 6.2 and 6.3 we show that the consecutive ones approach can also be used to solve the consistency problem for single-plateaued and for Black single-peaked preferences. Finally, in Section 6.4, we brieﬂy consider the concept of necessarily single-peaked preferences.

6.1 Transitive Majority Relations and Condorcet Winners

Preference proﬁles that satisfy either the Black single-peaked or single-plateaued restriction have several desirable properties. One of them is that both Black single-peaked and single-plateaued

5. We note that single-plateaued preferences are occasionally referred to as single-peaked preferences, e.g., in (Fishburn, 1973, Chapter 9).

Fitzsimmons & Lackner

preferences guarantee transitive majority relations (Black, 1948, 1958). To be precise, we say that candidate a is preferred to b by a (strict) majority if |V P : a b| > |V P : b a|; in this case we write a >m b, where >m denotes the majority relation. A transitive majority relation further guarantees the existence of one or more weak Condorcet winners. A candidate a is a weak Condorcet winner if there is no candidate b with b >m a. Upon closer inspection, the Black single-peaked and the single-plateaued restriction show diﬀerent characteristics; we refer the reader to Barber a (2007), who further discusses how the amounts of indiﬀerence permitted in these restrictions impact their properties. The gain in generality for possibly single-peaked preferences comes at a price: This condition is no longer restrictive enough to guarantee a transitive majority relation. This can be seen by considering the following simple proﬁle reproduced from Fishburn (1973, Table 9.1). Let P = (V1, V2, V3, V4, V5) with

V1 : b a c V2, V3 : c b a V4, V5 : a b c

The corresponding majority relation satisﬁes a >m c >m b >m a, and thus is clearly not transitive. Furthermore, no Condorcet winner exists. Note that P is possibly single-peaked with respect to the axis a b c and that this proﬁle is comprised of top orders. Thus, there exist preference proﬁles of top orders that are possibly single-peaked and do not have a transitive majority relation nor a Condorcet winner.

6.2 Single-Plateaued Proﬁles and Their Recognition

Single-plateaued preferences are a much more restrictive model than possibly single-peaked preferences since they are essentially Black single-peaked except that each preference order can have multiple most-preferred candidates (Black, 1958, Chapter 5). We ﬁrst provide a characterization of single-plateaued preferences, similar to the v-valley based characterization of possibly single-peaked preferences (Lemma 2). Since a preference order must be strictly increasing and then strictly decreasing with respect to an axis (except for its most-preferred candidates), we can again use the v-valley substructure. Furthermore, we will need an additional substructure to prevent two candidates that are ranked indiﬀerent in a voter s preference order from appearing on the same side of that voter s peak (plateau).

Deﬁnition 7. A preference order V contains a plateau with respect to an axis A if there exist candidates a, b C such that a and b are adjacent in A and V states a b. A preference order V contains a nonpeak plateau with respect to an axis A if there exist candidates a, b, c, C such that a b c on A and V states either a b c or c b a.

We can now state the following analogue of Lemma 2.

Lemma 5. Let P = (V1, . . . , Vn) be a proﬁle of weak orders. The following two statements are equivalent.

(i) The proﬁle P is single-plateaued with respect to A.

(ii) Every vote V P contains neither a v-valley nor a nonpeak plateau with respect to A.

Incomplete Preferences in Single-Peaked Electorates

Proof. Let P be a preference proﬁle of weak orders, and let A be an axis. If P is single-plateaued with respect to A then for every preference order V P, A can be split into segments X, Y , and Z such that V is strictly increasing along X, remaining constant along Y , and strictly decreasing along Z. Since v is only ever strictly decreasing along Z and Z is the rightmost segment of A, V cannot contain a v-valley with respect to A. For a nonpeak plateau to exist with respect to A there must exist candidates a, b, c C such that a b c in A and V states either a b c or c b a. We ﬁrst consider the case where V states a b c. Since V strictly prefers a to b and a to c, and both b and c are to the right of a on the axis, we know that both b and c must be in segment Z. However, V is strictly decreasing along Z, so V cannot have a nonpeak plateau of this form. We now consider the case where V states c b a. Since V strictly prefers c to a and c to b, and both a and b are to the left of c on the axis, we know that both a and b must be in segment X. However, V is strictly increasing along X, so V cannot have a nonpeak plateau of this form. For the other direction, assume that no preference order V P contains a v-valley with respect to A and no preference order V P contains a nonpeak plateau with respect to A. Since no preference order V P contains a v-valley with respect to A, we know from Lemma 2 that V is possibly single-peaked with respect to A. Since we also know that no preference order V P contains a nonpeak plateau with respect to A it is easy to see that V is single-plateaued with respect to A.

We now extend the consecutive ones approach from Section 5.1 to single-plateaued proﬁles. Since the nonpeak plateau substructure is needed in addition to the v-valley substructure, we modify Construction 1 so that if a preference order contains a nonpeak plateau with respect to an axis A, then when the columns of its corresponding preference matrix are permuted according to A the matrix will contain a row with the sequence 1 0 1 . Further notice that if a preference order ranks three candidates indiﬀerent to each other below its peak (plateau) that it will have a nonpeak plateau with respect to every possible axis. To handle this case in the extension to Construction 1 we need to ensure that its corresponding preference matrix will contain a row with the sequence 1 0 1 for every permutation of its columns.

Construction 2. Let P = (V1, . . . , Vn) be a proﬁle of weak orders over candidate set C with |C| = m. For each Vi we initially construct an m m binary matrix Xi as described in Construction 1. The following extensions to Construction 1 ensure that if Vi has a nonpeak plateau with respect to an axis A then when the columns of Xi are permuted according to A it will not have the consecutive ones property. If there exist three candidates a, b, c C such that Vi states a b c and they are not Vi s most-preferred candidates, then output a matrix that does not have the consecutive ones property. Otherwise, for each pair of candidates a, b C such that (i) Vi ranks a b and (i) a and b are not maximal in Vi, append three additional rows to the matrix Xi: to the column corresponding to a append 0 1 1 , to the column corresponding to b append 1 1 0 , to each column corresponding to a candidate strictly preferred to a and b append 1 1 1 , and to each column corresponding to a remaining candidate append 0 0 0 . After constructing a matrix Xi for each Vi, the matrices X1, . . . , Xn are row-wise concatenated to yield a matrix X.

Fitzsimmons & Lackner

Construction 1 ensures that no preference order contains a v-valley and the extensions made in Construction 2 ensure that no preference order contains a nonpeak plateau. So the following theorem can be shown by an argument similar to the proof of Theorem 3. Now the presence of v-valleys or nonpeak plateaus, not just v-valleys, is equivalent to a row containing the sequence 1 0 1 .

Theorem 7. The Weak Order Single-plateaued Consistency problem can be solved in O(m2 n) time.

6.3 Black Single-Peaked Consistency

Recall that a preference order is Black single-peaked with respect to an axis A if it is strictly increasing to a single most-preferred candidate (peak) and then strictly decreasing with respect to A, this is consequently a special case of single-plateaued preferences. So we again use the v-valley substructure to obtain a characterization result, but as before we need an additional substructure. Even if no preference order has a v-valley with respect to A it may not be Black single-peaked because it is indiﬀerent between two candidates on the same side of its peak or has more than one most-preferred candidate. We can handle the ﬁrst condition just mentioned with the nonpeak plateau substructure used in the previous section, but the second condition requires us to forbid any kind of plateau.

Lemma 6. Let P = (V1, . . . , Vn) be a proﬁle of weak orders. The following two statements are equivalent.

(i) The proﬁle P is Black single-peaked with respect to A.

(ii) Every vote V P contains neither a v-valley nor a plateau with respect to A.

We omit the proof, as the argument is very similar to the proof of Lemma 5. Now, we extend Construction 2 so that if a preference order contains a plateau with respect to an axis A, then when the columns of its preference matrix are permuted according to A the matrix will contain the sequence 1 0 1 . Since Construction 2 already ensures this for the case of nonpeak plateaus, our extended construction below only needs to add a condition for plateaus that contain the most-preferred candidates in a given preference order.

Construction 3. Follow Construction 2 except add the following condition while constructing a preference matrix Xi for each preference order Vi P. If there exist two candidates a, b C such that Vi states a b and they are Vi s most-preferred candidates, then output a matrix that does not have the consecutive ones property.

When a preference order has a unique most-preferred candidate and is single-plateaued, it is clearly also Black single-peaked. Construction 3 ensures that no preference order contains more than one most-preferred candidate the same way that Construction 2 ensures that no preference order contains three or more candidates that are all ranked indiﬀerent to each other and that are not the most preferred candidates, since this always results in a nonpeak plateau. So the following theorem can be shown by essentially the same argument as for Theorem 7, but using Lemma 6 instead of Lemma 5.

Theorem 8. The Weak Order Black Single-peaked Consistency problem can be solved in O(m2 n) time.

Incomplete Preferences in Single-Peaked Electorates

6.4 Necessarily Single-Peaked Preferences

The central deﬁnition of this paper is that of possibly single-peaked preferences. As mentioned in Section 3, one could also consider necessarily single-peaked preferences, i.e., incomplete preferences for which every extension is single-peaked. We conclude this section by considering this much more restrictive variant. For weak orders, we can give a clear answer how these two concepts compare: necessarily single-peaked preferences can be characterized as a subclass of single-plateaued preferences.

Proposition 2. A proﬁle of weak orders is necessarily single-peaked with respect to an axis A if and only if it is single-plateaued with respect to A in such a way that plateaus have a size of at most two.

Proof. Let P, a proﬁle of weak orders, be single-plateaued with respect to an axis A such that all plateaus have a size 2. It is easy to see that for each V P that every extension of V to a total order cannot contain a v-valley with respect to A. For the other direction, we consider two cases: (i) P is not single-plateaued with respect to A and (ii) P is single-plateaued with respect to axis A but a V P contains a plateau of size larger than two. In case (i), we use Lemma 5. There are two ways in which the single-plateaued property can be violated: a vote V contains a v-valley or a nonpeak plateau with respect to A. If V contains a v-valley, then none of its extensions is single-peaked with respect to A. If V contains a nonpeak plateau, then it is of the form p a b, where p is a maximal element of V , with a b p on A (or reversed). Let V be any extension of V for which p a b holds. Then V is not single-peaked with respect to A, and hence P is not necessarily single-peaked with respect to A. Now, consider case (ii). Let V P with a b c, all of which are maximal elements in V , i.e., we have a plateau of size at least three. Without loss of generality assume that a b c on A. Let V be any extension of V that satisﬁes a b and c b. Then V

contains a v-valley and thus P is not necessarily single-peaked with respect to A.

Interestingly, this plateau of size at most two deﬁnition is exactly the way Arrow (1951) deﬁned single-peakedness, introducing a slight deviation from Black s original deﬁnition (as mentioned by Dummett & Farquharson, 1961).

7. Discussion and Future Work

We have analyzed the T Single-peaked Consistency problem for T {Partial Order, Local Weak Order, Weak Order, Top Order, Total Order}. An overview of the results is displayed in Table 1. Despite the NP-completeness of Partial Order Single-peaked Consistency, we have found four fast algorithms for plausible application scenarios. The Guided Algorithm and the 2-SAT based algorithm each require a guiding vote. Such an order is likely to exist at least implicitly for large preference proﬁles. In the case that no guiding order exists, the consecutive ones approach and the Unguided Algorithm are applicable. Also, we have found that Partial Order Single-peaked Consistency is solvable in polynomial time if the axis is already part of the input. This covers a large spectrum of possible scenarios of real-world preferences where our algorithms could be applied.

Fitzsimmons & Lackner

T general with guiding vote Partial Order NP-c (Cor 1) NP-c (Thm 2) Local Weak O. NP-c (Thm 1) O(m3 n) (Thm 6) Weak Order O(m2 n) (Thm 3) O(m n) (Thm 4) Top Order O(m2 n) (Thm 5) O(m n) (Thm 4) Total Order O(m n) (Escoﬃer et al. (2008), also Thm 4) n/a

Table 1: Overview of the complexity results and algorithms for T Single-Peaked Consistency

7.1 Implementation

We implemented our consecutive ones-based algorithm for the recognition of possibly singlepeaked preferences for weak orders (and the extensions to the construction for single-plateaued and Black single-peaked preferences). The code is written in Python 3.7 and is available at https://github.com/zmf6921/incompletesp. We use a SAT solver for the consecutive ones instances. (This is a much simpler and more reliable approach than implementing the available linear-time algorithms and still yields very fast runtimes.) We ran the algorithm on all currently available proﬁles of weak orders available on Pref Lib.org (Mattei & Walsh, 2013); these are in total 379 toc-instances6. We found that none of these instances are possibly single-peaked. This highlights a disadvantage of the single-peaked domain: its poor robustness. Even a minor change in a single voter s preferences can violate the single-peaked condition. And although the possibly single-peaked domain is a more general restriction, this drawback remains. Given this fragility, the result is not surprising but leads us to ask the question of how close these proﬁles are to being possibly single-peaked. We discuss this research direction further below. On a more positive note, even large instances with > 1,000 candidates and instances with > 25,000 distinct votes could be solved in seconds (the maximum running time was 20.2 seconds, the average was 0.8 seconds, the median 0.02 seconds, processed on a 4GHz Intel i7 with 16 GB of RAM).

7.2 Top Orders and Scoring Rules

We would like to mention one particular application of our algorithms concerning a speciﬁc class of voting rules, so-called scoring rules. Scoring rules are speciﬁed by a family of scoring vectors. For an election over m candidates, a scoring rule uses the corresponding m-candidate scoring vector (α1, . . . , αm) to determine the winner(s). A vote c1 cm gives α1 points to c1, α2 points to c2, etc. The candidate(s) with the highest score win. Often, scoring vectors of the type (α1, . . . , αk, 0, . . . , 0) with α1 . . . αk > 0 are considered. For example, the voting in the Eurovision Song Contest uses the scoring vector (12, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, . . . , 0) (Ginsburgh & Noury, 2008). For such scoring vectors, top orders (with k ranked candidates) constitute full information for determining the winner. It is therefore debatable whether the input of such voting rules may be considered to be given as a proﬁle of total orders, as total orders contain problem-irrelevant information. Brandt et al. (2015) study the constructive coalitional weighted manipulation problem for scoring rules in single-peaked elections. The authors consider the axis to be part of the input (for good reasons as explained in their paper). The computation of such

6. At Pref Lib, proﬁles of weak orders are referred to as tied-order complete (toc) , c.f. http://www.preflib. org/data/format.php#toc.

Incomplete Preferences in Single-Peaked Electorates

an axis with existing algorithms is only possible if preferences are speciﬁed by total orders and thus contain problem-irrelevant information. If only relevant information is given, i.e., the input consists of top orders, algorithms such as those presented in this paper are required.

7.3 Future Research

Let us discuss some directions for future research. When discussing our implementation and the outcome of our Pref Lib analysis, we mentioned the lack of robustness of (possibly) singlepeaked proﬁles. This issue of robustness has been addressed by considering nearly single-peaked proﬁles, i.e., proﬁles that are close to being single-peaked according to some measure (Elkind, Faliszewski, & Slinko, 2012; Cornaz, Galand, & Spanjaard, 2012, 2013; Faliszewski, Hemaspaandra, & Hemaspaandra, 2014; Bredereck, Chen, & Woeginger, 2016; Erd elyi, Lackner, & Pfandler, 2017). This line of work is limited to proﬁles of total orders; an extension to possibly single-peaked proﬁles could further generalize the applicability of single-peakedness. The ﬁrst step in this direction has been taken by Menon and Larson (2016), who consider proﬁles of top orders in which most voters have single-peaked preferences. Furthermore, work on matrices that almost satisfy the consecutive ones property (see Section 5.1) is highly relevant for this purpose; we refer the reader to a survey by Dom (2009) for a literature overview. It would be of great interest to see how close to being possibly single-peaked the proﬁles on Pref Lib are. Finally, work by Durand (2003), Lackner and Lackner (2017), and Chen and Finnendahl (2018) analyzed the number of single-peaked proﬁles of total orders. To extend this work to proﬁles of partial orders could shed light on how much generality can be gained by moving from total orders to partial orders. Even more interesting would be a comparison of single-peaked concepts for weak orders (see Section 6). Clearly, the possibly single-peaked deﬁnition is more general than, e.g., the single-plateaued deﬁnition but a quantitative answer is missing.

Acknowledgements

This work is based on a conference paper by Lackner (2014) and a follow-up conference paper by Fitzsimmons (2015). Martin Lackner was supported by the Austrian Science Foundation FWF, grant P31890. Zack Fitzsimmons was supported in part by the National Science Foundation under grant no. CCF-1101452 and by a National Science Foundation Graduate Research Fellowship under grant no. DGE-1102937. The research was done in part while Zack Fitzsimmons was on research leave at Rensselaer Polytechnic Institute. The collaboration between the two authors of this paper has been supported by COST Action IC1205 on Computational Social Choice. We thank Edith Elkind, Piotr Faliszewski, Edith Hemaspaandra, David Narv aez, Stanis law Radziszowski, and the anonymous referees for their helpful comments and suggestions. We thank Dominik Peters for helpful discussions and the permission to use the Tik Z script that produced Figure 4.

Fitzsimmons & Lackner

Appendix A. Proof details

A.1 Correctness of the Guided Algorithm

We are going to prove that the Guided Algorithm (Algorithm 1) is correct. In the following, we write a b to denote that either a b or a b. We consider the Guided Algorithm at any given point during its runtime. In particular, we consider the sets AL and AR as constructed by the algorithm. Let Vg be the guiding vote in P.

Lemma 7. Let k [n], aℓ= maxk(AL), ar = maxk(AR), and cj {ci, . . . , cm}. It either holds that cj k ar or that cj k aℓ.

Proof. Without loss of generality we assume that aℓwas placed before ar. Towards a contradiction assume that both ar k cj and aℓ k cj. Let us consider the algorithm at the point when ar was placed (ci = ar for some i < i). We will show that (R1) is true and thus ar could not have been placed on the right-hand side. Recall condition (R1):

ci k min k (C>i) and max k (AL) k min k (C>i)

Since ci = ar k cj k mink(C>i ) and maxk(AL) = aℓ k cj k mink(C>i ), (R1) is true and ci could not have been placed on the right side of the axis.

Lemma 8. Let k [n] and cj = maxk(ci, . . . , cm). Furthermore, let a, a AR such that candidate a has been placed on AR before a . Then it either holds that a k cj or it holds that a k a.

Proof. We consider the algorithm at the point where a was placed on the right-hand side, i.e., in AR. At this point, condition (R2) had to be false; the fact that a k cj or a k a holds is a direct consequence.

Proposition 3. The Guided Algorithm (Algorithm 1) is correct, i.e., it outputs an axis if and only if the given preference proﬁle is single-peaked, and, furthermore, P is single-peaked with respect to any axis that is returned by the algorithm.

Proof. We ﬁrst show that if an axis A is found, the proﬁle P is single-peaked with respect to A. Note that the guiding vote Vg is single-peaked with respect to A, as the Guided Algorithm constructs A based on Vg. Towards a contradiction assume that there is a vote V P that is not single-peaked with respect to A. This means that there are three candidates a, b, c with order a b c on A, a b and c b. We have to distinguish six cases of how a, b, c are ordered by the guiding vote g:

a g b g c (a is placed ﬁrst, then b, then c; other candidates in arbitrary order): Let us consider the algorithm at the point when b is being placed, i.e., b = ci, and when the conditions for vote V are being checked. It holds that either a AL or a AR. If a AL, observe that condition (L2) is satisﬁed since a b and c b. Consequently, b has to be placed on the right side (left = false). Then it holds that a c b on the axis generated by the algorithm which contradicts our assumption that a b c holds. In the case that a AR condition (R2) is satisﬁed. This leads to a contradiction by the same argument.

c g b g a: This case is analogous.

Incomplete Preferences in Single-Peaked Electorates

a g c g b: Now we consider the point where c is being placed, i.e., c = ci, and when the conditions for vote V are being checked. It holds that either a AL or a AR. If a AL, observe that (R1) is satisﬁed and hence c has to be placed on the left side (right = false). Then it holds that a c b on the axis generated by the algorithm which contradicts our assumption that a b c holds. In the case that a AR, condition (L1) is satisﬁed and we obtain a contradiction by the same argument.

c g a g b: This case is analogous to the previous one.

b g c g a or b g a g c: Since b is placed on A before a and c, the resulting axis cannot be a b c, a contradiction.

For the other direction, let us show that if the algorithm returns not single peaked, then the proﬁle P is not single-peaked. First, let us observe under what conditions the algorithm returns not single peaked. There are four cases: Either conditions (R1) and (L1), (R1) and (L2), (R2) and (L1) or conditions (R2) and (L2) hold. These pairs of conditions may either hold for the same vote or for two distinct votes; we denote these two votes V and V although it might be that these two are the same.

While placing ci, condition (L1) holds for some vote V and condition (R1) holds for some vote V : We have the following ﬁve candidates in these conditions: ar = max V (AR), ci, cj = min V (C>i) in condition (L1) and aℓ= max V (AL), ci, c j = min V (C>i) in condition (R1). In Figure 5, the known information about the votes V and V is shown. Since condition (R1) and (L1) are symmetrical, we can assume without loss of generality that aℓis placed before ar. Thus, we can assume that the guiding vote is {cj, c j} g ci g ar g aℓ, as shown in the ﬁgure (the order of cj and c j is not relevant and thus can be arbitrary).

There are four types of axes possible that are compatible with the guiding vote Vg. (The order of candidates in sets is arbitrary.)

D aℓ ci {cj, c j} ar E : Vote V is not single-peaked with respect to any axis of this type (or their reverse).

D aℓ {cj, c j} ci ar E : Vote V is not single-peaked with respect to any axis of this type (or their reverse).

D aℓ ar {cj, c j} ci E : Vote V is not single-peaked with respect to any axis of this type (or their reverse).

D aℓ ar ci {cj, c j} E : Consider vote V and Lemma 7. Since aℓ c j it has to

hold that c j ar. Consequently, aℓ ar and ci ar. Thus, the candidates aℓ, ar, ci form a v-valley for vote V .

Since these are all possible axes, we can conclude that the proﬁle is not single-peaked.

While placing ci, condition (L2) holds for some vote V and condition (R2) holds for some vote V : This case is similar to the previous one. In particular, we use the same candidate variables. In Figure 6, the known information about the votes V and V is shown.

Fitzsimmons & Lackner

Guiding vote Vg Vote V Vote V

Figure 5: Conditions (L1) and (R1)

Guiding vote Vg Vote V Vote V

Figure 6: Conditions (L2) and (R2)

There are four types of axes possible that are compatible with Vg. (The order of candidates in sets is arbitrary.)

D aℓ ci {cj, c j} ar E : Vote V is not single-peaked with respect to any axis of this type (or their reverse).

D aℓ {cj, c j} ci ar E : Vote V is not single-peaked with respect to any axis of this type (or their reverse).

D aℓ ar {cj, c j} ci E : Consider vote V and Lemma 7. Since aℓ ci it has to hold that ci ar. Thus, the candidates aℓ, ar, cj form a v-valley for vote V .

D aℓ ar ci {cj, c j} E : Vote V is not single-peaked with respect to any axis of this type (or their reverse).

While placing ci, condition (L1) holds for vote V and condition (R2) holds for vote V : We have the following ﬁve candidates in these conditions: ar = max V (AR) ci, cj = min V (C>i) in condition (L1) and a r = max V (AR), ci, c j = min V (C>i) in condition (R2). In Figure 7, the known information about the votes V and V is shown. In the following arguments it is irrelevant which of cj and c j is placed ﬁrst. However, for ar and a r this is relevant. We will consider both possibilities (cases 1 and 2 in Figure 7). There are four types of axes possible that are compatible with either of these two guiding votes. (The order of candidates in sets is arbitrary.)

D {ar, a r} {cj, c j} ci E : Vote V is not single-peaked with respect to any axis of this type (or their reverse).

D {ar, a r} ci {cj, c j} E : Vote V is not single-peaked with respect to any axis of this type (or their reverse).

D ar {cj, c j} ci a r E : Both V and V are not single-peaked with respect to any axis of this type (or their reverse).

D ar ci {cj, c j} a r E : Here we have to distinguish whether ar or a r is placed ﬁrst (case 1 and 2 in Figure 7).

Incomplete Preferences in Single-Peaked Electorates

Guiding vote Vg Guiding vote Vg Vote V Vote V

(case 1) (case 2)

Figure 7: Condition (L1) and Condition (R2)

Case 1 (a r g ar): Lemma 8 applied to V implies that either (i) ar ci or (ii) ar a r. In both cases we encounter a valley with respect to vote V for the candidates {ar, a r, ci}. Case 2 (ar g a r): This case is similar to the previous. Lemma 8 applied to V implies that either (i) ar cj or (ii) a r ar. In both cases we encounter a valley with respect to vote V for the candidates {a r, ar, cj}.

We see that in both cases either V or V is not single-peaked with respect to any axis of this type (or their reverse).

While placing ci, condition (L2) holds for some vote and condition (R1) holds for some vote: This can be shown analogously to the previous case since (R1) and (L1) are symmetrical as well as (R2) and (L2), see Figure 3.

We have shown that if the algorithm returns not single peaked then the proﬁle P is indeed not single-peaked.

A.2 Runtime and Correctness for the Unguided Algorithm

Theorem 5. The Top Order Single-peaked Consistency problem can be solved in O(m2 n) time.

Proof. Let us ﬁrst discuss the runtime of Algorithm 2. Some functions have to be precomputed to achieve the O(m2 n) runtime, in particular the function Intersecting Vote. The function Intersecting Vote(A) returns a vote V with A V = and V \A = . We show that it suﬃces to compute a list of 2m votes to answer Intersecting Vote function calls in constant time. Let us ﬁrst make the following observation: Let c C. Consider the set of votes for which the sets {c C | c c} are maximal (with respect to ). If we consider a single-peaked axis, then candidates in such a set have to form a contiguous subsequence either directly left or directly right of c. Since these sets are maximal, only two of them can exist (assuming single-peakedness). Consequently, we compute these maximal sets for each candidate. If three or more exist for one candidate, we can terminate the algorithm already at this point. Also, if two maximal sets have a non-empty intersection, the algorithm terminates. (The candidates in the intersection would

Fitzsimmons & Lackner

have to lie left and right of c). Otherwise we store the (at most) two corresponding votes for each candidate. Let A = a1 . . . ai 1 ai , i.e., ai is the rightmost candidate in the incomplete axis A. The function call Intersecting Vote(A) can now be answered by considering the one or two maximal votes for ai. The function simply returns the vote where ai 1 is not ranked higher than ai. (It might be that both votes do not rank ai 1 higher than ai. In this case A cannot be extended to a single-peaked axis, but this is going to be detected by algorithm. Any of the two axes can be returned.) It remains to observe that ﬁnding the (at most two) maximal votes for a candidate c requires O(m n) time. This has to be done for every candidate and consequently this preprocessing requires O(m2 n) time. We can now analyze the runtime of the algorithm. The main loop (line 1) iterates over all m candidates. The loop in line 4 iterates over every vote at most once. Consequently, the operator is applied at most n times. Since A V can be computed in O(m) time, the lines 4 to 7 have a total runtime of O(m2 n). It remains to determine the runtime of the lines 8 to 20. Due to the preprocessing of the Intersecting Vote procedure we can obtain V in constant time. The proﬁle P can be generated in O(|C | n) time. Applying the Guided Algorithm requires O(|C | n) time as well (Theorem 4). Observe that after applying the Guided Algorithm the candidates in C are placed on the axis. Consequently, the Guided Algorithm is always applied to a disjoint set of candidates (except maybe ai). Hence for a ﬁxed cstart C, the total runtime of the Guided Algorithm is O(m n). Taking the loop in line 1 into account, we obtain a total runtime of O(m2 n). Let us now show that the Unguided Algorithm (Algorithm 2) is correct, i.e., it outputs an axis if and only if the given preference proﬁle is single-peaked and, furthermore, P is single-peaked with respect to any axis that is returned by the algorithm. If the algorithm outputs an axis, it is certainly single-peaked since this is tested for every vote in line 5. By the same argument, one can conclude that if the proﬁle is not single-peaked, the algorithm returns not single peaked. It remains to prove that the algorithm always returns a valid axis in case of a single-peaked proﬁle. Let us consider the algorithm at the time when cstart is the leftmost candidate of a valid axis. We show that the algorithm will ﬁnd a complete axis with cstart as leftmost candidate. First, observe that for every i in line 3 either there is a vote V with ai as its top-ranked candidate or the condition in line 8 is true. In the ﬁrst case, it is easy to verify that the operator adds candidates to the axis in the only possible way. In the second case, an intersecting vote is found as guaranteed by the connectedness condition. Then the Guided Algorithm is applied and the axis is extended by the candidates in C . It remains to verify that the resulting axis A is singlepeaked for all votes with a non-empty intersection with C . This is guaranteed by the x element, which ensures that candidates outside of A C are taken into account.

Arrow, K. (1951). Social Choice and Individual Values. John Wiley and Sons.

Aspvall, B., Plass, M., & Tarjan, R. (1979). A linear-time algorithm for testing the truth of certain quantiﬁed Boolean formulas. Information Processing Letters, 8(3), 121 123.

Aziz, H. (2014). Testing top monotonicity. Tech. rep. ar Xiv:1403.7625 [cs.GT], ar Xiv.org.

Incomplete Preferences in Single-Peaked Electorates

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

Barber a, S. (2007). Indiﬀerences and domain restrictions. Analyse & Kritik, 29(2), 146 162.

Barber a, S., & Moreno, B. (2011). Top monotonicity: A common root for single peakedness, single crossing and the median voter result. Games and Economic Behavior, 73(2), 345 359.

Bartholdi, III, J., Tovey, C., & Trick, M. (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. (1986). Stable matching with preferences derived from a psychological model. Operations Research Letters, 5(4), 165 169.

Baumeister, D., Faliszewski, P., Lang, J., & Rothe, J. (2012). Campaigns for lazy voters: Truncated ballots. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012), pp. 577 584. IFAAMAS.

Baumeister, D., & Rothe, J. (2012). Taking the ﬁnal step to a full dichotomy of the possible winner problem in pure scoring rules. Information Processing Letters, 112(5), 186 190.

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

Betzler, N., Bredereck, R., & Niedermeier, R. (2014). Theoretical and empirical evaluation of data reduction for exact Kemeny rank aggregation. Autonomous Agents and Multi-Agent Systems, 28(5), 721 748.

Betzler, N., & Dorn, B. (2010). Towards a dichotomy for the possible winner problem in elections based on scoring rules. Journal of Computer and System Sciences, 76(8), 812 836.

Betzler, N., Hemmann, S., & Niedermeier, R. (2009). A multivariate complexity analysis of determining possible winners given incomplete votes. In Proceedings of the 21st International Joint Conference on Artiﬁcial Intelligence (IJCAI 2009), pp. 53 58.

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

Black, D. (1958). The Theory of Committees and Elections. Cambridge University Press.

Booth, K., & Lueker, G. (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.

Boutilier, C., & Rosenschein, J. (2016). Incomplete information and communication in voting. 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. (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. (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.

Fitzsimmons & Lackner

Cantala, D. (2004). Choosing the level of a public good when agents have an outside option. Social Choice and Welfare, 22(3), 491 514.

Chen, J., & Finnendahl, U. (2018). On the number of single-peaked narcissistic or single-crossing 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.

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

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

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

De Gemmis, M., Iaquinta, L., Lops, P., Musto, C., Narducci, F., & Semeraro, G. (2010). Learning preference models in recommender systems. In Preference Learning, pp. 387 407. Springer.

Dery, L. N., Kalech, M., Rokach, L., & Shapira, B. (2014). Reaching a joint decision with minimal elicitation of voter preferences. Information Sciences, 278, 466 487.

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

Dom, M. (2009). Algorithmic aspects of the consecutive-ones property. In Bulletin of the European Association for Theoretical Computer Science, Vol. 98, pp. 27 59. EATCS.

Dummett, M., & Farquharson, R. (1961). Stability in voting. Econometrica, 29(1), 33 43.

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

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

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

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

Elkind, E., & Ismaili, A. (2015). OWA-based extensions of the chamberlin courant rule. In Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT 2015), pp. 486 502. Springer.

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

Incomplete Preferences in Single-Peaked Electorates

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 2016), pp. 4062 4065. IJCAI/AAAI Press.

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 single-peaked electorates. Journal of Artiﬁcial Intelligence Research, 58, 297 337.

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

Fagin, R., Kumar, R., Mahdian, M., Sivakumar, D., & Vee, E. (2006). Comparing partial rankings. SIAM Journal on Discrete Mathematics, 20(3), 628 648.

Fagin, R., Kumar, R., & Sivakumar, D. (2003). Comparing top k lists. SIAM Journal on Discrete Mathematics, 17(1), 134 160.

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., Hemaspaandra, E., Hemaspaandra, L., & 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.

Fishburn, P. (1973). The Theory of Social Choice. Princeton University Press.

Fitzsimmons, Z., & Hemaspaandra, E. (2015). Complexity of manipulative actions when voting with ties. In Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT 2015), pp. 103 119. Springer.

Fitzsimmons, Z. (2015). Single-peaked consistency for weak orders is easy. In Proceedings of the 15th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2015), pp. 127 140.

Fitzsimmons, Z., & Hemaspaandra, E. (2016). Modeling single-peakedness for votes with ties. In Proceedings of the 8th European Starting AI Researcher Symposium (STAIRS 2016), pp. 63 74. IOS Press.

Fulkerson, D., & Gross, G. (1965). Incidence matrices and interval graphs. Paciﬁc Journal of Mathematics, 15(5), 835 855.

Gaertner, W. (2002). Domain restrictions. In Arrow, K., Sen, A., & Suzumura, K. (Eds.), Handbook of Social Choice and Welfare, Volume 1, chap. 3, pp. 131 170. Elsevier.

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

Gibbard, A. (1973). Manipulation of voting schemes. Econometrica, 41(4), 587 601.

Ginsburgh, V., & Noury, A. (2008). The Eurovision song contest. Is voting political or cultural?. European Journal of Political Economy, 24(1), 41 52.

Habib, M., Mc Connell, R., Paul, C., & Viennot, L. (2000). Lex-BFS and partition reﬁnement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theoretical Computer Science, 234(1), 59 84.

Fitzsimmons & Lackner

Hemaspaandra, E., Hemaspaandra, L., & Rothe, J. (2016). The complexity of manipulative actions in single-peaked societies. In Rothe, J. (Ed.), Economics and Computation, pp. 327 360. Springer.

Hemaspaandra, E., Hemaspaandra, L. A., & Rothe, J. (1997). Exact analysis of Dodgson elections: Lewis Carroll s 1876 voting system is complete for parallel access to NP. Journal of the ACM, 44(6), 806 825.

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

Hsu, W.-L. (2002). A simple test for the consecutive ones property. Journal of Algorithms, 43(1), 1 16.

Konczak, K., & Lang, J. (2005). Voting procedures with incomplete preferences. In Proceedings of the 1st Multidisciplinary Workshop on Advances in Preference Handling (MPref 2005), pp. 124 129.

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 2014), pp. 742 748. AAAI Press.

Le Grand, R., Markakis, E., & Mehta, A. (2007). Some results on approximating the minimax solution in approval voting. In AAMAS 07, pp. 1185 1187.

Liu, H., & Guo, J. (2016). Parameterized complexity of winner determination in minimax committee elections. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, pp. 341 349. International Foundation for Autonomous Agents and Multiagent Systems.

Magiera, K., & Faliszewski, P. (2019). Recognizing top-monotonic preference proﬁles in polynomial time. Journal of Artiﬁcial Intelligence Research, 66, 57 84.

Masthoﬀ, J. (2015). Group recommender systems: Aggregation, satisfaction and group attributes. In Francesco Ricci, Lior Rokach, B. S. (Ed.), Recommender Systems Handbook. Springer.

Mattei, N., & Walsh, T. (2013). Preﬂib: A library of preference data. In Proceedings of the 3rd International Conference on Algorithmic Decision Theory (ADT 2013). Springer.

Mc Connell, R. M. (2004). A certifying algorithm for the consecutive-ones property. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 768 777. Society for Industrial and Applied Mathematics.

Meidanis, J., Porto, O., & Telles, G. P. (1998). On the consecutive ones property. Discrete Applied Mathematics, 88(1), 325 354.

Menon, V., & Larson, K. (2017). Computational aspects of strategic behaviour in elections with top-truncated ballots. Autonomous Agents and Multiagent Systems, 31(6), 1506 1547.

Menon, V., & Larson, K. (2016). Reinstating combinatorial protections for manipulation and bribery in single-peaked and nearly single-peaked electorates. In Schuurmans, D., & Wellman, M. P. (Eds.), Proceedings of the Thirtieth AAAI Conference on Artiﬁcial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA., pp. 565 571. AAAI Press.

Incomplete Preferences in Single-Peaked Electorates

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

Moulin, H. (1984). Generalized Condorcet-winners for single peaked and single-plateau preferences. Social Choice and Welfare, 1(2), 127 147.

Opatrny, J. (1979). Total ordering problem. SIAM Journal on Computing, 8(1), 111 114.

Peters, D. (2017). Recognising multidimensional Euclidean preferences. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence (AAAI 2017), pp. 642 648. AAAI Press.

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 2018), pp. 1169 1176. AAAI Press.

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

Pini, M., Rossi, F., Venable, K., & Walsh, T. (2011). Incompleteness and incomparability in preference aggregation: Complexity results. Artiﬁcial Intelligence, 175(7-8), 1272 1289.

Raﬃnot, M. (2011). Consecutive ones property testing: Cut or swap. In Conference on Computability in Europe, pp. 239 249. Springer.

Rothe, J., Spakowski, H., & Vogel, J. (2003). Exact complexity of the winner problem for Young elections. Theory of Computing Systems, 36(4), 375 386.

Satterthwaite, M. (1975). Strategy-proofness and Arrow s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2), 187 217.

Schafer, J. B., Frankowski, D., Herlocker, J., & Sen, S. (2007). Collaborative ﬁltering recommender systems. In The adaptive web, pp. 291 324. Springer.

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

Xia, L., & Conitzer, V. (2011). Determining possible and necessary winners under common voting rules given partial orders. Journal of Artiﬁcial Intelligence Research, 41(2), 25 67.