# recognizing_topmonotonic_preference_profiles_in_polynomial_time__5783c483.pdf

Recognizing Top-Monotonic Preference Proﬁles in Polynomial Time

Krzysztof Magiera and Piotr Faliszewski AGH University, Krakow, Poland krzys.magiera@gmail.com, faliszew@agh.edu.pl

We provide the ﬁrst polynomial-time algorithm for recognizing if a proﬁle of (possibly weak) preference orders is top-monotonic. Top-monotonicity is a generalization of the notions of single-peakedness and single-crossingness, deﬁned by Barber a and Moreno. Top-monotonic proﬁles always have weak Condorcet winners and satisfy a variant of the median voter theorem. Our algorithm proceeds by reducing the recognition problem to the SAT-2CNF problem.

1 Introduction

Condorcet paradox refers to situations where a group of rational individuals (i.e., a group of individuals where each can rank a set of objects from the best one to the worst one) has cyclic collective preference (under majority voting). For example, consider objects a, b, and c (referred to as candidates) and three individuals, v1, v2, and v3 (referred to as voters), with preference orders:

v1 : a b c, v2 : b c a, v3 : c a b.

A majority of the voters (v1 and v3) prefers a to b, a majority of the voters (v1 and v2) prefers b to c, and a majority of the voters (v2 and v3) prefers c to a. The fact that a Condorcet paradox can occur in preference aggregation is unfortunate. Indeed, if cyclic collective preferences could be avoided, then it would often be quite clear how to aggregate voters opinions. For example, in each election there would be a candidate (or, possibly, a group of candidates, if ties could happen) preferred by a majority of voters to all the other ones, and equally preferred among themselves; such candidates are known as (weak) Condorcet winners. One of the standard ways to avoid the Condorcet paradox is to restrict the domain of legal preference orders from all permutations of the candidates to some subset of such permutations. Indeed, a Condorcet domain is a set of allowed preference orders, such that, if one forms a preference proﬁle by choosing orders only from this set, then there

We thank the reviewers for very helpful comments. Piotr Faliszewski was supported by AGH University grant 11.11.230.337 (statutory research).

will certainly be a (weak) Condorcet winner (see, e.g., the overview of Gaerner [2001], or the work of Clearwater et al. [2015]). Two best-known examples of domain restrictions are the notions of single-peakedness [Black, 1958; Arrow, 1951] and single-crossingness [Mirrlees, 1971; Roberts, 1977] (formally, single-crossingness corresponds to a family of Condorcet domains). Under single-peaked preferences, we assume that the candidates can be arranged on a line, known as the societal axis (e.g., on the left-to-right political spectrum, or simply in the order of increasing numbers if we consider such an issue as, e.g., choosing the most comfortable temperature in a room). Then, a voter has single-peaked preferences if as we go along the societal axis, ﬁrst this voter s appreciation for the candidates increases and then decreases. On the other hand, a preference proﬁle is single-crossing if the voters can be ordered in such a way that as we progress from one end of the voter spectrum to the other, then for each pair of candidates their relative order can change at most once. (The left-right political spectrum again provides an example: if the voters have views that can be arranged on the left-to-right spectrum, and the candidates can also be associated with such views, then for each two candidates a and b, such that a is more left-wing and b is more right-wing, the extreme-left voters certainly prefer a to b, extreme-right voters certainly prefer b to a, and as we progress from one extreme to the other, we expect only one swap.) Saporiti and Tohm e [2006] discuss several settings where single-crossing preferences arise in practice (the ﬁrst motivating examples of Mirrlees [1971] and Roberts [1977] regarded taxation). Not only is it known that the Condorcet paradox cannot occur if the voters have single-peaked or single-crossing preferences, but also many other negative effects cannot happen in these cases (e.g., the famous impossibility theorems of Arrow [1951] and of Gibbard [1973] and Satterthwaite [1975] do not hold under these restrictions).1 In this paper we consider a far more recent domain restriction than either single-peakedness or single-crossingness, namely the notion of top-monotonic preferences of Barber a and Moreno [2011]. Top monotonicity has many advantages as, for example, it generalizes both the notions of single-

1Results of Arrow and of Gibbard and Satterthwaite are often interpreted as saying that in general no perfect voting rule exists. For single-peaked or single-crossing preferences, such a perfect voting rule simply elects the (weak) Condorcet winners.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

