Aggregating preferences of a set of agents is a common problem in multiagent systems. In a typical setting, we have a set of m candidates, a set of n voters each of whom possesses a preference which is a linear order (reflexive, anti-symmetric, and transitive relations) over the set of candidates, and we would like to aggregate these preferences into one preference which intuitively “reflects” the preference of all the voters. However, it is wellknown that the pairwise majority relation of a set of preferences may often be intransitive due to existence of the Condorcet cycles – a set of candidates is preferred over by a majority of the voters for every preferred over (see [Mou91]). Consecutively, a substantial amount of research effort has been devoted to finding interesting restrictions on the preferences of the voters which ensure transitivity of the majority relation (see [MG04] for a survey).

Among the most widely used domains in social choice theory are the single peaked and single crossing domains. Introduced by [Bla48], the single peaked domain not only satisfies transitivity of majority relation but also captures the essence of many election scenarios including political elections [HM97]. Intuitively, a profile, which is a tuple of preferences of all the voters, is called single peaked if the candidates can be arranged in a linear order (often called societal axis or harmonious order) and every voter can be placed somewhere in that linear order so that she prefers candidates “closer” to her than candidates “far” from her. The notion of single peakedness has subsequently been generalized further, often at the cost of the transitivity property of the majority relation. For example, the popular single peaked domain on trees [Dem82] only guarantees existence of a Condorcet winner (for an odd number of voters) and the notion of single peaked width [CGS12] does not even guarantee existence of a Condorcet winner. A Condorcet winner is a candidate who is preferred over every other candidate by a majority of the voters.

[Mir71] proposed the single crossing domain where voters (instead of candidates as in the case of single peaked domain) can be arranged in a linear order so that, for every two candidates x and y, all the voters who prefer x over y appear consecutively. Other than guaranteeing transitivity property of the majority relation, the single crossing domain has found wide applications in economics [DS74], specially in redistributive income taxation [Rob77, MR81], trade union bargaining [BC84], etc. The notion of single crossingness has further been generalized with respect to median graphs while maintaining the transitivity of the majority relation [Dem12]. A graph is called a median graph if, for every three nodes, there exists a unique node which is present in the shortest paths between all three pairs of nodes. Trees, hypercubes, etc. are important examples of median graphs. In recent times, Kung applied single-crossingness on trees to the study of networks [Kun15].

All the domains discussed above also enjoy other desirable properties. Existence of strategy-proof voting rules, polynomial time tractability of the problem of finding the winner for important voting rules like Kemeny [Kem59, Lev75, BBHH15], Dodgson [Dod76, BNM58], Chamberlin-Courant [BSU13, SYFE13, CPS15], etc. are prominent examples of such properties. Domain restrictions in the presence of incomplete votes (where votes may be partial orders instead of complete orders) has also received signifi-cant research attention in recent times. [Lac14] showed that determining whether a set of incomplete votes is single peaked is an NP-complete problem. [EFLO15a] performed similar exercise for the single crossing domain and showed that although the problem of finding whether a set of incomplete votes is single crossing is NP-complete in general, it admits polynomial time algorithms for top orders and for various other practically appealing cases. [EL15] extended the notions of single peakedness and single crossingness to approval votes and showed that various computational problems that are hard in the approval voting setting become polynomial time tractable. In a approval voting scenario, every vote simply approves a subset of candidates instead of specifying a complete ranking of the candidates. Closeness of a profile to various domains also forms an active body of current research. The work of [ELP13] and [BCW16] showed that the problem of find-ing the distance of a profile from the single peaked and single crossing domains are often

Figure 1: The set is single crossing with respect to a tree. However is not single crossing with respect to any tree.

NP-hard and occasionally polynomial time solvable under various natural notions of distance. [EL14] provided approximation and fixed parameter tractable algorithms for the problems of finding the minimum number of votes/candidates that need to be deleted so that the resulting profile belongs to some specific domain – their algorithms work for any domain which can be characterized by forbidden configurations and thus, in particular, for both the single peaked and single crossing domains. [FHH14] studied various manipulation, control, and bribery problems in nearly single peaked domain and showed many interesting results; for example, they proved that some control problems suddenly become NP-hard even in the presence of only one maverick whereas many other manipulation problems continue to be polynomial time solvable with a reasonable number of mavericks. We refer the reader to the recent survey article by [ELP16] and references therein for a more complete picture of recent research activity in preference restrictions in computational social choice theory.

1.1 Motivation and Related Work

