Recognizing Top-Monotonic Preference Profiles in Polynomial Time

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:

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 profile by choosing orders only from this set, then there 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, first this voter's appreciation for the candidates increases and then decreases.

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

On the other hand, a preference profile 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 first 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 singlepeakedness 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 define intuitively (and, indeed, this is why we refrain from describing them here on the intuitive level and point the reader to the formal definition 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; Escoffier 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 first such algorithm. (However, we mention that there are natural domain restrictions for which the recognition problem is NP-hard [Peters, 2017].)

1 Results 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.

The first 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 profile 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 profiles 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 satisfiable, 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 problem 3 (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 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).

2 Lackner [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.

3 In 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].

Our results may inspire researchers to seek positive algorithmic consequences for top-monotonic preference profiles.

2 Preliminaries

We mostly adopt the notation of Barber`a and Moreno [2011]. We let A be a (finite) 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 defined for each x, y ∈ A as follows:

A preference profile is a collection of preference orders of the agents from N; we write ≽ = (≽1, . . . , ≽n) to denote a preference profile of weak orders, and ≻ = (≻1, . . . , ≻n) for a profile 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 define top-monotonic preferences, let us give formal definitions of single-peaked and single-crossing ones.

Definition 1 (Black [1958], Arrow [1951]). Apreference profile ≻ 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 definition 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 >.)

Definition 2 (Mirrlees [1971] and Roberts [1977]). A profile ≻ = (≻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}. Profile ≻ is singlecrossing if it is single-crossing with respect to some ordering of the voters.

That is, a profile 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 profile of the following preference orders:

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

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

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; fulfilling these conditions simultaneously is impossible).

We are ready to define 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 = ⋃i∈N ti(A). For each preference profile ≽, 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).

Definition 3 (Barber`a andMoreno [2011]). A preference profile ≽ is top-monotonic if there exists a linear order > over the set of the alternatives, such that:

1. ti(A) is a finite 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:

Definition 4. A linear order > over the set of alternatives is a top-monotonic order of a preference profile ≽ if ≽ is topmonotonic and > fulfills condition (2) from Definition 3.

The following example, provided by Barber`a and Moreno [2011], shows that there is a profile that is topmonotonic but neither single-peaked nor single-crossing (the fact that every single-peaked or single-crossing profile is topmonotonic is also shown in their work).

Example 2. Consider candidate set {a, b, c, d} and profile ≻ of three preference orders:

Note that c is preferred to each other candidate by a majority of the agents. The profile 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 is impossible. However, the profile is top-monotonic with respect to the order a > b > c > d.

4 Since we assumed A to be a finite set, this part of the definition is always trivially satisfied. Barber`a and Moreno consider also more general sets of alternatives and-to indicate the generality of their definition-we decided to keep this requirement in the text.

To see that the profile 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 profile using the definition 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 profile is as follows: Given a finite set of alternatives A, a finite set of agents N, and a preference profile ≽ (for the agents in N) over A, find 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 definition, 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.

Definition 5. For each triple of distinct alternatives S = {x, y, z} ⊆ A and each pair of agents i, j ∈ N, we define 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:

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 satisfies all the five 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 definitions 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 defined 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 Abe a set of alternatives, N be a set of agents, and ≽ be a preference profile 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, Definition 5 and Lemma 1 jointly follow quite closely the definition of top-monotonic preferences, but the detailed proof, available upon request, is rather lengthy).

The greatest advantage of using Lemma 1 and Definition 5 over directly applying Definition 3 is that it allows us to focus on sets of three candidates only (Definition 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 profile 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 sufficient to demonstrate that finding 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 fromQT . 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 Definition 5. To obtain a set of legal orderings for some triple of candidates S and some agents i and j, it suffices 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 profile ≽′ be as follows (N ′ = {1, 2}):

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:

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

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 find a linear order > over the set of alternatives such that for each X ∈ Q we can find 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:

We can create a similar formula for each set of legal orderings fromQ, 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:

or, equivalently, as:

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

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):

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

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

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

5 The 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 find a 2CNF formula and we made a brute-force search for one that would work.

To prove this result, we first note that if ≽ has a topmonotonic order then the global ordering formula is satisfiable. 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 profile is top-monotonic. Let us assume that the global ordering formula has a satisfying assignment and let relation >′ be defined for each pair of alternatives p, q ∈ A as follows: We set p >′ q exactly if the literal pq evaluates to 1. By definition, relation >′ satisfies 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 irreflexive, 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 profile); 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 >∗ satisfies 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 satisfiable 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 profile 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 fromQNT . 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 satisfiable assignment if and only if a top-monotonic order exists.

4 Conclusion

We have given the first polynomial-time algorithm for recognizing if a profile 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 profiles [Sen, 1966].