peakedness and single-crossingness while still guaranteeing existence of (weak) Condorcet winners, and it is applicable to the settings where voters have weak preferences.2 However, it also has drawbacks. One is that top-monotonic preferences are hard to deﬁne intuitively (and, indeed, this is why we refrain from describing them here on the intuitive level and point the reader to the formal deﬁnition in Section 2). Another one is that so far no polynomial-time algorithm for recognizing top-monotonic preferences was known (even though there is a number of algorithms for recognizing single-peaked preferences [Bartholdi and Trick, 1986; Escofﬁer et al., 2008] and single-crossing preferences [Elkind et al., 2012; Bredereck et al., 2013; Cornaz et al., 2013]). Our main contribution is providing the ﬁrst such algorithm. (However, we mention that there are natural domain restrictions for which the recognition problem is NP-hard [Peters, 2017].) The ﬁrst algorithmic study of top monotonicity is due to Aziz [2014]. While he did not give a recognition algorithm, he has shown that the problem of deciding if a proﬁle of partial preference orders can be extended to a top-monotonic one is NP-hard (similar results were earlier obtained for singlepeakedness [Lackner, 2014] and single-crossingness [Elkind et al., 2015]). He also related the problem of recognizing top-monotonic proﬁles to the non-betweenness problem [Guttmann and Maucher, 2006]. Our algorithm uses different ideas and is based on a somewhat intricate reduction to the SAT-2CNF problem (i.e., the problem of testing if a logical formula in conjunctive normal form with at most two literals per clause is satisﬁable, well known to be solvable in polynomial time [Krom, 1967]). This is interesting both technically (indeed, noting that our approach can produce SAT2CNF formulas requires some insight) and because many other methods for recognizing elections in restricted domains rely on the consecutive-ones problem3 (see, e.g., the works of Peters and Lackner [2017] or Elkind and Lackner [2015]). The SAT-2CNF problem might have similar impact on the design of further algorithms recognizing domain restrictions and we recommend it as a useful tool for such tasks. We conclude by noting that there is yet another reason why having a polynomial time algorithm for recognizing top-monotonic preferences is important. Indeed, many NPhard voting-related problems turn out to be polynomial-time solvable under various restricted domains. This was noted, e.g., by Conitzer [2009] for the case of vote elicitation, by Faliszewski et al. [2011; 2014] and by Magiera and Faliszewski [2014] for election control (i.e., for problems that model affecting the election result by changing its structure), by Brandt et al. [2015] for election bribery (i.e., problems where we can change some number of votes to ensure a given candidate s victory), and most importantly by many researchers for the case of winner determination (as a few examples, we mention the results of Brandt et al. [2015] for all

2Lackner [2014] and Elkind et al. [2015] also apply notions of single-peakedness and single-crossingness to partial orders (including weak ones) and encounter some computational hardness results. 3In this problem, we are given a binary matrix and we ask if we can permute its rows so that in each column the entries with ones are consecutive [1976].

the Condorcet consistent rules and the results of Betzler et al. [2013], Cornaz et al. [2012], and Skowron et al. [2015] for the Chamberlin Courant rule). Our results may inspire researchers to seek positive algorithmic consequences for top-monotonic preference proﬁles.

2 Preliminaries

We mostly adopt the notation of Barber a and Moreno [2011]. We let A be a (ﬁnite) set of alternatives (also called candidates) and we let N = {1, . . . , n} be a set of n agents (also called voters). We denote the preference order of agent i over the set of alternatives by i (note that we take them to be weak orders). For each pair of alternatives x, y A, we write x i y if the i-th agent weakly prefers alternative x over y. We use the strict order ( i) and equality ( i) notations deﬁned for each x, y A as follows:

1. x i y holds if x i y and it is not the case that y i x;

2. x i y holds if x i y and y i x.

A preference proﬁle is a collection of preference orders of the agents from N; we write = ( 1, . . . , n) to denote a preference proﬁle of weak orders, and = ( 1, . . . , n) for a proﬁle of strict orders (i.e., one where there is no agent i and distinct candidates x, y A such that x i y). Before we deﬁne top-monotonic preferences, let us give formal deﬁnitions of single-peaked and single-crossing ones.

Deﬁnition 1 (Black [1958], Arrow [1951]). A preference proﬁle is single-peaked if there exists a linear order > over the set of the alternatives (the societal axis), such that for each three alternatives x, y, and z, if either it holds that x > y > z or z > y > x, then for each agent i N we have that x i y = y i z.

Intuitively put, the deﬁnition says that each agent i can choose his or her most preferred candidate arbitrarily, but then this agent must choose the following ones so that for each j {1, . . . |A|}, the set of top j candidates according to i forms a consecutive block within the societal axis. (In consequence, for each agent the candidate ranked last is either the maximum or the minimum element of >.)

Deﬁnition 2 (Mirrlees [1971] and Roberts [1977]). A proﬁle = ( 1, . . . , n) is single-crossing with respect to an ordering of voters ( 1, . . . , n) if for each two alternatives x and y such that x 1 y, there is a number tx,y such that {i N | x i y} = {1, . . . , tx,y}. Proﬁle is singlecrossing if it is single-crossing with respect to some ordering of the voters.

