Generalizing the Single-Crossing Property on Lines and Trees to Intermediate Preferences on Median Graphs

1 Introduction

Condorcet's famous paradox demonstrates that pairwise majority voting may produce intransitive collective preferences. The question of whether, and if so, how, this problem can be overcome by means of restrictions on the domain of admissible individual preferences has attracted constant interest over the recent decades, see [Gaertner, 2001] for a detailed overview. Probably the best-known domain restriction is single-peakedness [Black, 1948] which is frequently employed in models of political economy. It stipulates that all alternatives can be arranged along one dimension, for instance according to the political left-right spectrum, so that each voter has an ideal choice in the set of alternatives and the alternatives that are further from their ideal choice are preferred less. The concept of single-peakedness itself can be generalized considerably, however, the sufficiency of singlepeakedness for transitivity of the (strict) majority relation is confined to the classical one-dimensional case only. 1

A different and frequently useful sufficient condition for transitivity of the majority relation is the single-crossing

1 Single-peakedness on trees still guarantees the existence of a Condorcet winner, and single-peakedness on a median graph the existence of a "local" Condorcet winner [Bandelt and Barth´el´emy, 1984].

Arkadii Slinko

The University of Auckland Auckland, New Zealand a.slinko@auckland.ac.nz

property [Mirrlees, 1971]. A profile of individual preferences is said to have the single-crossing property if the voters can be arranged on a one-dimensional linear spectrum so that, for all pairs of alternatives (a, b), the set of voters who prefer a to b and also the set of voters who prefer b to a are both convex. As shown by Rothstein [1991], every single-crossing profile has a so-called representative voter, i.e., a voter whose (strict) preference coincides with the (strict) majority relation. 2

Roberts [1977], Blair and Crawford [1984], Gans Smart [1996] provide a number of economic applications of singlecrossingness among which are voting models of redistributive income taxation and trade union bargaining. All of them represent situations when preferences of individuals depend on a single parameter while in practice we may have a number of them. So there are compelling economic reasons which prompt us to consider single-crossingness on graphs more general than a line. Kung [2014], in particular, argues that single-crossingness on trees can be applied to the study of networks.

In contrast to the case of single-peaked preferences, the sufficiency of the single-crossing property for transitivity of the strict majority relation generalizes to median graphs [Demange, 2012], which, in particular, include trees and lattice graphs. This generalisation is based on the notion of intermediate preferences [Grandmont, 1978]. Assume that voters can be indexed by the vertices of a graph, and say that a profile satisfies the intermediateness property (or simply that it is intermediate) with respect to this graph if, for all pairs of alternatives (a, b) and any two voters i and j who prefer a to b, all voters that lie on any shortest path between i and j on the graph also prefer a to b. Evidently, if the graph is a line, a profile satisfies the intermediateness property if and only if it satisfies the single-crossing property.

The purpose of this paper is two-fold. Firstly, we prove that any profile which is intermediate on a median graph gives rise to a Condorcet domain. We give a constructive proof of the existence of an intermediate profile for any median graph with n vertices (generalising and strengthening the corresponding result of Kung for trees). We prove that n alternatives are always sufficient and that there exists a median graph (actually a tree) for which intermediate profiles with fewer than n alternatives do not exist. We also give a polynomial-time algorithm that recognizes whether or not a given profile is intermediate with respect to some median graph. Finally, we prove that the Chamberlin-Courant multiwinner voting rule on single-crossing profiles on trees has a polynomial time winner-determination problem which generalises a similar result of Skowron et al. [2013] for the classical single-crossing property. The corresponding problem on median graphs remains open. It is interesting to note that for the single-peaked property on a tree only the egalitarian version of the Chamberlin-Courant rule remains polynomial. The classical utilitarian version of this rule becomes NP-hard [Yu et al., 2013].

2 One can show that such a result does not hold for single-peaked preferences even on a line.

The problem addressed in the present paper is closely related to the search of maximal Condorcet domains [Abello and Johnson, 1984; Abello, 1991; Galambos and Reiner, 2008; Danilov et al., 2012]; see also the survey on the topic in [Monjardet, 2009]. Indeed, any intermediate profile on a median graph provides us with a new type of Condorcet domain (although possibly not maximal).