A property that is usually true for all popular domains is what we call “downward monotonicity” – if a profile belongs to a domain D, then so is any subset of the profile (votes). To the best of our knowledge, only important exceptions to this is the single crossing domain on trees [CPS14] and Condorcet domain (the set of all preference profiles where a Condorcet winner exists). We refer to Figure 1 for an example. Interestingly, the sub-profiles of a single crossing profile on trees continue to exhibit desirable properties like transitivity of majority relation, polynomial time recognition algorithm [CPS15], existence of polynomial time algorithms for Kemeny and Dodgson voting rules, etc. This makes the study of the sub-profiles of single crossing profiles on trees important. We call the domain consisting of all profiles which are sub-profiles of some single crossing profile on trees, weakly single crossing domain on trees. We remark that the domain of top monotonic profiles also does not satisfy similar notion of downward monotonicity with respect to candidates – deleting candidates from a top monotonic profile may destroy top monotonicity property. However, the votes are much more general there than simply being complete rankings and are allowed to be any complete, reflexive, and transitive (not necessarily anti-symmetric) binary relations. We refer the interested readers to the work of [BM11] for an elaborate exposition to top monotonic profiles.

One of the first questions to ask for any domain is whether there exists an efficient recognition algorithm – given a profile P, does there exist a polynomial time algorithm to decide whether P belongs to the domain? Indeed, there exist efficient recognition algorithms for many popular domains, for example, single peaked [Tri89], single crossing [BCW13, CPS15], and so on [Kno10, EFLO15b, EF14]. This motivates us to pursue a similar question for the weakly single crossing domain on trees – does there exist a polynomial time recognition algorithm for the weakly single crossing domain on trees?

Another fundamental problem in social choice theory is preference elicitation – elicit the preferences of a set of agents by asking them (hopefully a small number of) comparison queries. Indeed, in many applications of social choice theory, for example, metasearch engines [DKNS01], spam detection [CSS99], computational biology [JSA08], the number of candidates is huge and thus, simply asking the agents to reveal their preferences is impractical. [Con09] showed that, for the domain of single peaked profiles, we can elicit the preferences of a set of agents by asking a small number of comparison queries. Recently, a similar study has been carried out for the single peaked domain on trees [DM16a] and single crossing domain [DM16b]. This motivates us to study preference elicitation for the weakly single crossing domain on trees.

1.2 Our Contribution

Our specific contributions in this work are as follows.

Given a weakly single crossing profile P on trees, we show that there exists an inclusion-minimal profile ¯P which contains P and is itself single crossing with respect to some tree [Theorem 1]. We call ¯P the single crossing tree closure of P.

We extend the polynomial time recognition algorithm of Clearwater et al. [CPS15] for single crossing profiles on trees to a polynomial time recognition algorithm for weakly single crossing profiles on trees. Moreover, for any weakly single crossing profile P on trees, our recognition algorithm also outputs a tree T on the single crossing tree closure ¯P of P with respect to which ¯P is single crossing [Corollary 1].

minfor eliciting weakly single crossing profiles on trees, even if we do not a priori know any tree with respect to which the single crossing tree closure of the input profile is single crossing and we are only allowed to access the preferences in an arbitrary (unknown) sequential order [Theorem 3 and Corollary 2]. We note that the query complexity of our preference elicitation algorithm matches (up to constant factors) with the query complexity of preference elicitation algorithm for single crossing profiles due to [DM16b].

We complement the query complexity of our preference elicitation algorithm by showing that any preference elicitation algorithm for single crossing profiles on trees

has query complexity , even if the input profile is single crossing with respect to a known tree and we are allowed to query preferences randomly and interleave the queries to different preferences arbitrarily [Theorem 4].

We improve the query complexity lower bound in [DM16b] for eliciting single crossing profiles when random queries are permitted to showing optimality of their alogrithm [Theorem 5].

For a positive integer , we denote the set . For a set X and an integer k, we denote the set of all possible subsets of

Let be a set of be a set of m candidates. If not mentioned otherwise, we denote the set of candidates, the set of voters, the number of candidates, and the number of voters by C, V, m, and n respectively. Every voter has a preference which is a linear order over the set C of candidates. We say voter prefers a candidate over another candidate . We denote the set of all preferences over of the preferences of all the voters is called a profile. For a subset a sub-profile of We often view a profile P as a multi-set consisting of the preferences in P to avoid use of cumbersome notations. The view of a profile we are considering will be clear from the context. Given a preference and a positive integer , we denote the profile consisting of copies of the preference is a set of profiles. The single crossing domain is defined as follows.

Definition 1 (Single Crossing Profile). A profile preferences over a set C of candidates is called a single crossing profile if there exists a permutation such that, for every two distinct candidates , whenever we have integers