That is, a proﬁle is single-crossing if it is possible to order the voters so that, as we move along this order, the relative order of each two candidates changes at most once.

Example 1. Consider candidate set {a, b, c, d} and the proﬁle of the following preference orders:

a 1 b 1 c 1 d, b 2 a 2 d 2 c, d 3 c 3 b 3 a.

It is single-crossing (for the natural order of the voters) but not single-peaked for any axis (because each of the three agents ranks a different candidate last).

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

For candidate set {a, b, c, d, e}, consider a proﬁle with the following four preference orders:

c 1 b 1 d 1 a 1 e, c 2 d 2 b 2 a 2 e, c 3 b 3 d 3 e 3 a, c 4 d 4 b 4 e 4 a.

It is single-peaked with respect to the axis a > b > c > d > e (indeed, for each agent i and each j {1, . . . , 5}, the top j candidates ranked by i form a consecutive block on this axis), but it is not single-crossing (a single-crossing ordering would have to put agent 1 next to 2, 3 next to 4, 1 next to 3, and 2 next to 4; fulﬁlling these conditions simultaneously is impossible). We are ready to deﬁne top-monotonic preferences [Barber a and Moreno, 2011]. For all i N and for each S A, we denote by ti(S) the set of top choices of the i-th agent among the alternatives from S. That is, ti(S) = {x S | x i y for all y S} and we call it the top of i in S according to . Let T = S i N ti(A). For each preference proﬁle , let A( ) be the family of sets containing A itself and all triples of distinct alternatives where each alternative is top in A for some agent i N according to (i.e., the triples in A( ) consist of the candidates from T, but A( ) also contains A). Deﬁnition 3 (Barber a and Moreno [2011]). A preference proﬁle is top-monotonic if there exists a linear order > over the set of the alternatives, such that:

(1) ti(A) is a ﬁnite union of closed intervals for all i N.4

(2) For all S A( ), for all i, j N, all x ti(S), all y tj(S), and all z S, we have that:

[x > y > z z > y > x] = y i z, if z ti(S) tj(S), y i z, if z / ti(S) tj(S).

Deﬁnition 4. A linear order > over the set of alternatives is a top-monotonic order of a preference proﬁle if is topmonotonic and > fulﬁlls condition (2) from Deﬁnition 3. The following example, provided by Barber a and Moreno [2011], shows that there is a proﬁle that is topmonotonic but neither single-peaked nor single-crossing (the fact that every single-peaked or single-crossing proﬁle is topmonotonic is also shown in their work). Example 2. Consider candidate set {a, b, c, d} and proﬁle of three preference orders:

a 1 b 1 c 1 d, c 2 d 2 b 2 a, d 3 c 3 a 3 b.

Note that c is preferred to each other candidate by a majority of the agents. The proﬁle is not single-peaked because there are three alternatives that are ranked last (a, b, and d). It is not single-crossing because agents 1 and 3 would have to be next to each other (because of the alternatives a and b), agents 2 and 3 would have to be next to each other (because of alternatives b and c), and agents 1 and 2 would have to be next to each other (because of alternatives c and d), which

4Since we assumed A to be a ﬁnite set, this part of the deﬁnition is always trivially satisﬁed. Barber a and Moreno consider also more general sets of alternatives and to indicate the generality of their deﬁnition we decided to keep this requirement in the text.

is impossible. However, the proﬁle is top-monotonic with respect to the order a > b > c > d. To see that the proﬁle is top-monotonic, note that A( ) = {{a, b, c, d}, {a, c, d}}. We have to check each S A( ) and each two agents i and j. Let us take S = {a, c, d}, i = 1 and j = 2. We have x t1(S) = {a}, y t2(S) = {c}, and we take z = d. It holds that a > c > d and z = d / t1(S) t2(S) = {a, c}, so it is required that c 1 d, and this indeed holds. Checking top-monotonicity of the proﬁle using the deﬁnition would require checking all the remaining combinations of S, i, j, and z.

3 Results The problem of determining a top-monotonic order of a preference proﬁle is as follows: Given a ﬁnite set of alternatives A, a ﬁnite set of agents N, and a preference proﬁle (for the agents in N) over A, ﬁnd a top-monotonic order of or decide that no such order exists. In this section we provide an algorithm for this problem (we use notation as in Section 2). The following deﬁnition, and Lemma 1 a bit later, constitute an interface between the notion of top-monotonicity and our main algorithm, which reconstructs the top-monotonic order from allowed orders over triples of candidates. Deﬁnition 5. For each triple of distinct alternatives S = {x, y, z} A and each pair of agents i, j N, we deﬁne the set of legal orderings, denoted by Li,j S , to be the set of ordered sequences of alternatives x, y, z, such that for each sequence σ = (σ1, σ2, σ3) where {σ1, σ2, σ3} = S, all the following criteria are met: [σ1 ti(S) and σ2 tj(S)] = σ2 i σ3, if σ3 ti(S) tj(S) σ2 i σ3, if σ3 / ti(S) tj(S) (1)