2 Preliminaries

2.1 Linear orders and profiles

Let A and V be two finite sets of cardinality m and n, respectively. The elements of A will be called alternatives, the elements of V = {1, 2, . . . , n} voters. We assume that the voters have preferences over the set of alternatives. By L(A) we denote the set of all (strict) linear orders on A; they represent the preferences of agents over A. The elements of the Cartesian product L(A)n = L(A) × . . . ×L(A) (n times) are called n-profiles or simply profiles. They represent the collection of preferences of the voters from V over the alternatives fromA. If a linear order Ri represents the preferences of the i-th voter, then by aRib, where a, b ∈ A, we denote that this agent prefers a to b. We also denote this as a ≻i b.

Given a profile R = (R1, . . . ,Rn), we say that a linear order Rj is between orders Ri and Rk if a ≻i b and a ≻k b imply a ≻j b for every pair of alternatives a, b ∈ A. The set of all linear orders fromR that are between Ri and Rk is denoted [Ri, Rk].

Definition 2.1. Let R = (R1, . . . ,Rn) be a profile. The majority relation M(R) of R over A is the binary relation on A such that for any a, b ∈ A we have a ⪰ b if and only if |{i | a ≻i b}| ≥ |{i | b ≻i a}|.

We will also write a ≻ b if a ⪰ b but not b ⪰ a and call it the strict majority relation. When n is odd, the majority relation coincides with the strict majority relation and is a tournament on A, i.e., a complete and asymmetric binary relation.

Definition 2.2. A Condorcet domain is a set of linear orders C ⊆ L(A) such that, no matter how many voters in the profile P have each of the linear orders from C as their preference relation, the strict majority relation of P is transitive.

Condorcet domains have long been of interest to Social Choice scientists and mathematicians alike; see the aforementioned survey byMonjardet. For a detailed discussion of single-crossing condition see [Bredereck et al., 2013].

2.2 Median Graphs, Geodesic Convexity and Geodesic Betweenness

Let G = (V, E) be a connected graph. The distance d(u, v) between two vertices u, v ∈ V will be the smallest number of edges that a path from u to v may contain. While the distance is uniquely defined, there may be several shortest paths from u to v. We say that vertex w is geodesically between vertices u and v if w lies on a shortest path that connects u and v or, alternatively, d(u, v) = d(u, w) + d(w, v).

Definition 2.3. A (geodesically) convex set in a graph G = (V, E) is a subset C ⊆ V such that for any two vertices u, v ∈ C all vertices of any shortest path between u and v in G lie entirely in C.

Definition 2.4. A connected graph G = (V,E) is called a median graph if for any three distinct vertices u, v,w ∈ V there is a unique vertex m(u, v, w), called median, which lies on shortest paths from u to v, from u to w and from v to w.

Trees and lattice graphs are examples of median graphs. It is known that median graphs are bipartite and hence do not contain triangles [Bandelt and Barth´el´emy, 1984].

To describe the structure of an arbitrary median graph we remind the concept of convex expansion for graphs.

Definition 2.5. Let G = (V, E) be a graph. Let W1, W2 ⊂ V be subsets such that W1 ∪W2 = V , W1 ∩W2 ̸= ∅ and there are no edges connecting vertices of W1 \ W2 and vertices of W2 \W1. The expansion of G with respect to W1 and W2 is the graph G′ constructed as follows:

• each vertex v ∈ W1 ∩W2 is replaced by two vertices v1 , v2 joined by an edge;
• v1 is joined to the neighbours of v inW1 \W2 and v2 is joined to the neighbours of v in W2 \ W1;
• if v,w ∈W1 ∩W2 and vw ∈ E, then v1 is joined to w1 and v2 is joined to w2 .

If W1 and W2 are convex, then G′ will be called a convex expansion of G.

Example 2.6 (Convex expansion). In the graph G shown on the left of the following figure we set W1 = {a, b, c, d} and W2 = {c, d, e, f}. These are convex and their intersection W1 ∩ W2 = {c, d} is not empty. Also the vertices of W1 \ W2 = {a, b} and W2 \ W1 = {e, f} have no edges between them. On the right we see the graph G′ obtained by the convex expansion of G with respect to W1 and W2.