Demange significantly generalizes the single crossing domain to the single crossing domain on median graphs in [Dem12]. A graph G = (V, E) is called a median graph if, for every three nodes , there exists a unique vertex m(u, v, w), called the median of the nodes u, v, and w, which is present in the shortest paths between each pair of u, v, and w. Trees and hypercubes are important examples of median graphs. In this work, we will be concerned with trees only. A tree is a connected acyclic graph. A star is a tree where there is a central node with whom every other node is connected by an edge. We refer to [Die97] for common terminologies of trees. Given a tree T and a node , we denote the tree rooted at u by T[u]. The single crossing domain on trees is defined as follows.

Definition 2 (Single Crossing Profile on Trees). A profile P is called single crossing on trees if there exists a tree T on the set of voters such that every sub-profile along every path of T is single crossing with respect to that path.

Let a profile P be single crossing with respect to a tree T. We call T a single crossing tree of P. We denote the preference associated with a voter (which is a node in by . We denote a voter in T associated with a preference . An equivalent condition for a profile to be single crossing with respect to a tree T is that, for every pair of candidates , there exists at most one edge in the cut is the set of voters who prefer x over y [CPS15]. We now generalize the single crossing domain on trees to the weakly single crossing domain on trees as follows.

Definition 3 (Weakly Single Crossing Profile on Trees). The weakly single crossing domain on trees is the set of all profiles P such that there exists a profile which contains P and is itself single crossing with respect to a tree T.

2.1 Problem Formulation

We study the following problem for recognizing weakly single crossing profiles on trees.

Problem Definition 1 (WEAKLY SINGLE CROSSING TREE RECOGNITION). Given a profile P, does P belong to the weakly single crossing domain on trees?

Suppose we have a profile P with n voters and m candidates. Let us define a function QUERYfor a voter and two different candidates if the voter prefers the candidate x over the candidate otherwise. We now define the preference elicitation problem.

Problem Definition 2 (PREFERENCE ELICITATION). Given an oracle access to QUERYa profile P, find P.

For two distinct candidates and a voter , we say a PREFERENCE ELICITA- TION algorithm A compares candidates x and y for the voter makes a call to either QUERY. We define the number of queries made by the algorithm A, called the query complexity of A, to be the number of distinct tuples with such that the algorithm A compares the candidates x and y for the voter Notice that, even if the algorithm A makes multiple calls to QUERY () with same tuple , we count it only once in the query complexity of A. This is without loss of generality since we can always implement a “wrapper” around the oracle which memorizes all the calls made to the oracle so far and whenever it receives a duplicate call, it replies from its memory without “actually” making a call to the oracle.

The following observation is immediate from standard sorting algorithms like merge sort.

Observation 1. There is a PREFERENCE ELICITATION algorithm for eliciting one preference with query complexity O(m log m).

Model of Input for PREFERENCE ELICITATION There are two prominent models for accessing the preferences in the literature (see [DM16b]). In the random access model, we are allowed to query any preference at any point of time. Moreover, we are also allowed to interleave the queries to different voters. In the sequential access model, voters are arriving in a sequential manner one after another to the system. Once a voter arrives, we can query her preference as many times as we like and then we “release” the voter system to grab the next voter in the queue. Once the voter is released, its preference can never be queried again.

In this section, we present our polynomial time algorithm for the WEAKLY SINGLE CROSS- ING TREE RECOGNITION problem. In the interest of space, we omit a few proofs. They are available in the supplementary material. We begin with bounding the number of distinct preferences in a profile which is single crossing with respect to some tree. We remark that the exact same bound of Lemma 1 is known for the single crossing profiles [DM16b].

Lemma 1. Let a profile P of distinct preferences be single crossing with respect to a tree T. Then

Proof. Let be any edge of T = (V, E). Since the preferences in P are all distinct, the set differently} of pairs of candidates that are ordered differently by the voters u and v is nonempty. Since the profile P is single crossing with respect to T, for any two distinct edges . We also have . Now we bound |P| as follows.

The following result which is immediate from the proof of Lemma 3.7 in [CPS15], simplifies lot of our proofs.

Lemma 2. Let be a profile with be the profile resulting from P after removing all the duplicate preferences. Then P is single crossing with respect to some tree if and only if is single crossing with respect to some tree. Therefore, P is a weakly single crossing profile on trees if and only if is a weakly single crossing profile on trees. Moreover, given the tree with respect to which the profile P is single crossing, we can construct another tree with respect to which is single crossing in polynomial amount of time and vice versa.

We next define the majority relation of a set of preferences which helps us formulate an important property of single crossing domain with respect to trees. We call that property the triad majority property. This property will in turn help us in defining and finding what we call the single crossing tree closure of a weakly single crossing profile on trees. The notion of a single crossing tree closure plays a central role in our recognition and elicitation algorithms.