[σ1 tj(S) and σ2 ti(S)] = σ2 j σ3, if σ3 ti(S) tj(S) σ2 j σ3, if σ3 / ti(S) tj(S) (2)

[σ3 ti(S) and σ2 tj(S)] = σ2 i σ1, if σ1 ti(S) tj(S) σ2 i σ1, if σ1 / ti(S) tj(S) (3)

[σ3 tj(S) and σ2 ti(S)] = σ2 j σ1, if σ1 ti(S) tj(S) σ2 j σ1, if σ1 / ti(S) tj(S) (4)

[σ1 ti(S) and σ3 i σ2] [σ1 tj(S) and σ3 j σ2] [σ3 ti(S) and σ1 i σ2] [σ3 tj(S) and σ1 j σ2]

= σ2 / T (5)

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

To illustrate how the set of legal orderings is constructed, let us consider the following example. We take S = {x, y, z} and two agents i and j with preference orders x i y i z and z j x j y. Now we need to consider six different orderings of candidates x, y, z. Let us consider ordering σ = (x, z, y). We can see that it does not satisfy condition (1) as x ti(S), z tj(S) but z i y is not true. Similarily, if we consider ordering σ = (x, y, z), and if we assume that x, y, z T, then we can see that it does not satisfy condition (5) as z tj(S) and x j y (so the left-hand side of the implication is true) but y T. On the other hand, if we consider ordering σ = (z, x, y) then we can see that it satisﬁes all the ﬁve conditions and therefore is going to be a part of the set of legal orderings Li,j S . By analyzing the remaining three possible orderings we get the complete set of legal orderings for the setup under consideration, Li,j S = {(z, x, y), (y, x, z)}. Let QT be a family of sets of legal orderings for every triple x, y, z such that x, y, z T and every i, j N (recall that T is the set of candidates that are ever ranked on the top by some agent). Let QNT be another family of sets of legal orderings, for every triple x, y, z, where x, y T and z (A \ T), and every i, j N such that x ti(A) and y tj(A). Note that for both deﬁnitions we allow for agents i and j to be the same. In other words, family QT regards sets of legal orderings for all agents and all triples of candidates that appear on top of some preference orders, whereas QNT is deﬁned analogously, but for triples of candidates that contain two candidates from tops of some preference orders and one candidate that never appears on top (of any preference order).

Lemma 1. Let A be a set of alternatives, N be a set of agents, and be a preference proﬁle over A. Let Q = QT QNT . There exists a linear order > over the set of alternatives such that for each set X Q, there exists an element σ = (σ1, σ2, σ3) X such that σ1 > σ2 > σ3, if and only if is top-monotonic and > is a top-monotonic order over .

We omit the proof of Lemma 1 due to restricted space (in essence, Deﬁnition 5 and Lemma 1 jointly follow quite closely the deﬁnition of top-monotonic preferences, but the detailed proof, available upon request, is rather lengthy). The greatest advantage of using Lemma 1 and Deﬁnition 5 over directly applying Deﬁnition 3 is that it allows us to focus on sets of three candidates only (Deﬁnition 3 also uses the whole set A since A A( )). This property is crucial for our technique. Due to limited space, we present a proof for the following simpler variant of our main theorem. The full proof uses a very similar approach (we comment on this later).

Theorem 2. Let A be a set of alternatives, N be a set of agents, and be a preference proﬁle such that every alternative from A is top in A of some i N. The problem of determining if a top-monotonic order of exists (and computing it) is polynomial-time solvable.

Proof. Due to Lemma 1, it is sufﬁcient to demonstrate that ﬁnding an order > over A, such that for each X Q there exists σ = (σ1, σ2, σ3) X such that σ1 > σ2 > σ3, can be done in polynomial time. From now on we focus on this task.

Since each of the alternatives is a top for some i N (with respect to A), we have T = A and Q = QT . Let us now consider some set of orderings from QT . As they all correspond to triples of alternatives from T, there are only a few possible cases of how they may relate to each other in preference orders of pairs of agents. Let us take some three alternatives x, y, z T; there are 21 different combinations of pairs of preference orders that we need to consider (see second column of Table 1). All these combinations have their entries in Table 1, precomputed according to Deﬁnition 5. To obtain a set of legal orderings for some triple of candidates S and some agents i and j, it sufﬁces to assign these candidates to variables x, y, z and choose an entry in Table 1 corresponding to the preference orders of agents i and j. With Table 1 available, we can compute the set QT by looking up appropriate values. We illustrate this process with the example below.