Theorem 2.7 (Mulder's convex expansion theorem). A graph is a median graph if it can be obtained from a trivial one-vertex graph by repeated convex expansions.

3 Intermediateness property

Let G = (V, E) be a graph with V = {1, . . . , n} and R = (R1, . . . , Rn) be a profile. We will consider the linear orders of R as indexed by vertices of G.

Theorem 3.1. Let G = (V,E) be a graph with V = {1, . . . , n} and R = (R1, . . . ,Rn) ∈ L(A)n be a profile. The following conditions are equivalent:

• (i) Rj is between Ri and Rk whenever j is geodesically between i and k;
• (ii) for every ordered pair of alternatives (a, b) ∈ A2 the set Vab = {i ∈ V | a ≻i b} is convex in G;
• (iii) for every shortest path i1, . . . , ik in G between i1 and ik the profile (Ri1 , . . . ,Rik ) is classical single-crossing profile relative to the order of voters determined by that path.

Proof. (i) ⇒ (ii). Let i, k ∈ Vab. Consider j on any shortest path from i to k. Then by (i) Rj is between Ri and Rk and since i and k agree on the pair a, b we have a ≻j b, whence j ∈ Vab.

(ii) ⇒ (iii). Let I = {i1, . . . , ik} As I is a shortest path and Vab is convex, then Vab ∩ I is a subpath. But Vba ∩ I is also a subpath and this can happen only when there exists ℓ such that Vab = {i1, . . . , iℓ} and Vba = {iℓ+1, . . . , k}.

(iii) ⇒ (i). Follows from properties of classical singlecrossing profiles.

Definition 3.2. The profile R = (R1, . . . ,Rn) is said to be intermediate on the graph G = (V, E) if one of the equivalent conditions (i) - (iii) of Theorem 3.1 holds.

Let us consider several examples.

Example 3.3. (a) Classical single-crossingness. A classical single-crossing profile R = (R1, . . . , Rn) is intermediate on a path:

(b) Single-crossing on a tree. Consider the profile R = (R1,R2,R3,R4) on the set {a, b, c, d} consisting of the following four orders: R1 = acbd, R2 = abcd, R3 = abdc, and R4 = bacd. As is easily seen, this profile is intermediate (single-crossing) on the following tree:

(c) Intermediate profile on a lattice graph. The following profile R is made of a set of linear orders which is a maximal Condorcet domain: R1 := abcd, R2 := abdc, R3 := bacd, R4 := badc, R5 := cdab, R6 := dcab, R7 := cdba, R8 := dcba. It can be checked that R is intermediate on the cube:

Unlike for trees an ab-cut may not be unique (although [Demange, 2012] claims that it is). Given an edge e let us denote S(e) = {(a, b) ∈ A2 | e is an ab-cut}.

Lemma 3.5. Let P be a profile which is intermediate on a median graph G = (V,E). An edge e = uv ∈ E is an abcut if and only if Vab = {w ∈ V | d(w, u) < d(w, v)}, and Vba = {w ∈ V | d(w, u) > d(w, v)}.

Proof. Let w ∈ Vab. Then, due to intermediateness, among w, u, v only u can be the median. Hence wuv is the shortest path from w to v and d(w, u) = d(w, v) - 1 and d(w, u) < d(w, v). The converse is clear.

Corollary 3.6. Let P be a profile which is intermediate on a median graph G = (V,E). Suppose e1, . . . , ek ∈ E are ab-cuts. Then S(e1) = . . . = S(ek).

Proof. Suppose e1 = u1v1 is an ab-cut and also a cd-cut. Then by Lemma 3.5 Vab = Vcd and Vba = Vdc. Since ei = uivi is an ab-cut, then ui ∈ Vab = Vcd and vi ∈ Vba = Vdc. Hence ei is also a cd-cut.

We need the following technical lemma now.

Lemma 3.7. Let P = (P k1 1 , . . . , P kn n ) be a profile, where linear order Pi is repeated ki times and Pi ̸= Pj if i ̸= j. If P is intermediate on a median graph G, then the profile ˆ P = (P1, . . . , Pn) is also intermediate on a median graph.

Proof. Any two identical linear orders are either neighbors in G or connected by a path of vertices with identical linear orders. Contracting them to a single vertex results in the graph sought for.

Let P be a profile. By D(P) we denote the set of all distinct linear orders present in P. If all linear orders of P are different, we call the profile P reduced.

Theorem 3.8. Let P be a profile which is intermediate with respect to a median graph G = (V,E). Then D(P) is a Condorcet domain.

Proof. By Lemma 3.7 we may assume that the profile P is reduced. Let Q = (Qs1 1 , . . . ,Qsm m ) be a profile with Qi ∈ D(P) and Qi ̸= Qj for all i ̸= j. We can add linear orders Qm+1, . . . ,Qn so that the extended profile ̂Q = (Q1, . . . ,Qn) is intermediate on a median graph G = ( ̂ V ,E), where ̂ V = {1, . . . , n} (renumeration of vertices may be necessary). We will also denote V = {1, . . . , m}.

Suppose that a ≻ b and b ≻ c, where ≻ is the majority relation for Q. Then we have two partitions of V , namely, V = Vab ∪ Vba and V = Vbc ∪ Vcb. We have |Vab| > |Vba| and |Vbc| > |Vcb|. Obviously, Vabc = Vab ∩ Vbc ̸= ∅ since each of these sets contains a majority of voters in V . We have Vab ⊆ ̂ Vab and Vbc ⊆ ̂ Vbc, where ̂ Vxy = {i ∈ ̂ V | x ≻i y}. We cannot claim that ̂ Vab or ̂ Vbc contains more than half of all elements of ̂ V but we know that ̂ Vab ∩ ̂ Vbc ⊇ Vabc ̸= ∅.

Consider now ̂ Vac and ̂ Vca. Suppose there are several edges es = usvs (s = 1, . . . , t), connecting them; all of them are ac-cuts. Suppose ̂ Vac ∩ ̂ Vab ̸= ∅ and ̂ Vca ∩ ̂ Vab ̸= ∅. Then for any p ∈ ̂ Vac ∩ ̂ Vab and q ∈ ̂ Vca ∩ ̂ Vab the shortest path between them includes one of the ac-cuts, say ei = uivi. This means that a ≻ui b and a ≻vi b. But then it is not possible to have ̂ Vac ∩ ̂ Vbc ̸= ∅ and ̂ Vca ∩ ̂ Vbc ̸= ∅ since in this case we would have b ≻ui c and b ≻vi c and by transitivity a ≻ui c and a ≻vi c which contradicts to ei being an ac-cut. Since ∅ ̸= Vabc ⊆ ̂ Vac ∩ ̂ Vbc, we have ̂ Vca ∩ ̂ Vbc = ∅ and Vbc ⊆ Vac. This means a ≻ c and ≻ is transitive.

Now we are going to prove that for any median graph we can construct a reduced profile which is intermediate on that particular graph. We then discuss how many alternatives may be needed.

Theorem 3.9. For every median graph G = (V,E) with |V | = n there exists a reduced preference profile R = (R1, . . . ,Rn) ∈ L(Y )n on a set of alternatives Y with |Y | ≤ n such that R is intermediate on G.

Proof. Since the statement is true for the trivial graph consisting of a single vertex, arguing by induction, we assume that the statement is true for all median graphs with k vertices or less. Let G′ = (V ′ , E′ ) be a median graph with |V ′ | = k+1. By Mulder's theorem G′ is a convex expansion of a certain median graph G = (V, E) relative to convex subsets W1 and W2, where |V | = ℓ ≤ k. By induction there exists a reduced profile R = (R1, . . . ,Rℓ) ∈ L(X)ℓ with |X| ≤ k which is intermediate on G.

To obtain a new profile R′ which is intermediate on G′ we clone an arbitrary alternative x ∈ X and introduce a clone y /∈ X of x. 3 The linear orders of the new profile R′ will be constructed as follows. If v is a vertex of W1 \W2 to obtain R′v we replace x with xy in Rv placing y lower than x and to obtain R′u for u ∈ W2 \ W1 we replace x with yx in Ru placing y higher than x. Let v now be in W1 ∩W2. In the convex expansion this vertex is split into v1 and v2 . To obtain R′v1 we clone the linear order Rv replacing x with xy and to obtain R′v2 we clone the same linear order Rv replacing x with yx. We have Y = X∪{y} so the number of alternatives has increased by one, so it is not greater than k + 1 = |V ′ |. The profile R′ , so obtained, is also reduced.

To prove that R′ is intermediate on G′ . we need to consider several cases. For example, let u ∈ W1 \W2 and v ∈ W2 \ W1 and let us prove that all linear orders on a shortest path between u and v are between R′u and R′v . Firstly, we note that any such shortest path will contain an edge e = w1w2 , where w ∈ W1 ∩W2. There is the corresponding path in G, where the edge e is contracted to w and all linear orders on that path are between Ru and Rv. The way we placed y in these linear orders will not disturb the betweenness since all linear orders R′z between R′u and Rw1 (inclusive) will have x ≻′z y and all others will have y ≻′z x. All other cases are considered similarly.

3 We say that x and y are clones if they are neighbours in any linear order of the domain (cf. Elkind et al (2011) and (2012)).

The constant n in this theorem cannot be improved even for trees. However we must exclude some trivial cases. For example, if all the linear orders in a profile are equal, then it is intermediate for any graph. So we have to restrict ourselves to reduced profiles.

Theorem 3.10. For the star Sn with n vertices (the complete bipartite graph K1,n-1) there does not exist a reduced profile R = (R1, . . . , Rn) ∈ L(X)n on the set X of alternatives of cardinality smaller than n which is intermediate on Sn.

Proof. We reason by induction on n. The base case is the star S2 with two vertices for which the result is clear.

Let us assume that for Sn, n ≥ 2, we cannot construct a reduced profile with less than n alternatives which is intermediate on Sn. Consider Sn+1 and suppose towards a contradiction that we can find a reduced profile P = (P1, . . . , Pn+1) with n alternatives which is intermediate on Sn+1. Suppose that the vertices of Sn+1 are numbered so that voter 1's vertex has degree n and voter 1 has preferences expressed by the linear order a1 ≻1 a2 ≻1 . . . ≻1 an. Suppose, first, that s is the smallest number for which one of the edges, say the one connecting 1 with n+1, is an a1as-cut for Sn+1; if such a number does not exist, a1 can be removed from the profile and it will stay reduced. Then as ≻n+1 a1 and a1 ≻i as for all i ≤ n (otherwise intermediateness fails). Let us remove now vertex n + 1 from the graph and linear order Pn+1 from the profile. Then we get graph Sn and the profile P ′ = (P1, . . . , Pn) which is intermediate on Sn. No edge in Sn is an a1as-cut now. Let us now remove the alternative a1 from P ′ to obtain a profile P ′′ = (P ′′ 1 , . . . , P ′′ n ). Then P ′′ is still intermediate on the star Sn and we claim that P ′′ is reduced. If not, then after removal of a1, at least two linear orders, say P ′′ i and P ′′ k become equal. If i = 1, then the only cut the edge 1k had was an a1at-cut for some t > s. Then we had at ≻k a1 ≻k as while as ≻1 at; so we see that 1k had also a asat-cut. This contradicts P ′′ 1 = P ′′ k .

Now suppose P ′′ i = P ′′ k with i ̸= 1 and k ̸= 1. Then Pi and Pk must agree on a2, . . . , an. Due to intermediateness they must also agree with P1 on these, i.e., a2 ≻i . . . ≻i an and a2 ≻k . . . ≻k an. Since a1 cannot be on the top of each of them (otherwise one would be equal to P1) we have a2 ≻i a1 and a2 ≻k a1, which contradicts intermediateness.

Hence P ′′ is reduced. Since P ′′ has n-1 alternatives, this is a contradiction.

4 Algorithmic aspects of single-crossedness

4.1 A recognition algorithm.

The goal of this section is to give a polynomial-time algorithm for recognising intermediate profiles on median graphs. We need to know more about the structure of intermediate profiles on median graphs.

Theorem 4.1. Let R = (R1, . . . , Rn) ∈ L(A)n be a profile whose linear orders are indexed by the vertices of graph G = (V,E). Let a, b ∈ A be a pair of alternatives such that ∅ ̸= Vab ̸= V . Let also ei = uivi, i = 1, . . . , s be the edges that connect Vab and Vba with ui ∈ Vab and vi ∈ Vba. Then G is a median graph and R is intermediate on G iff

• (i) u1, . . . , us are all distinct and so are v1, . . . , vs;
• (ii) S(e1) = . . . = S(es);
• (iii) Induced graphs on Vab and Vba are median graphs in their own right;
• (iv) Rab = {Ru | u ∈ Vab} and Rba = {Rv | v ∈ Vab} are the profiles which are intermediate on Vab and Vba, respectively;
• (v) Let ¯G be the graph G with edges e1, . . . , es contracted. Let ¯ Vab and ¯ Vba be images of Vab and Vba in ¯G. Then G is the convex expansion of ¯Gwith respect to ¯ Vab and ¯ Vba.

Proof. =⇒ (i) Suppose vi = vj, then ui ̸= uj and (a, b) ∈ S(ei) = S(ej). Since G is bipartite it has no triangles, hence uiviuj is the shortest path between ui and uj. This contradicts to intermediateness since Rui and Ruj agree on (a, b) but Rvi disagrees with them.

• (ii) is Corollary 3.6.
• (iii) Follows from an observation that a shortest path between vertices w,w′ ∈ Vab cannot involve any of e1, . . . , es and hence lies entirely in Vab.

(iv) and (v) are now obvious.

⇐= Firstly, G is median due to Mulder's theorem. To check intermediateness, let us consider a shortest path between u and v from V . If they are both in Vab or Vba, this case is clear. Suppose u ∈ Vab and v ∈ Vba and they agree on (c, d) for some c, d ∈ A. The shortest path between u and v contains one of the edges e1, . . . , es, say ei so it goes through vertices u, ui, vi, v. Since elements of Vcd are found both in Vab and Vba by Lemma 3.5 we cannot have (c, d) ∈ S, where S = S(e1) = . . . = S(es). Thus both c ≻ui d and c ≻vi d. The part of the path connecting u and ui is the shortest path in Vab so all linear orders on this path agree with u and ui on (c, d). So do the linear orders on the path from vi to v. This proves the theorem.

The idea of the recognition algorithm is now clear. We give the construction only for a reduced profile R = (R1, . . . ,Rn). The order of linear orders in the profile can be ignored so we actually deal with the domain D = {R1, . . . , Rn}. Firstly, we identify the graph GD to be tested. For this we find all pairs of 'neighboring' linear orders. Any two linear orders P,Q ∈ D define the 'interval' [P,Q] as the set of all linear orders in D which are between P and Q and call P and Q neighbors if [P,Q] = {P,Q}. We draw edges between the neighboring orders and obtain the graph GD on linear orders from D. The construction of this graph requires O(m2n3 ) operations, where m is the number of alternatives.

If R was intermediate on a median graph G, then GD is exactly G. Indeed, if u and v were neighbors in G, then [Ru,Rv] = {Ru,Rv}. If only Rw ∈ [Ru,Rv] for w ̸= u and w ̸= v, then, since u and v are neighbors, the median m(u, v,w) is either u or v. Suppose m(u, v,w) = u. Then, due to intermediateness, Ru is between Rw and Rv from which Rw = Ru. On the other hand, if u and v are not neighbors in G, then it is easy to see that [Ru,Rv] ̸= {Ru,Rv}.

We then pick any pair (a, b) ∈ A for which Vab and Vba are both nonempty and select edges ei = uivi, i = 1, . . . , s of GD. If all ui's and all vi's are different, and S(e1) = . . . = S(es), then the question of whether or not R is intermediate on GD will be reduced to the questions of whether or not Rab = {Ru | u ∈ Vab} and Rba = {Rv | v ∈ Vba} are intermediate on graphs induced on Vab and Vba, respectively. This can be arranged as a recursive algorithm. We have proved

Theorem 4.2. For an input profile with n voters and m alternatives we can determine in time polynomial in m, n whether or not the given profile is intermediate on some median graph, and, if so, construct this graph.

4.2 Chamberlin-Courant rule

This section deals with single-crossing profiles on trees.

Given a society of n voters V with preferences over a set of m candidates A and a fixed positive integer k ≤ m, a method of fully proportional representation outputs a kmember committee (e.g., parliament), which is a subset of A, and assigns to each voter a candidate that will represent this voter in the committee. The fully proportional representation rules, suggested by Chamberlin and Courant [1983] and Monroe [1995], have been widely discussed in Political Science and Social Choice literature alike [Potthof and Brams, 1998; Meir et al., 2008; Betzler et al., 2013].

It is well-known that on an unrestricted domain of preferences both rules are intractable in the classical [Meir et al., 2008; Lu and Boutilier, 2011] and parameterized complexity [Betzler et al., 2013] senses. [Skowron et al., 2013], however, showed that for the classical single-crossing elections the winner-determination problem for the ChamberlinCourant rule is polynomial-time solvable for every dissatisfaction function for both the utilitarian [Chamberlin and Courant, 1983] and egalitarian [Betzler et al., 2013] versions of the rule. They also generalized this result to elections with bounded single-crossing width proving fixedparameter tractability of the Chamberlin-Courant rule with single-crossing width as parameter. The concept of singlepeaked width was defined in [Cornaz et al., 2012].

Here we will prove that polynomial solvability remains for single-crossing profiles on any tree. But, firstly, we will remind the reader the definitions needed for discussing the Chamberlin-Courant rule. By posv (c) we denote the position of the alternative c in the ranking of voter v; the top-ranked alternative has position 1, the second best has position 2, etc.

Definition 4.3. Given a profile P over set A of alternatives, a mapping r : P × A → Q+0 is called a misrepresentation function if for any voter v ∈ V and candidates c, c′ ∈ A the condition posv (c) < posv (c′ ) implies r(v, c) ≤ r(v, c′ ).

In the classical framework the misrepresentation of a candidate for a voter is a function of the position of the candidate in the preference order of that voter given by s = (s1, . . . , sm), where 0 = s1 ≤ s2 ≤ . . . ≤ sm, that is, the misrepresentation function in this case will be r(v, c) =

sposv (c). Such a misrepresentation function is called positional. An important case is the Borda misrepresentation function defined by the vector (0, 1, . . . ,m - 1) which was used in [Chamberlin and Courant, 1983]. We assume that the misrepresentation function is defined for any number of alternatives and that it is polynomial-time computable.

In the approval voting framework, if a voter is represented by a candidate whom she approves, her misrepresentation is zero, otherwise it is equal to one. This function is called the approval misrepresentation function. It does not have to be positional since different voters may approve different numbers of candidates. In the general framework the misrepresentation function may be arbitrary.

By w: V → A we denote the function that assigns voters to representatives, i.e., under this assignment voter v is represented by candidate w(v). If |w(V )| ≤ k we call it a kassignment. The total misrepresentation Φ(P, w) of the given election under w is then given by Φ(P, w) = ℓ(r(v, w(v))), where ℓ is used to mean either the sum or the maximum of a given list of values depending on the utilitarian or egalitarian model, respectively.

The Chamberlin-Courant rule takes the profile and the number of representatives to be elected k as input and outputs an optimal k-assignment wopt of voters to representatives that minimizes the total misrepresentation Φ(P, w).

Theorem4.4. For any polynomial-time computable dissatisfaction function, every positive integer k, and for both utilitarian and egalitarian versions of the Chamberlin-Courant rule, there is a polynomial-time algorithm that given a profile P = (P1, . . . , Pn) over a set of alternatives A = {a1, . . . , am}, which is single-crossing with respect to some tree, finds an optimal k-assignment function wopt for P.

Lemma 4.5. Let P = (P1, . . . , Pn) be a reduced profile over a set A = {a1, . . . , am} of alternatives, where P is singlecrossing with respect to a tree T. Let wopt be an optimal kassignment for P. Let voter 1 be an arbitrary vertex of T, and let b ∈ A be the least preferred alternative of voter 1 in wopt(V ). Then the vertices of w-1 opt (b) are vertices of a terminal subtree (a subtree whose vertex-complement is also a subtree) of T .

Proof. On a tree T we may define the distance between any two vertices u and v which is the number of edges on the unique path connecting these two vertices. Let v be the closest vertex to 1 such that wopt(v) = b. Let u be the vertex on that path which is one edge closer to 1 (it can be actually 1 itself). Due to minimality of T the edge (u, v) is an (a, b)- cut for some a = wopt(u) where a ≻1 b. Let us show that w-1 opt (b) = Vba. Suppose first that wopt(v′ ) = b. Then b ≻v′ a (otherwise v′ would be assigned a) and hence v′ ∈ Vba. Suppose now v′ ∈ Vba. Then v′ is connected by a path within Vba, hence the unique path between 1 and v′ passes through v. Since linear orders on this path form a classical single crossing subprofile we have wopt(v′ ) = b.

The fact that the least preferred alternative of voter 1 in the elected committee w(V ) represents voters in a terminal subtree of T is important in our design of a dynamic programming algorithm. We will fix an arbitrary leaf, without loss of generality it will be voter 1, and reduce the problem of calculating an optimal assignment for a profile P = (P1, . . . , Pn) over a set of alternatives A = {a1, . . . , am} to a partially ordered set of subproblems which will be defined shortly. Let us denote the original problem as (P,A, k). We define the set of subproblems as follows. A triple (P ′ ,A′ , k′ ), where k′ ≤ k is a positive integer, P ′ is a subprofile of P and A′ is a subset of A is a subproblem of (P, A, k) if

1. P ′ = Pab, the subprofile of linear orders corresponding to the subset of vertices Vab ⊆ V , where a ≻1 b;
2. A′ = {a1, . . . , aj} for some positive integer j such that k ≤ j ≤ n;
3. the goal is to find an optimal assignment w′ : Vab → A′ with |w′ (Vab)| ≤ k′ .

The idea behind this definition is based on Lemma 4.5. Namely, we can try to guess the least preferred alternative of voter 1 in the elected committee aj and the terminal subtree Vba whose voters are all assigned to aj , then the problem will be reduced to choosing a committee of size k - 1 among {a1, . . . , aj-1} given the profile Pab of voters corresponding to Vab. We note that there are at most n - 1 subproblems. Note that our cuts can be naturally ordered: we can say that ab-cut ⊂ cd-cut if and only if Vab ⊂ Vcd.

Proof of Theorem 4.4. The tree T with respect to which P is single-crossing can be computed in polynomial time, by Theorem 4.2. We can identify one of the leaves then. Let this be voter 1 with preferences a1 ≻1 · · · ≻1 am.

For every ab-cut, j ∈ {1, . . . ,m} and t ∈ {1, . . . , k} we define A[Vab, j, t] to be the optimal dissatisfaction (calculated in the utilitarian or egalitarian way) that can be achieved with a t-assignment function when considering a subprofile P ′ = {Pab | 1 ∈ Vab} over A′ = {a1, . . . , aj}. It is clear that for V ⊆ V , j ∈ M\{1} and t ∈ K\{1}, the following recursive relation holds

Here ℓ is used to mean either the sum or the maximum of a given list of values depending on the utilitarian or egalitarian model, respectively. To account for the possibility that aj is not elected in the optimal solution, we also include the term A[V, j-1, t]. Thus, A[V, m, k] is then the optimal dissatisfaction, and in calculating it we simultaneously find the optimal k-assignment function.

The following base cases are sufficient for the recursion to be well-defined

• A[∅, j, t] = 0;
• A[V, j, 1] = min j ′≤j ℓ((r(vi, aj ′ ))i∈V );
• A[V, j, t] = 0 for t ≥ j.

These conditions suffice for our recursion to be welldefined. Using dynamic programming, we can compute in polynomial time, in fact, in time O(mn2k), the optimal dissatisfaction of the voters and the assignment that achieves it. Note that the complexity is the same as for the classical case in [Skowron et al., 2013] which we closely followed.

5 Conclusion

This paper generalises the classical single-crossing property to an intermediate property on median graphs and, in particular, to trees. We complement Demange's representative voter theoremwith the fact that the set of linear orders of any intermediate profile on a median graph is a Condorcet domain.

We prove that, for any median graph, there exists a profile of preferences which is intermediate with respect to that particular graph. Finally we present two results on algorithmic aspects of single-crossedness. The first one states that recognising intermediateness on median graphs is possible in polynomial time, and the second shows that the winner determination problem for the Chamberlin-Courant rule is also polynomial for single-crossing profiles on trees. We do not know whether or not this latest result can be extended to intermediate profiles on median graphs.