Definition 4 (Majority Relation). Given a profile of n preferences the relation the majority relation of the profile If the majority relation Maj(P) of a profile P turns out to be a linear order, we say that a majority order of P exists and we call Maj(P) the majority order of P.

Property 1 (Triad Majority Property). A profile P is said to satisfy the triad majority property if, for every three preferences (not necessarily distinct) the majority relation is a linear order and

We now show that every single crossing profile on trees, satisfies the triad majority property.

Lemma 3. Let P be a single crossing profile with respect to a tree T. Then P satisfies the triad majority property.

Proof. For any three preferences , let the nodes associated with in be the unique node in T that lies in the shortest paths to . We claim that the preference associated with the node u. Suppose not, then there exist two candidates . But then the sub-profile of P along the path between is not single crossing. This contradicts our assumption that P is single crossing with respect to the tree T.

We now define the notion of triad majority closure of a profile which will be used crucially in our algorithm for WEAKLY SINGLE CROSSING TREE RECOGNITION.

Definition 5 (Triad Majority Closure). The triad majority closure of any profile P is de-fined to be the inclusion-wise minimal profile ¯P that satisfies the triad majority property and contains P.

The following result shows that a triad majority closure of a sub-profile of a profile that satisfies the triad majority property, is unique thereby establishing the well-definedness of Definition 5.

Proposition 1. The triad majority closure of every profile exists and it is unique.

Proof. Let P be any profile and M(P) the set of profiles which contains P and satisfies the triad majority property. We observe that . We define ¯claim that ¯P is the triad majority closure of P. For two profiles that satisfy the triad majority property and contain P, the profile also satisfies the triad majority property and contains satisfies the triad majority property and contains P; this proves existence. For uniqueness, let us assume, if possible, that two different profiles are both triad majority closures of is also another triad majority closure of P. However, we have which contradicts our assumption that is a triad majority closure of P. Hence, the triad majority closure of P exists and it is unique.

Similar to the triad majority closure, we next define the single crossing tree closure.

Definition 6 (Single Crossing Tree Closure). Let P be a weakly single crossing profile on trees. The single crossing tree closure of P is defined to be the inclusion-wise minimal profile which is single crossing with respect to some tree.

The following result shows that, for every weakly single crossing profile P on trees, the single crossing tree closure exists and is unique, thereby establishing well-definedness of Definition 6. Moreover, turns out to be the triad majority closure of P.

Theorem 1. Let P be a weakly single crossing profile on trees. Then the triad majority closure ¯P of P is single crossing on trees. Therefore, the single crossing tree closure of P exists, it is unique, and equals to its triad majority closure ¯P. Moreover, the single crossing tree closure of P can be computed in time polynomial in the size of

Proof. We can assume, without loss of generality, that the preferences in P are all distinct due to Lemma 2. Let R be a profile of distinct preferences that is single crossing with respect to a tree T and P be a sub-profile of R – such an R exists since P is a weakly single crossing profile on trees. Let us consider the subgraph , where, for two nodes denotes the unique path between u and v in T. We observe that is actually a subtree of T since it is a connected subgraph of the tree T. We also observe that, for every leaf node , the preference corresponding to l always belongs to P. We iteratively apply the following transformation on as long as we can: if there exists a node of degree two such that the preference associated with u does not belong to P, then we “bypass” u, that is, we remove along with the two edges incident on u and add an edge between the two neighbors of u. Let us call the tree which results from after making all the transformations iteratively as long as we can. We claim that the triad majority closure ¯P of P is exactly the set Q of preferences associated with the nodes of the tree . We first observe that Q satisfies the triad majority property since Q is single crossing with respect to the tree [see Lemma 3]. Now to show that Q is the triad majority closure of P, it is enough to show that every preference majority order of some three preferences in be the node in whose corresponding preference is . We observe that the degree of is at least 3, since otherwise the transformation would have deleted u. So the degree of least 3. We make and call it , be any three neighbors of . Let the subtrees of the rooted tree observe that there must exists a node such that the preference attached to belongs to . We claim that is the majority order of otherwise we may assume (by renaming) that there exists two candidates that . However, this violates single crossing property on the path between is the majority order of . This proves the claim. Hence, Q is the triad majority closure of P. Also Q is single crossing with respect to the tree . Hence, by Lemma 3, Q is the single crossing tree closure of P. We also observe that every preference in ¯P \ P is a majority of some three (not necessarily distinct) preferences in P.