Example 3. Let the set of alternatives be A = {a, b, c, d} and let the preference proﬁle be as follows (N = {1, 2}):

a 1 b 1 c 1 d, c 2 d 2 a 2 b.

We see that T = {a, b, c, d} = A , as each of the alternatives is on top for some agent. We have four possible triples of alternatives and three possible pairs of agents (note that we can make a pair that consists of the same two agents). Let us start with triple {a, b, c} and agents 1 and 2. We get the following relation between alternatives from this triple: a 1 b 1 c and c 2 a 2 b, which matches rule no. 4 from Table 1 (where x c, y a and z b) and generates the following set of legal orderings:

{(a, c, b), (c, a, b), (b, c, a), (b, a, c)}.

Similarly, if we now take triple {a, b, d} and agents 1 and 2, the relation looks as follows: a 1 b 1 d and d 2 a 2 b, which matches rule no. 10 (with x a, y b and z d). Therefore it generates the set of legal orderings {(b, a, d), (d, a, b)}. If we follow in similar steps for triples {a, c, d} and {b, c, d}, we will match rule no. 14 for the former and rule no. 6 for the latter, generating the two corresponding sets of legal orderings ({(a, c, d), (d, c, a)} and {(b, c, d), (d, c, b)}). On top of that, we have to consider pairs that are made of the same two agents (that is 1 and 1; 2 and 2). As a result, family Q will have 12 elements and will be:

Q = {{(a, c, b), (c, a, b), (b, c, a), (b, a, c)},

{(b, a, d), (d, a, b)},

{(a, c, d), (d, c, a)},

{(b, c, d), (d, c, b)},

{(b, a, c), (b, c, a), (c, a, b), (a, c, b), (c, b, a), (a, b, c)},

{(b, a, d), (a, b, d), (d, a, b), (d, b, a)},

{(c, a, d), (a, c, d), (d, a, c), (d, c, a)},

{(c, b, d), (b, c, d), (d, b, c), (d, b, a)},

{(c, b, a), (c, a, b), (a, b, c), (b, a, c)},

{(d, b, a), (d, a, b), (d, b, c), (b, a, d)},

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

Comb. of agents i, j N Set of legal orderings 2CNF ordering formula

1 x i y i z and x j y j z {(y, x, z), (x, y, z), (z, x, y), (z, y, x)} (xz zy) (yz zx) 2 x i y i z and x j y j z {(y, x, z), (x, y, z), (z, x, y), (z, y, x)} (xz zy) (yz zx) 3 x i y i z and x j y j z {(y, x, z), (x, y, z), (z, x, y), (z, y, x)} (xz zy) (yz zx) 4 x i y i z and x j y j z {(y, x, z), (x, y, z), (z, x, y), (z, y, x)} (xz zy) (yz zx) 5 x i y i z and x j z j y {(y, x, z), (z, x, y)} (xy xz) (yz zx) (yx zy) 6 x i z i y and x j y j z {(y, x, z), (z, x, y)} (xy xz) (yz zx) (yx zy) 7 x i y i z and y j x j z {(y, x, z), (x, y, z), (z, x, y), (z, y, x)} (xz zy) (yz zx) 8 y i x i z and x j y j z {(y, x, z), (z, x, y)} (xy xz) (yz zx) (yx zy) 9 x i y i z and y j z j x {(x, y, z), (z, y, x)} (xy zx) (xz zy) (yz yx) 10 z i x i y and x j y j z {(y, x, z), (z, x, y)} (xy xz) (yz zx) (yx zy) 11 y i z i x and x j y j z {(y, z, x), (x, z, y)} (xy yz) (xz yx) (zx zy) 12 x i y i z and z j y j x {(x, y, z), (z, y, x)} (xy zx) (xz zy) (yz yx) 13 x i y i z and x j y j z {(y, x, z), (z, x, y)} (xy xz) (yz zx) (yx zy) 14 x i y i z and y j x j z {(x, z, y), (y, z, x)} (xy yz) (xz yx) (zx zy) 15 z i x i y and x j y j z {(y, x, z), (x, y, z), (z, x, y), (z, y, x)} (xz zy) (yz zx) 16 x i y i z and x j y j z {(y, x, z), (x, y, z), (z, x, y), (z, y, x)} (xz zy) (yz zx) 17 x i y i z and x j y j z {(y, x, z), (x, y, z), (z, x, y), (z, y, x)} (xz zy) (yz zx) 18 x i y i z and x j z j y {(y, x, z), (z, x, y)} (xy xz) (yz zx) (yx zy) 19 x i y i z and x j y j z {(y, x, z), (y, z, x), (z, x, y), (x, z, y), (z, y, x), (x, y, z)} n/a 20 x i y i z and x j y j z {(y, x, z), (y, z, x), (z, x, y), (x, z, y), (z, y, x), (x, y, z)} n/a 21 x i y i z and x j y j z {(y, x, z), (y, z, x), (z, x, y), (x, z, y), (z, y, x), (x, y, z)} n/a

Table 1: All possible settings of pairs of agents from QT , with a corresponding sets of legal orderings (third column). The last column shows a 2CNF representation of each ordering formulas (note that we can write yx instead of (xy)).

{(d, c, a), (d, a, c), (a, c, d), (c, a, d), (a, d, c), (c, d, a)},

{(b, c, d), (c, b, d), (d, c, b), (d, b, c)}}

Taking order b > a > c > d, we see that for each set X Q there is at least one sequence σ = (σ1, σ2, σ3) X such that σ1 > σ2 > σ3 (corresponding items for each set are underlined on the listing above). By Lemma 1, we conclude that is top-monotonic and > is its top-monotonic order.

Set Q consists of |N|2 |A| 3 elements, where each element is of the form of one of the sets from the third column of Table 1. We want to ﬁnd a linear order > over the set of alternatives such that for each X Q we can ﬁnd at least one sequence σ = (σ1, σ2, σ3) X with σ1 > σ2 > σ3. It turns out that we can express this problem as an instance of the SAT-2CNF problem. To illustrate this approach, let us consider rule no. 5 from Table 1, with output {(y, x, z), (z, x, y)}. If the desired order > exists, it has to satisfy condition:

(y > x > z) (z > x > y) (6)

We can create a similar formula for each set of legal orderings from Q, and then expect the order > (if it exists) to satisfy the conjunction of these formulas. The crucial observation is that Eq. (6) (as well as formulas corresponding to all the other rules from Table 1) can be expressed in conjunctive normal form with two literals per clause (2CNF). To this end, we take our logical variables to be xy, xz, and yz and we interpret them as representing appropriate relations under order > (e.g., xy is true if x > y holds; we also write, e.g., zx as an abbreviation for xz). Then, Eq. (6) can be equivalently expressed as:

(yx xz yz) (zx xy zy)

or, equivalently, as:

( xy xz yz) ( xz xy yz).

This formula, on the other hand, is true if and only if the following one is (see comments below):

(xz xy) (yz xz) ( xy yz). (7)

To check that the two formulas above are, indeed, equivalent, one may try all possible truth assignments for our variables. For example, if we take the following (1 denotes logical truth and 0 denotes falsity):

xy = 1, xz = 1, and yz = 0

then both formulas evaluate to 0, whereas if we take:

xy = 0, xz = 1, and yz = 1

then they both evaluate to 1. Formula (7) is in the 2CNF form and, in fact, we can represent each of the possible sets of legal orderings using 2CNF formulas, as presented in Table 1 (the only exception is that rules 19, 20, and 21 do not impose any restrictions on the orderings and, thus, do not generate formulas at all; we show later why this does not affect the properties of the order that we want to calculate).5 We now show that a top-monotonic order exists if and only if the global ordering formula is satisﬁable.

Observation 1. A top-monotonic order for exists if and only if there is an assignment for the variables that satisﬁes the global ordering formula.

5The reader may wonder how we derived Formula (7) from Formula (6), or how we deduced that it can be translated to an equivalent 2CNF form. We are afraid that wishful thinking is our only response here; we wanted to ﬁnd a 2CNF formula and we made a brute-force search for one that would work.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

To prove this result, we ﬁrst note that if has a topmonotonic order then the global ordering formula is satisﬁable. Let > be this top-monotonic order. Now consider a variable assignment for the global ordering formula to be such that for each two candidates p and q, we set the literal pq = 1 if p > q (note that it may, in fact, mean setting variable qp to 0, depending which one of pq and qp is used as a variable in the global ordering formula and which one is represented as its negation). It is easy to see that such a variable assignment is a valid solution for the global ordering formula. Now it remains to show that if there is a satisfying assignment for the variables of the global ordering formula, then the proﬁle is top-monotonic. Let us assume that the global ordering formula has a satisfying assignment and let relation > be deﬁned for each pair of alternatives p, q A as follows: We set p > q exactly if the literal pq evaluates to 1. By deﬁnition, relation > satisﬁes the global ordering formula and we only need to show that it, indeed, is an order over A. We show that this is the case, by considering the three requirements that a strict order must satisfy:

(a) Relation > is irreﬂexive, because we do not have literals of the form xx in our global ordering formula.

(b) Relation > is assymetric, because for each x, y A, if x > y then it is not the case that y > x because for each x, y A, xy yx and, so, it cannot be that both xy and yx are set to 1 at the same time.