We consider the algorithm A which iteratively adds (which is initialized to empty set) for all three (not necessarily distinct) preferences inates duplicates from Q, and outputs Q so that every preference in Q are distinct. Clearly, we have . The correctness of A follows from the fact that every preference in ¯P \ P is a majority of some three (not necessarily distinct) preferences in P. The algorithm A runs in time polynomial in the size of ¯P and thus polynomial in

We will use Theorem 1 in our PREFERENCE ELICITATION algorithm for single crossing profiles on trees in Theorem 3. We believe that Theorem 1 is an important structural result for weakly single crossing profiles on trees which may be useful otherwise also.

The following result on recognizing single crossing profiles on trees is due to [CPS15].

Theorem 2. (Theorem 4.2 in [CPS15]) Given a profile P, there is a polynomial time algorithm for checking whether there exists a tree T with respect to which P is single crossing. Moreover, if a single crossing tree exists, then the algorithm also outputs a tree with respect to which P is single crossing.

Theorems 1 and 2 give us a polynomial time algorithm for the WEAKLY SINGLE CROSS-

Corollary 1. The WEAKLY SINGLE CROSSING TREE RECOGNITION problem is in P.

Proof. Let P be any profile. We need to compute if P is weakly single-crossing. Using Lemma 2, let us assume that the preferences in P are all distinct. Our algorithm A first constructs the triad majority closure ¯P of P using the algorithm in Theorem 1. While constructing ¯P iteratively in A, if we have at any point of time, we output NO. The correctness of this step follows from the fact that, if P is indeed a weakly single-crossing profile on trees, then, by Theorem 1, we have . So, let us now assume that A has constructed the triad majority closure ¯P of P and we have . Our algorithm now checks whether ¯P is single crossing with respect to some tree using Theorem 2. If the algorithm in Theorem 2 outputs YES, then A also outputs YES and the tree returned by the algorithm in Theorem 2; otherwise . The correctness of A now follows the correctness of the algorithm in Theorem 2. The polynomial running time of A follows from polynomial running time of the algorithms in Theorems 1 and 2.

In this section, we present a polynomial time low query complexity algorithm for eliciting weakly single crossing profiles on trees. We begin with bounding the degree of any node in a single crossing tree for a profile consisting of distinct preferences. We use this to bound the query complexity of our elicitation algorithm.

Lemma 4. Let a profile P of distinct preferences be single crossing with respect to a tree T. Then the degree of every node in T is at most

Proof. Consider any node v in T and let the preference associated with the node v be . Let the neighbors of the node , and the preferences associated with them be , respectively. We need to show that first observe that, for every , there exists at most one neighbor node v such that the preference associated with the node otherwise let us assume that there exist two neighbors node v such that the preferences associated with them both have and . Then the sub-profile along the path is not single crossing which contradicts our assumption that P is single crossing with respect to the tree T. Hence, for every , there exists at most one neighbor , of the node v such that the preference associated with the node . We also observe that, for every , there exists an since otherwise we have which contradicts our assumption that the preferences of the profile P are all distinct. Hence, we have 1 since otherwise we will have such that we have both due to pigeon hole argument which leads to a contradiction as argued above.

We remark that the assumption that the profile in Lemma 4 consists of distinct preferences is crucial since a profile where all the preferences are the same is single crossing with respect to every tree. We show next a structural result about trees. We will use it crucially for bounding query complexity of our elicitation algorithm.

Lemma 5. Let T be a tree of size at least 3. Then there exists a node r in T of degree at least 2 such that the following holds: make the tree T rooted at r; let the neighbors of r be ; let the rooted subtrees of be respectively

Proof. Let be any arbitrary node in satisfies the properties of the lemma, then we are done. Otherwise, let be the neighbor of such that, if we remove the edge , then the connected component containing has more than 3|T|/4 nodes. Let the removal of the edge creates two connected components satisfies the properties of the lemma, then we are done. Otherwise, we repeat the above process defining . We observe that . We continue this process until we get a node that satisfies the properties of the lemma. The process has to terminate because otherwise we have an infinite chain

This cannot happen since all the inclusions in the chain above are proper and every i. Hence, the process always terminates with a node satisfying the properties of the lemma.

Given a profile P of distinct preferences, a tree T with respect to which P is single crossing, and a preference , we now present an algorithm for finding whether belongs to T using O(m) calls to QUERY (). This algorithm is a crucial component in our PREFERENCE ELICITATION algorithm.

Lemma 6. Given a profile P of distinct preferences, a tree T with respect to which P is single crossing, and an oracle access to a preference , Algorithm 1 elicits P in polynomial time using