(c) Relation > is transitive, that is, for every triple x, y, z A if x > y and y > z then x > z. This comes from the fact that for every triple x, y, z A we need to satisfy a formula that corresponds to a set of legal orderings. It is clear that any element from the set of legal orderings has to satisfy the transitivity condition (as such an element represents an order of alternatives). The only exception is when a triple x, y, z A matches either of the rules 19, 20, or 21 from Table 1 for every possible pair of agents i, j N. However, in such a case it is easy to see that it must be the case that y i z for every i N. Therefore we can ignore this case as alternatives y and z are indistinguishable form each other for all the agents. We pick one of them to use in the algorithm (and remove the other one from the proﬁle); if it turns out that a topmonotonic order exists, then we place these candidates next to each other in this order (the algorithm computes the position of one of them in the top-monotonic order, and the other can be put on its either side).

So far, we have not yet argued that > is a total order and, indeed, it may be partial. We let > be a linear extension of > . Due to order-extension principle, since > is a strict partial order, a linear extension > of it exists. Since > satisﬁes the global ordering formula (as it is an extension of > ) and it is a linear order, > is a top-monotonic order for . Finally, we note that, since the global ordering formula is in conjunctive normal form with at most two variables per clause, there is a simple polynomial-time algorithm that checks if it is satisﬁable and, if so, produces a satisfying assignment. Further, the formula itself is of length polynomially bounded in the number of candidates and agents (we need

O(N 2 |A|3) subformulas from Table 1, with at most O(|A|2) variables).

Our main result holds without the assumption that each candidate is a top for some agent. Theorem 3. Let A be a set of alternatives, N be a set of agents, and be a preference proﬁle over A. The problem of determining whether top-monotonic order of exists (and computing it) is polynomial-time solvable. The proof follows exactly the same path as that of Theorem 3, but takes into account that the set QNT is not empty. Thus, in addition to creating 2CNF formulas out of the sets of legal orderings from QT (see Table 1), we also do the same with the sets from QNT . As an example, let us consider a pair of agents i, j with preferences over three candidates x, y, ω, where x ti(A), y tj(A) and ω (A \ T), such that x i ω i y and y j x j ω. This setting yields 2CNF formula (xy yω) (yx ωy). It turns out that based on QNT we can generate fewer rules than based on QT (namely, only 9 unique rules, as opposed to 21 generated for QT ). This is due to the fact that candidate ω can never be preferred over x by agent i or over y by agent j. We see that the rules generated off of the restrictions given by QNT can be added to the global ordering formula and, similarly as in the proof of Theorem 3, we show that the global formula has a satisﬁable assignment if and only if a top-monotonic order exists.

4 Conclusion We have given the ﬁrst polynomial-time algorithm for recognizing if a proﬁle of (possibly weak) preference orders is top-monotonic. Top-monotonic preferences are in principle very attractive. For example, they subsume single-peaked and single-crossing ones, while ensuring that a (weak) Condorcet winner always exists. However, they are not easy to work with. We hope that our proof will enable further researchers to show positive algorithmic consequences of the top-monotonicity assumption. For example, it is natural to ask if the Chamberlin Courant rule is polynomialtime solvable under top-monotonic preferences (it is under single-peaked [Betzler et al., 2013] and single-crossing ones [Skowron et al., 2015]). It is also interesting to compare the notion of top-monotonicity to that of value-restricted proﬁles [Sen, 1966].

References [Arrow, 1951] K. Arrow. Social Choice and Individual Values. John Wiley and Sons, 1951. Revised editon, 1963. [Aziz, 2014] H. Aziz. Testing top monotonicity. Technical Report ar Xiv:1403.7625v5 [cs.GT], ar Xiv.org, June 2014. [Barber a and Moreno, 2011] S. Barber a and B. Moreno. Top monotonicity: A common root for single peakedness, single crossing and the median voter result. Games and Economic Behavior, 73(2):345 359, 2011. [Bartholdi and Trick, 1986] J. Bartholdi, III and M. Trick. Stable matching with preferences derived from a psychological model. Operations Research Letters, 5(4):165 169, 1986.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)

[Betzler et al., 2013] N. Betzler, A. Slinko, and J. Uhlmann. On the computation of fully proportional representation. Journal of Artiﬁcial Intelligence Research, 47(1):475 519, 2013. [Black, 1958] D. Black. The Theory of Committees and Elections. Cambridge University Press, 1958. [Booth and Lueker, 1976] K. Booth and G. Lueker. 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, 1976. [Brandt et al., 2015] F. Brandt, M. Brill, E. Hemaspaandra, and L. Hemaspaandra. Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates. Journal of Artiﬁcial Intelligence Research, 53:439 496, 2015. [Bredereck et al., 2013] R. Bredereck, J. Chen, and G. Woeginger. A characterization of the single-crossing domain. Social Choice and Welfare, 41(4):989 998, October 2013. [Clearwater et al., 2015] A. Clearwater, C. Puppe, and A. Slinko. Generalizing the single-crossing property on lines and trees to intermediate preferences on median graphs. In Proceedings of the 24th International Joint Conference on Artiﬁcial Intelligence, pages 32 38, 2015. [Conitzer, 2009] V. Conitzer. Eliciting single-peaked preferences using comparison queries. Journal of Artiﬁcial Intelligence Research, 35:161 191, 2009. [Cornaz et al., 2012] D. Cornaz, L. Galand, and O. Spanjaard. Bounded single-peaked width and proportional representation. In Proceedings of the 20th European Conference on Artiﬁcial Intelligence, pages 270 275, August 2012. [Cornaz et al., 2013] D. Cornaz, L. Galand, and O. Spanjaard. Kemeny elections with bounded single-peaked or single-crossing width. In Proceedings of the 23rd International Joint Conference on Artiﬁcial Intelligence, pages 76 82, 2013. [Elkind and Lackner, 2015] E. Elkind and M. Lackner. Structure in dichotomous preferences. In Proceedings of the 24th International Joint Conference on Artiﬁcial Intelligence, pages 2019 2025, 2015. [Elkind et al., 2012] E. Elkind, P. Faliszewski, and A. Slinko. Clone structures in voters preferences. In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 496 513, June 2012. [Elkind et al., 2015] E. Elkind, P. Faliszewski, M. Lackner, and S. Obraztsova. The complexity of recognizing incomplete single-crossing preferences. In Proceedings of the 29th AAAI Conference on Artiﬁcial Intelligence, pages 865 871, 2015. [Escofﬁer et al., 2008] B. Escofﬁer, J. Lang, and M. Ozt urk. Single-peaked consistency and its complexity. In Proceedings of the 18th European Conference on Artiﬁcial Intelligence, pages 366 370. IOS Press, July 2008.

[Faliszewski et al., 2011] P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. The shield that never was: Societies with single-peaked preferences are more open to manipulation and control. Information and Computation, 209(2):89 107, 2011. [Faliszewski et al., 2014] P. Faliszewski, E. Hemaspaandra, and L. Hemaspaandra. The complexity of manipulative attacks in nearly single-peaked electorates. Artiﬁcial Intelligence, 207:69 99, February 2014. [Gaerner, 2001] W. Gaerner. Domain Conditions in Social Choice Theory. Cambridge University Press, 2001. [Gibbard, 1973] A. Gibbard. Manipulation of voting schemes. Econometrica, 41(4):587 601, 1973. [Guttmann and Maucher, 2006] W. Guttmann and M. Maucher. Variations on an ordering theme with constraints. In Fourth IFIP International Conference on Theoretical Computer Science TCS 2006, pages 77 90. Springer, 2006. [Krom, 1967] M. Krom. The decision problem for a class of ﬁrst-order formulas in which all disjunctions are binary. Zeitschrift f ur Mathematische Logik und Grundlagen der Mathematik, 13:15 20, 1967. [Lackner, 2014] M. Lackner. Incomplete preferences in single-peaked electorates. In Proceedings of the 28th AAAI Conference on Artiﬁcial Intelligence, pages 742 748, 2014. [Magiera and Faliszewski, 2014] K. Magiera and P. Faliszewski. How hard is control in single-crossing elections? In Proceedings of the 21st European Conference on Artiﬁcial Intelligence, pages 579 584, 2014. [Mirrlees, 1971] J. Mirrlees. An exploration in the theory of optimal income taxation. Review of Economic Studies, 38:175 208, 1971. [Peters and Lackner, 2017] D. Peters and M. Lackner. Preferences single-peaked on a circle. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence, 2017. [Peters, 2017] D. Peters. Recognising multidimensional euclidean preferences. In Proceedings of the 31st AAAI Conference on Artiﬁcial Intelligence, pages 642 648, 2017. [Roberts, 1977] K. Roberts. Voting over income tax schedules. Journal of Public Economics, 8(3):329 340, 1977. [Saporiti and Tohm e, 2006] A. Saporiti and F. Tohm e. Single-crossing, strategic voting and the median choice rule. Social Choice and Welfare, 26(2):363 383, 2006. [Satterthwaite, 1975] M. Satterthwaite. 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, 1975. [Sen, 1966] A. Sen. A possibility theorem on majority decisions. Econometrica, 34(2):491 499, 1966. [Skowron et al., 2015] P. Skowron, L. Yu, P. Faliszewski, and E. Elkind. The complexity of fully proportional representation for single-crossing electorates. Theoretical Computer Science, 569:43 57, 2015.

Proceedings of the Twenty-Sixth International Joint Conference on Artiﬁcial Intelligence (IJCAI-17)