Proof. We present our algorithm in Algorithm 1. Let r be a node as in Lemma 5. We consider the tree T rooted at r which we denote by T[r]. Let the neighbors of r in T[r] be , for some 2 1 (the upper bound of 1 follows from Lemma 4), the rooted subtrees of 4. Since the profile P consists of distinct preferences, for every exist two candidates be the preference which we have to search in T; we can access only through the QUERY () function. We query the oracle for cannot belong to the subtree and thus we remove as done in line 6 of Algorithm 1. On the other hand, if

cannot belong to and thus we remove as is done in line 8 of Algorithm 1. Hence, after each iteration of the while loop, remains in was present at the start of the iteration. Since every iteration decreases the size of T, the algorithm terminates and is correct. We now turn our attention to the query complexity of Algorithm 1. For a tree T with n nodes where every preference is over m candidates, let T(n, m) be the query complexity of the while loop from line 1 to line 11 in Algorithm 1. Let us consider an iteration of the while loop at line 1. Let k be the number of times the for loop at line 3 iterates. If k = 1, then the algorithm makes only one query in the current iteration of the while loop in Algorithm 1 and the number of nodes in the new tree T is upper bounded by 3/4-th time the number of nodes in the previous T (by the choice of 2, we observe that the number of nodes in the new tree T is upper bounded by 1/k-th times the number of nodes in the previous T– this is because the for loop at line 3 iterates according to a nonincreasing order of subtrees. Hence, we have the following recurrence relation.

We know from Lemma 1 that 1. By solving the above recurrence with theupper bound on n and the fact that line 12 to 14 can be executed with O(m) queries (see [DM16b]), we get that the query complexity of Algorithm 1 is O(m).

We first present a PREFERENCE ELICITATION algorithm for single crossing profiles on trees when we are given a sequential access to the preference (the sequential order is a priori not known) and we do not know any tree with respect to which the input profile is single crossing.

Theorem 3. Suppose a profile P is single crossing with respect to some unknown tree T. Suppose we have only sequential access to the preferences whose ordering is also not known a priori. Then there is a PREFERENCE ELICITATION algorithm for the single crossing profiles on trees with query complexity

Proof. We present our PREFERENCE ELICITATION algorithm in Algorithm 2. We maintain an array R of length n to store the preferences of all the n voters and a set Q to store all the distinct preferences seen so far. Let be the order in which the voters are accessed. To elicit the preference of voter , we first construct, in polynomial time, a tree T with respect to which the single crossing tree closure ¯Q of Q is single crossing using Theorem 1. Next we find whether the preference of the voter is already present in T; this can be done in polynomial time with making O(m) calls to QUERYusing Lemma 6. If the preference of the voter is present in T, we have elicited Otherwise, we elicit queries by Observation 1. However, since the number of distinct preferences in any profile which is single crossing with respect to some tree is at most1 due to Lemma 1, we use Observation 1 at mostHence, the query complexity of Algorithm 2 is

Our algorithm in Theorem 3 can readily be seen to work for weakly single crossing profiles on trees too. Hence, we have the following corollary.

Corollary 2. There exists a polynomial time PREFERENCE ELICITATION algorithm for the weakly single crossing profiles on trees with query complexity

We prove next that the query complexity upper bound in Theorem 3 is optimal up to constant factors for a large number of voters (more specifically, when even if a tree T is known with respect to which the input profile P is single crossing and random access to preferences are allowed.

Theorem 4. Let a profile P be single crossing with respect to a tree T. Let T be known except for the preferences associated with the nodes of rithm has query complexity even if we are allowed to query preferences randomly and interleave the queries to different preferences arbitrarily.

Proof. The bound follows from the sorting lower bound and the fact that any profile consisting of only one preference is single crossing. Let T be a star with one central node and 1 leaf nodes attached to the central node with an edge. Suppose we have an even number of candidates, that is, even integer m. Consider the ordering and the pairing of the candidates . The oracle answers all the query requests consistently according to the ordering Q. We claim that any PREFERENCE ELICITATION algorithm A must compare for every voter corresponding to every leaf node of T and for every odd integer . Indeed, otherwise, there exist a voter corresponding to a leaf node of T and an odd integer such that the algorithm A does not compare . Suppose the algorithm outputs a profile . The oracle fixes the preference of every voter except . If the voter oracle fixes the preference otherwise the oracle fixes . The algorithm fails to correctly output the preference of the voter in both the cases. Also the final profile with the oracle is single crossing with respect to the tree T. Hence, A must compare for every voter corresponding to every leaf node of T and for every odd integer and thus has query complexity

Hence, the query complexity of PREFERENCE ELICITATION for the weakly single crossing profiles on trees, does not depend substantially on how the preferences are accessed and whether we know a single crossing tree of the single crossing closure of the input profile. This is in sharp contrast to the corresponding results for single crossing domain where the query complexity for PREFERENCE ELICITATION improves substantially if we know a single crossing ordering and we have a random access to the preferences than if we only have sequential access to preferences [DM16b]. Next, we present our lower bound on the query complexity of any PREFERENCE ELICITATION algorithm for single crossing domains in the random access model.

Theorem 5. Let a profile P be single crossing with respect to the identity permutation of the voters. Then any algorithm for eliciting P has query complexity even if we are allowed to query preferences randomly.

Proof. Any PREFERENCE ELICITATION algorithm can be viewed to be a binary decision tree. Let the set C of candidates be be any single crossing profile consisting of 2 distinct preferences; we know such a profile exists. Let R be the collection of all profiles of size n which contains multiple copies of every preference present in Q and nothing else. Then we have . Since every profile in R can be a valid input to any PREFERENCE ELICITATION algorithm A, the corresponding binary decision tree must have at least leaf vertices. Hence, the query complexity of A is the height of the corresponding binary decision tree which is at least

We have shown that, for every weakly single crossing profile on trees, there always exists a unique inclusion-minimal single crossing profile on trees containing it. We exploit this uniqueness property along with the known polynomial time recognition algorithm for single crossing profiles on trees to design a polynomial time recognition algorithm for weakly single crossing profiles on trees. We have also shown that the query complexity for preference elicitation for weakly single crossing profiles on trees is small – the query complexity bounds are similar to the corresponding bounds for single peaked [Con09] and single crossing profiles [DM16b]. Moreover, we have proved that our preference elicitation algorithm makes an optimal number of queries up to constant factors for a large number of voters. Hence, our results in this paper, along with the fact that the weakly single crossing domain on trees inherits most of the desirable properties from the single crossing domain on trees, shows that the weakly single crossing domain on trees is an important generalization of the single crossing domain on trees. An immediate future work is to extend our recognition and elicitation algorithms to the more general median graphs. Characterizing weakly single crossing profiles in trees in terms of forbidden structures is another important direction of research.

[BBHH15] Felix Brandt, Markus Brill, Edith Hemaspaandra, and Lane A Hemaspaandra. Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates. J. Artif. Intell. Res., pages 439–496, 2015.

[BC84] Douglas H Blair and David L Crawford. Labor union objectives and collective bargaining. Q. J. Econ., pages 547–566, 1984.

[BCW13] Robert Bredereck, Jiehua Chen, and Gerhard J Woeginger. A characterization of the single-crossing domain. Soc. Choice Welf., 41(4):989–998, 2013.

[BCW16] Robert Bredereck, Jiehua Chen, and Gerhard J. Woeginger. Are there any nicely structured preference profiles nearby? Math. Soc. Sci., 79:61–73, 2016.

[Bla48] Duncan Black. On the rationale of group decision-making. J. Polit. Econ., pages 23–34, 1948.

[BM11] Salvador Barber`a and Bernardo Moreno. Top monotonicity: A common root for single peakedness, single crossing and the median voter result. GEB, 73(2):345–359, 2011.

[BNM58] Duncan Black, Robert Albert Newing, Iain McLean, Alistair McMillan, and Burt L Monroe. The theory of committees and elections. Springer, 1958.

[BSU13] Nadja Betzler, Arkadii Slinko, and Johannes Uhlmann. On the computation of fully proportional representation. J. Artif. Intell. Res., 47:475–519, 2013.

[CGS12] Denis Cornaz, Lucie Galand, and Olivier Spanjaard. Bounded single-peaked width and proportional representation. In Proc. Twentieth European Conference on Artificial Intelligence (ECAI), volume 242 of Frontiers in Artificial Intelligence and Applications, pages 270–275. IOS Press, 2012.

[Con09] Vincent Conitzer. Eliciting single-peaked preferences using comparison queries. J. Artif. Intell. Res., 35:161–191, 2009.

[CPS14] Adam Clearwater, Clemens Puppe, and Arkadii Slinko. The single-crossing property on a tree. arXiv preprint arXiv:1410.2272, 2014.

[CPS15] Adam Clearwater, Clemens Puppe, and Arkadii Slinko. Generalizing the single-crossing property on lines and trees to intermediate preferences on median graphs. In Proc. 24th International Conference on Artificial Intelligence, IJCAI, pages 32–38. AAAI Press, 2015.

[CSS99] William W. Cohen, Robert E. Schapire, and Yoram Singer. Learning to order things. J. Artif. Int. Res., 10(1):243–270, May 1999.

[Dem82] Gabrielle Demange. Single-peaked orders on a tree. Mathematical Social Sciences, 3(4):389–396, 1982.

[Dem12] Gabrielle Demange. Majority relation and median representative ordering. SERIEs, 3(1-2):95–109, 2012.

[Die97] Reinhard Diestel. Graph theory. Graduate texts in mathematics. Springer, New York, Berlin, Paris, 1997. Trad. de : Graphentheorie, paru en 1996 chez Springer.

[DKNS01] Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the web. In Proc. 10th International Conference on World Wide Web, WWW ’01, pages 613–622, New York, NY, USA, 2001. ACM.

[DM16a] Palash Dey and Neeldhara Misra. Elicitation for preferences single peaked on trees. In Proc. Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pages 215–221, 2016.

[DM16b] Palash Dey and Neeldhara Misra. Preference elicitation for single crossing domain. In Proc. Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pages 222–228, 2016.

[Dod76] Charles Lutwidge Dodgson. A method of taking votes on more than two issues. 1876.

[DS74] Peter A Diamond and Joseph E Stiglitz. Increases in risk and in risk aversion. J. Econ. Theory, 8(3):337–360, 1974.

[EF14] Edith Elkind and Piotr Faliszewski. Recognizing 1-euclidean preferences: An alternative approach. In Algorithmic Game Theory - 7th International Symposium, SAGT 2014, Haifa, Israel, September 30 - October 2, 2014. Proceedings, pages 146–157, 2014.

[EFLO15a] Edith Elkind, Piotr Faliszewski, Martin Lackner, and Svetlana Obraztsova. The complexity of recognizing incomplete single-crossing preferences. In Proc. Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA., pages 865–871, 2015.

[EFLO15b] Edith Elkind, Piotr Faliszewski, Martin Lackner, and Svetlana Obraztsova. The complexity of recognizing incomplete single-crossing preferences. In Proc. Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA., pages 865–871, 2015.

[EL14] Edith Elkind and Martin Lackner. On detecting nearly structured preference profiles. In Proc. Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27 -31, 2014, Qu´ebec City, Qu´ebec, Canada., pages 661–667, 2014.

[EL15] Edith Elkind and Martin Lackner. Structure in dichotomous preferences. In Proc. Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 2019–2025, 2015.

[ELP13] G´abor Erd´elyi, Martin Lackner, and Andreas Pfandler. Computational aspects of nearly single-peaked electorates. In Proc. Twenty-Seventh AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA., 2013.

[ELP16] Edith Elkind, Martin Lackner, and Dominik Peters. Preference restrictions in computational social choice: Recent progress. In Proc. Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pages 4062–4065, 2016.

[FHH14] Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra. The complexity of manipulative attacks in nearly single-peaked electorates. Artif. Intell., 207:69–99, February 2014.

[HM97] Mel vin J Hinich and Michael C Munger. Analytical politics. Cambridge University Press, 1997.

[JSA08] Benjamin G. Jackson, Patrick S. Schnable, and Srinivas Aluru. Consensus genetic maps as median orders from inconsistent sources. IEEE/ACM Trans. Comput. Biology Bioinform., 5(2):161–171, 2008.

[Kem59] John G Kemeny. Mathematics without numbers. Daedalus, 88(4):577–591, 1959.

[Kno10] Vicki Knoblauch. Recognizing one-dimensional euclidean preference profiles. J. Math. Econ., 46(1):1–5, 2010.

[Kun15] Fan-Chin Kung. Sorting out single-crossing preferences on networks. Soc. Choice Welf., 44(3):663–672, 2015.

[Lac14] Martin Lackner. Incomplete preferences in single-peaked electorates. In Proc. Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI), pages 742–748, 2014.

[Lev75] Arthur Levenglick. Fair and reasonable election systems. Behavioral Science, 20(1):34–46, 1975.

[MG04] Vincent Merlin and Wulf Gaertner. Domain conditions in social choice theory, 2004.

[Mir71] James A Mirrlees. An exploration in the theory of optimum income taxation. Rev. Econ. Stud., pages 175–208, 1971.

[Mou91] Hervi Moulin. Axioms of cooperative decision making. Number 15. Cambridge University Press, 1991.

[MR81] Allan H Meltzer and Scott F Richard. A rational theory of the size of government. J. Polit. Econ., pages 914–927, 1981.

[Rob77] Kevin WS Roberts. Voting over income tax schedules. J Public Econ, 8(3):329– 340, 1977.

[SYFE13] Piotr Skowron, Lan Yu, Piotr Faliszewski, and Edith Elkind. The complexity of fully proportional representation for single-crossing electorates. In International Symposium on Algorithmic Game Theory, pages 1–12. Springer, 2013.

[Tri89] Michael A Trick. Recognizing single-peaked preferences on a tree. Mathematical Social Sciences, 17(3):329–334, 1989.