# preference_elicitation_for_single_crossing_domain__38e041d2.pdf

Preference Elicitation for Single Crossing Domain

Palash Dey Indian Institute of Science, Bangalore

palash@csa.iisc.ernet.in

Neeldhara Misra Indian Institute of Technology, Gandhinagar

mail@neeldhara.com

Abstract Eliciting the preferences of a set of agents over a set of alternatives is a problem of fundamental importance in social choice theory. Prior work on this problem has studied the query complexity of preference elicitation for the unrestricted domain and for the domain of single peaked preferences. In this paper, we consider the domain of single crossing preference proﬁles and study the query complexity of preference elicitation under various settings. We consider two distinct situations: when an ordering of the voters with respect to which the proﬁle is single crossing is known versus when it is unknown. We also consider random and sequential access models. The main contribution of our work is to provide polynomial time algorithms with low query complexity for preference elicitation in all the above cases. Further, we show that the query complexities of our algorithms are optimal up to constant factors for all but one of the above cases.

1 Introduction

Agents in multiagent systems often have individual preferences which are complete orders over a set of candidates and one would like to ﬁnd an aggregate ranking or choose the best candidate. Classic examples where such a scenario appears are collaborative ﬁltering [Pennock et al., 2000] etc. In a typical such setting, we have a set of agents or voters; each of them has a preference, called a vote, over a set of candidates; and a voting rule (respectively an aggregation function) which ﬁnds a candidate (respectively an aggregated preference) called winner.

However, eliciting the preferences of the agents is a nontrivial task since we often have a large number of candidates (ranking restaurants for example) and it may often be infeasible for the agents to rank all of them. Hence it becomes important to elicit the preferences of the agents by asking them (hopefully a small number of) comparison queries only - ask an agent i to compare two candidates x and y.

Unfortunately, it turns out that one would need ask every voter (mlog m) queries to know her preference, and this argument is based on the decision-tree based lower bound on the number of comparisons for sorting an array. How-

ever, if the preferences are not completely arbitrary, but admit additional structure, then possibly we can do better. Indeed, an afﬁrmation of this thought comes from the work of [Conitzer, 2009], who showed that we can elicit preferences using only O(m) queries per voter for what are called single peaked preferences (which is a well-studied restriction on preferences, and we will deﬁne the notion formally later in this section).

There are two reasons for restricting the domain of preferences. The ﬁrst is that in several application scenarios commonly considered, it is rare that votes are ad-hoc, demonstrating no patterns whatsoever. For example, the notion of singlepeaked preferences forms the basis of several studies in the analytical political sciences [Hinich and Munger, 1997].

The second motivation for studying restricted preferences comes from the fact that they are very well-behaved from a theoretical perspective as well. The axiomatic approach of social choice involves deﬁning certain properties that formally capture the quality of a voting rule. For example, we would not want a voting rule to be, informally speaking, a dictatorship, which would essentially mean that it discards all but one voter s input. As it happens, a series of cornerstone results establish that it is impossible to devise voting rules which respect some of the simplest desirable properties. Celebrated results in social choice theory [Arrow, 1950; Gibbard, 1973; Satterthwaite, 1975] show that it is impossible to have an aggregation function or a voting rule that simultaneously satisﬁes a desirable set of properties, for example, strategy-proofness, ontoness, non-dictatorship etc. We refer the reader to [Moulin, 1991] for an excellent exposition of all key issues that arise in this context. Adding to the difﬁculties is the fact that many important voting rules such as Kemeny [Kemeny, 1959; Levenglick, 1975], Dodgson [Dodgson, 1876; Black et al., 1958], and Young [Young, 1977] are computationally intractable [Bartholdi III et al., 1989; Hemaspaandra et al., 2005; Procaccia et al., 2008].

This brings us to the second important reason for considering structured preferences they provide a very elegant workaround to the difﬁculties that we outlined above. The domains of single peaked and single crossing proﬁles are arguably the most important and well-studied domains among such restricted domains [Saporiti and Tohm e, 2006; Ballester and Haeringer, 2011; Cornaz et al., 2013; Skowron et al., 2013; Magiera and Faliszewski, 2014; Faliszewski et

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-16)

al., 2014; Brandt et al., 2015, and references therein]. A proﬁle is called single peaked if the candidates can be arranged in a complete order such that every preference in the proﬁle respects the order in the sense that, for every two candidates x and y, we have x y whenever we have either c x y or y x c, where c is the most preferred candidate in [Black, 1948]. On the other hand a proﬁle is called single crossing if the voters can be arranged in a complete order such that for every two candidates x and y, all the voters who prefer x over y appear consecutively in [Mirrlees, 1971; Roberts, 1977].

Elicitation on Restricted Domains. Conitzer and Sandholm show that determining whether we have enough information at any point of the elicitation process for ﬁnding a winner under some common voting rules is computationally intractable [Conitzer and Sandholm, 2002]. They also prove in their classic paper [Conitzer and Sandholm, 2005] that one would need to make (mnlog m) queries even to decide the winner for many commonly used voting rules which matches with the trivial O(mnlog m) upper bound (based on sorting) for preference elicitation in unrestricted domain. Dey and Misra proved tight query complexity bounds for preferences single peaked on trees with respect to various tree parameters [Dey and Misra, 2016a].

A natural question at this point is if these restricted domains allow for better elicitation algorithms as well. The answer to this is in the afﬁrmative, and one can indeed elicit the preferences of the voters using only O(mn) many queries for the domain of single peaked preference proﬁles [Conitzer, 2009]. Our work belongs to this kind of research we investigate the number of queries one has to ask for preference elicitation in single crossing domains. When some partial information is available about the preferences, Ding and Lin prove interesting properties of what they call a deciding set of queries [Ding and Lin, 2013]. Lu and Boutilier empirically show that several heuristics often work well [Lu and Boutilier, 2011b; 2011a].

Contributions. In this paper we present novel algorithms for preference elicitation for the domain of single crossing proﬁles in various settings. We consider two distinct situations: when an ordering of the voters with respect to which the proﬁle is single crossing is known versus when it is unknown. We also consider different access models: when the votes can be accessed at random, as opposed to when they are coming in a pre-deﬁned sequence. In the sequential access model, we distinguish two cases when the ordering is known: the ﬁrst is that sequence in which the votes appear is also a single-crossing order, versus when it is not. We also prove lower bounds on the query complexity of preference elicitation for the domain of single crossing proﬁles; these bounds match the upper bounds up to constant factors (for a large number of voters) for all the six scenarios above except the case when we know a single crossing ordering of the voters and we have a random access to the voters; in this case, the upper and lower bounds match up to a factor of O(m). We summarize our results in Table 1.

2 Preliminaries For a positive integer , we denote the set {1,..., } by [ ]. Let V = {vi i [n]} be a set of n voters and C = {cj j [m]} 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 voters by C , V , m, and n respectively. Every voter vi has a preference i which is a complete order over the set C of candidates. We say voter vi prefers a candidate x C over another candidate y C if x i y. We denote the set of all preferences over C by L(C). The n-tuple ( i)i [n] L(C)n of the preferences of all the voters is called a proﬁle. We say a candidate x is placed at the kth position of a preference if x is preferred over all but exactly (k 1) other candidates in . Let Sn denote the set of all permutations over [n] and idn be the identity permutation of [n]. Let an ordering σ be x1 x2 x . Then by σ we denote the ordering x x2 x1. All the logarithms in this paper are base 2 unless speciﬁed otherwise.

Single Crossing Domain A proﬁle P = ( 1,..., n) of n voters over a set C of candidates is called a single crossing proﬁle if there exists a permutation σ Sn of [n] such that, for every two distinct candidates x,y C, whenever we have x σ(i) y and x σ(j) y for two integers i and j with 1 i < j n, we have x σ(k) y for every i k j. The following observation is immediate from the deﬁnition of single crossing proﬁles.

Observation 1 Suppose a proﬁle P is single crossing with respect to an ordering σ Sn of votes. Then P is single crossing with respect to the ordering σ too.

Problem Formulation Suppose we have a proﬁle P with n voters and m candidates. Let us deﬁne a function QUERY(x y) for a voter and two different candidates x and y to be TRUE if the voter prefers the candidate x over the candidate y and FALSE otherwise. We now formally deﬁne the problem.

Deﬁnition 1 PREFERENCE ELICITATION Given an oracle access to QUERY( ) for a single crossing proﬁle P , ﬁnd P .

For two distinct candidates x,y C and a voter , we say a PREFERENCE ELICITATION algorithm A compares candidates x and y for voter , if A makes a call to either QUERY(x y) or QUERY(y x). We deﬁne the number of queries made by the algorithm A , called the query complexity of A , to be the number of distinct tuples ( ,x,y) V C C with x y such that the algorithm A compares the candidates x and y for voter . Notice that, even if the algorithm A makes multiple calls to QUERY( ) with same tuple ( ,x,y), 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. We say two query complexities q(m,n) and q (m,n) are tight up to a factor of for a large number of voters if 1 limn q(m,n) q (m,n) .

Ordering Access model Query Complexity Upper Bound Lower Bound

Random O(m2 log n) Lemma 1 (mlog m + mlog n) Theorem 1 Sequential single crossing order O(mn + m2) Theorem 2

(mlog m + mn) Theorem 3 Sequential any order O(mn + m2 log n) Theorem 4

Unknown Sequential any order O(mn + m3 log m) Theorem 5 Random O(mn + m3 log m) Corollary 1 (mlog m + mn) Theorem 6

Table 1: Summary of Results for preference elicitation for single crossing proﬁles.

Note that by using a standard sorting routine like merge sort, we can fully elicit an unknown preference using O(mlog m) queries. We state this explicitly below, as it will be useful in our subsequent discussions.

Observation 2 There is a PREFERENCE ELICITATION algorithm for eliciting a single preference with query complexity O(mlog m).

Model of Input We study two models of input for PREFERENCE ELICITATION for single crossing proﬁles.

Random access to voters: In this model, we have a set

of voters and we are allowed to ask any voter to compare any two candidates at any point of time. Moreover, we are also allowed to interleave the queries to different voters. Random access to voters is the model of input for elections within an organization where every voter belongs to the organization and can be queried any time.

Sequential access to voters: In this model, voters are

arriving in a sequential manner one after another to the system. Once a voter arrives, we can query voter as many times as we like and then we release the voter from the system to grab the next voter in the queue. Once voter is released, it can never be queried again. Sequential access to voters is indeed the model of input in many practical elections scenarios such as political elections, restaurant ranking etc.

In this section, we present our technical results. In the interest of space, we defer the proofs of a few results to the full version of the paper [Dey and Misra, 2016b]. We ﬁrst consider the (simpler) situation when the single crossing order is known, and then turn to the case when the order is unknown. In both cases, we explore all the relevant access models.

3.1 Results: Known Single Crossing Order We begin with a simple PREFERENCE ELICITATION algorithm when we are given a random access to the voters and a single crossing ordering is known.

Lemma 1 Suppose a proﬁle P is single crossing with respect to a known permutation of the voters. Given a random access to voters, there is a PREFERENCE ELICITATION algorithm with query complexity O(m2 log n).

Proof: By renaming, we assume that the proﬁle is single crossing with respect to the identity permutation of the votes.

Now, for every m

2 pair of candidates {x,y} C, we perform a binary search over the votes to ﬁnd the index i({x,y}) where the ordering of x and y changes. We now know how any voter j orders any two candidates x and y from i({x,y}) and thus we have found P. Interestingly, the simple algorithm in Lemma 1 turns out to be optimal up to a multiplicative factor of O(m) as we prove next. The idea is to pair up the candidates and design an oracle which hides the vote where the ordering of the two candidates in any pair (x,y) changes unless it receives at least (log m 1) queries involving only these two candidates x and y. We formalize this idea below.

Theorem 1 Suppose a proﬁle P is single crossing with respect to the identity permutation of votes. Given random access to voters, any PREFERENCE ELICITATION algorithm has query complexity (mlog m + mlog n).

Proof: The (mlog m) bound follows from the query complexity lower bound of sorting and the fact that any proﬁle consisting of only one preference L(C) is single crossing. Let C = {c1,...,cm} be the set of m candidates where m is an even integer. Consider the ordering Q = c1 c2 cm L(C) and the following pairing of the candidates: {c1,c2},{c3,c4},...,{cm 1,cm}. Our oracle answers QUERY( ) as follows. The oracle ﬁxes the preferences of the voters one and n to be Q and Q respectively. For every odd integer i [m], the oracle maintains i (respectively βi) which corresponds to the largest (respectively smallest) index of the voter for whom (ci,ci+1) has already been queried and the oracle answered that the voter prefers ci over ci+1 (ci+1 over ci respectively). The oracle initially sets i = 1 and βi = n for every odd integer i [m]. Suppose oracle receives a query to compare candidates ci and cj for i,j [m] with i < j for a voter . If i is an even integer or j i 2 (that is, ci and cj belong to different pairs), then the oracle answers that the voter prefers ci over cj. Otherwise we have j = i + 1 and i is an odd integer. The oracle answers the query to be ci ci+1 and updates i to keeping βi ﬁxed if i βi and otherwise answers ci+1 ci and updates βi to keeping i ﬁxed (that is, the oracle answers according to the vote which is closer to the voter between i and βi and updates i or βi accordingly). If the pair (ci,ci+1) is queried less than (log n 2) times, then we have βi i 2 at the end of the algorithm since every query for the pair (ci,ci+1) decreases βi i by at most a factor of two and we started with βi i = n 1. Consider a voter with i < < βi. If the elicitation algorithm outputs that the voter prefers ci over ci+1 (respectively ci+1 over ci), then the oracle sets all

the voters with i < < βi to prefer ci+1 over ci (respectively ci over ci+1). Clearly, the algorithm does not elicit the preference of the voter correctly. Also, the proﬁle is single crossing with respect to the identity permutation of the voters and consistent with the answers of all the queries made by the algorithm. Hence, for every odd integer i [m], the algorithm must make at least (log n 1) queries for the pair (ci,ci+1) thereby making (mlog n) queries in total. We now present our PREFERENCE ELICITATION algorithm when we have a sequential access to the voters according to a single crossing order. We elicit the preference of the ﬁrst voter using Observation 2. From second vote onwards, we simply use the idea of insertion sort relative to the previously elicited vote [Cormen, 2009]. Since we are using insertion sort, any particular voter may be queried O(m2) times. However, we are able to bound the query complexity of our algorithm due to two fundamental reasons: (i) consecutive preferences will often be almost similar in a single crossing ordering, (ii) our algorithm takes only O(m) queries to elicit the preference of the current voter if its preference is indeed the same as the preference of the voter preceding it. In other words, every time we have to pay for shifting a candidate further back in the current vote, the relative ordering of that candidate with all the candidates that it jumped over is now ﬁxed, because for these pairs, the one permitted crossing is now used up. We begin with presenting an important subroutine called Elicit( ) which ﬁnds the preference of a voter given another preference R by performing an insertion sort using R as the order of insertion.

Algorithm 1 Elicit(C , R , ) Input: A set of candidates C = {ci i [m]}, an ordering

R = c1 cm of C , a voter Output: Preference ordering of voter on C

1: Q c1 Q will be the preference of the voter 2: for i 2 to m do ci is inserted in the ith iteration 3: Scan Q linearly from index i 1 to 1 to ﬁnd the index j where ci should be inserted according to the preference of voter and insert ci in Q at j 4: end for 5: return Q

For the sake of the analysis of our algorithm, let us to introduce a few terminologies. Given two preferences 1 and 2, we call a pair of candidates (x,y) C C,x y, good if both 1 and 2 order them in a same way; a pair of candidates is called bad if it is not good. We divide the number of queries made by our algorithm into two parts: good Cost( ) and bad Cost( ) which are the number of queries made between good and respectively bad pair of candidates. In what follows, we show that good Cost( ) for Elicit( ) is small and the total bad Cost( ) across all the runs of Elicit( ) is small.

Lemma 2 The good Cost(Elicit(C,R, )) of Elicit(C,R, ) is O(m) (good is with respect to the preferences R and ).

Proof: Follows immediately from the observation that in any iteration of the for loop at line 2 in Algorithm 1, only one good pair of candidates are compared.

We now use Algorithm 1 iteratively to ﬁnd the proﬁle. We present the pseudocode in Algorithm 2 which works for the more general setting where a single crossing ordering is known but the voters are arriving in any arbitrary order . We next compute the query complexity of Algorithm 2 when voters are arriving in a single crossing order.

Algorithm 2 Preference Elicit( ) Input: Sn Output: Proﬁle of all the voters

1: Q[ (1)] Elicit (1) using Observation 2 Q stores

the proﬁle 2: X { (1)} Set of voters whose preferences have already been elicited 3: for i 2 to n do Elicit the preference of voter (i) in

iteration i 4: k minj X j i Find the closest known preference 5: R Q[k],X X { (i)} 6: Q[ (i)] Elicit(C,R, (i)) 7: end for 8: return Q

Theorem 2 Assume that the voters are arriving sequentially according to an order with respect to which a proﬁle P is single crossing. Then there is a PREFERENCE ELICITATION algorithm with query complexity O(mn + m2).

Proof: By renaming, let us assume, without loss of generality, that the voters are arriving according to the identity permutation idn of the voters and the proﬁle P is single crossing with respect to idn. Let the proﬁle P be (P1,P2,...,Pn) L(C)n. For two candidates x,y C and a voter i {2,...,n}, let us deﬁne a variable b(x,y,i) to be one if x and y are compared for the voter i by Elicit(C ,Pi 1, i) and (x,y) is a bad pair of candidates with respect to the preferences of voter i and i 1; otherwise b(x,y,i) is deﬁned to be zero. Then we have the following.

Cost Preference Elicit(idn)

= O(mlog m) +

n i=2(good Cost(QUERY(C,Pi 1,i)) +

bad Cost(QUERY(C,Pi 1,i)))

O(mlog m + mn) +

bad Cost(QUERY(C,Pi 1,i))

= O(mlog m + mn) + (x,y) C C

O(mlog m + mn) + (x,y) C C

= O(mn + m2)

The ﬁrst inequality follows from Lemma 2, the second equality follows from the deﬁnition of b(x,y,i), and the second inequality follows from the fact that n

i=2 b(x,y,i) 1 for every pair of candidates (x,y) C since the proﬁle P is single crossing.

We show next that, when the voters are arriving in a single crossing order, the query complexity upper bound in Theorem 3 is tight for a large number of voters up to constant factors. The idea is to pair up the candidates in a certain way and argue that the algorithm must compare the candidates in every pair for every voter thereby proving a (mn) lower bound on query complexity.

Theorem 3 Assume that the voters are arriving sequentially according to an order with respect to which a proﬁle P is single crossing. Then any PREFERENCE ELICITATION algorithm has query complexity (mlog m + mn).

Proof: The (mlog m) bound follows from the fact that any proﬁle consisting of only one preference P L(C) is single crossing. By renaming, let us assume without loss of generality that the proﬁle P is single crossing with respect to the identity permutation of the voters. Suppose we have an even number of candidates and C = {c1,...,cm}. Consider the order Q = c1 c2 cm and the pairing of the candidates {c1,c2},{c3,c4},...,{cm 1,cm}. The oracle answers all the query requests consistently according to the order Q till the ﬁrst voter for which there exists at least one odd integer i [m] such that the pair (ci,ci+1) is not queried. If there does not exist any such , then the algorithm makes at least mn 2 queries thereby proving the statement. Otherwise, let be the ﬁrst vote such that the algorithm does not compare ci and ci+1 for some odd integer i [m]. The oracle answers the queries for the rest of the voters { +1,...,n} according to the order Q = c1 c2 ci 1 ci+1 ci ci+2 cm. If the algorithm orders ci ci+1 in the preference of the voter , then the oracle sets the preference of the voter to be Q . On the other hand, if the algorithm orders ci+1 ci in the preference of voter , then the oracle sets the preference of voter to be Q . Clearly, the elicitation algorithm fails to correctly elicit the preference of the voter . However, the proﬁles for both the cases are single crossing with respect to the identity permutation of the voters and are consistent with the answers given to all the queries made by the algorithm. Hence, the algorithm must make at least mn 2 queries. We next move on to the case when we know a single crossing order of the voters; however, the voters arrive in an arbitrary order Sn. The idea is to call the function Elicit(C,R,i) where the current voter is the voter i and R is the preference of the voter which is closest to i according to a single crossing ordering and whose preference has already been elicited by the algorithm.

Theorem 4 Assume that a proﬁle P is known to be single crossing with respect to a known ordering of voters σ Sn. However, the voters are arriving sequentially according to an arbitrary order Sn which may be different from σ. Then there is a PREFERENCE ELICITATION algorithm with query complexity O(mn + m2 log n).

Proof: By renaming, let us assume, without loss of generality, that the proﬁle P is single peaked with respect to the identity permutation of the voters. Let the proﬁle P be (P1,P2,...,Pn) L(C)n. Let f [n] [n] be the function such that f(i) is the k corresponding to the i at line 4 in Algorithm 2. For candidates x,y C and voter , we

deﬁne b(x,y, ) analogously as in the proof of Theorem 2. We claim that B(x,y) = n

i=2 b(x,y,i) log n. To see this, we consider any arbitrary pair (x,y) C C. Let the set of indices of the voters that have arrived immediately after the ﬁrst time (x,y) contributes to B(x,y) be {i1,i2,...,it}. Without loss of generality, let us assume i1 < i2 < < it. Again, without loss of generality, let us assume that voters i1,i2,...,ij prefer x over y and voters ij+1,...,it prefer y over x. Let us deﬁne to be the difference between smallest index of the voter who prefers y over x and the largest index of the voter who prefers x over y. Hence, we currently have = ij+1 ij. A crucial observation is that if a new voter contributes to B(x,y) then we must necessarily have ij < < ij+1. Another crucial observation is that whenever a new voter contributes to B(x,y), the value of gets reduced at least by a factor of two by the choice of k at line 4 in Algorithm 2. Hence, the pair (x,y) can contribute at most (1 + log ) = O(log n) to B(x,y) since we have n to begin with. The rest of the proof is along the same line of the proof of Theorem 2.

3.2 Results: Unknown Single Crossing Order We now turn our attention to PREFERENCE ELICITATION for single crossing proﬁles when no single crossing ordering is known. Before we present our PREFERENCE ELICITATION algorithm for this setting, let us ﬁrst prove a few structural results about single crossing proﬁles which we will use crucially later. We begin with showing an upper bound on the number of distinct preferences in any single crossing proﬁle.

Lemma 3 Let P be a proﬁle on a set C of candidates which is single crossing. Then the number of distinct preferences in P is at most m

Proof: By renaming, let us assume, without loss of generality, that the proﬁle P is single crossing with respect to the identity permutation of the voters. We now observe that whenever the ith vote is different from the (i + 1)th vote for some i [n 1], there must exist a pair of candidates (x,y) C C whom the ith vote and the (i + 1)th vote order differently. Now the statement follows from the fact that, for every pair of candidates (a,b) C C, there can exist at most one i [n 1] such that the ith vote and the (i + 1)th vote order a and b differently.

We show next that in every single crossing proﬁle P where all the preferences are distinct, there exists a pair of candidates (x,y) C C such that nearly half of the voters in P prefer x over y and the other voters prefer y over x.

Lemma 4 Let P be a proﬁle of n voters such that all the preferences are distinct. Then there exists a pair of candidates (x,y) C such that x is preferred over y in at least n 2 preferences and y is preferred over x in at least n 2 preferences in P .

Proof: Without loss of generality, by renaming, let us assume that the proﬁle P is single crossing with respect to the identity permutation of the voters. Since all the preferences in P are distinct, there exists a pair of candidates

(x,y) C C such that the voter n 2 and the voter n 2 + 1 order x and y differently. Let us assume, without loss of generality, that the voter n 2 prefers x over y. Now, since the proﬁle P is single crossing, every voter in [ n 2 ] prefer x over y and every voter in { n 2 +1,...,n} prefer y over x.

Using Lemma 3 and 4 we now design a PREFERENCE ELICITATION algorithm when no single crossing ordering of the voters is known. The overview of the algorithm is as follows. At any point of time in the elicitation process, we have the set Q of all the distinct preferences that we have already elicited completely and we have to elicit the preference of a voter . We ﬁrst search the set of votes Q for a preference which is possibly same as the preference of the voter . It turns out that we can ﬁnd a possible match Q using O(log Q ) queries due to Lemma 4 which is O(log m) due to Lemma 3. We then check whether the preference of the voter is indeed the same as or not using O(m) queries. If is the same as , then we have elicited using O(m) queries. Otherwise, we elicit using O(mlog m) queries using Observation 2. Fortunately, Lemma 3 tells us that we would use the algorithm in Observation 2 at most O(m2) times. We present the pseudocode of our PREFERENCE ELICITATION algorithm in this setting in Algorithm 4.

Algorithm 3 Same(R , ) Input: R = c1 c2 cm L(C), [n] Output: TRUE if the preference of the th voter is R ; FALSE oth-

erwise 1: for i 1 to m 1 do 2: if QUERY(ci ci+1) = FALSE then 3: return FALSE We have found a mismatch. 4: end if 5: end for 6: return TRUE

Theorem 5 Assume that a proﬁle P is known to be single crossing. However, no ordering of the voters with respect to which P is single crossing is known. The voters are arriving sequentially according to an arbitrary order Sn. Then there is a PREFERENCE ELICITATION algorithm with query complexity O(mn + m3 log m). Proof: We present the pesudocode in Algorithm 4. We maintain two arrays in the algorithm. The array R is of length n and the jth entry stores the preference of voter j. The other array Q stores all the votes seen so far after removing duplicate votes; more speciﬁcally, if some speciﬁc preference has been seen many times for any > 0, Q stores only one copy of . Upon arrival of voter i, we ﬁrst check whether there is a preference in Q which is potentially same as the preference of voter i. At the beginning of the search, our search space Q = Q for a potential match in Q is of size Q . We next iteratively keep halving the search space as follows. We ﬁnd a pair of candidates (x,y) C C such that at least Q 2 preferences in Q prefer x over y and at least Q 2 preferences prefer y over x. The existence of such a pair of candidates is guaranteed by Lemma 4 and can be found in O(m2) time by simply going over all possible pairs of candidates. By querying how voter i orders x and y, we reduce the search space Q

Algorithm 4 Preference Elicit Unknown SCOrdering( ) Input: Sn Output: Proﬁle of all the voters

1: R, Q Q stores all the votes seen so far without duplicate. R stores the proﬁle. 2: for i 1 to n do Elicit preference of the ith voter in ith

iteration of this for loop. 3: Q Q 4: while Q > 1 do Search Q to ﬁnd a vote potentially same as the preference of (i) 5: Let x, y C be two candidates such that at least Q 2 votes in Q prefer x over y and at least Q 2 votes in Q prefer y over x. 6: if QUERY(x (i) y) = TRUE then 7: Q {v Q v prefers x over y} 8: else 9: Q {v Q v prefers y oer x} 10: end if 11: end while 12: Let w be the only vote in Q w is potentially same as the preference of (i) 13: if Same(w, (i)) = TRUE then Check whether the vote (i) is potentially same as w 14: R[ (i)] w 15: else 16: R[ (i)] Elicit using Observation 2 17: Q Q {R[ (i)]} 18: end if 19: end for 20: return R

for a potential match in Q to a set of size at most Q 2 + 1. Hence, in O(log m) queries, the search space reduces to only one preference since we have Q m2 by Lemma 3. Once we ﬁnd a potential match w in Q (line 12 in Algorithm 4), we check whether the preference of voter i is the same as w or not using O(m) queries. If the preference of voter i is indeed same as w, then we output w as the preference of voter i. Otherwise, we use Observation 2 to elicit the preference of voter i using O(mlog m) queries and put the preference of voter i in Q . Since the number of times we need to use the algorithm in Observation 2 is at most the number of distinct votes in P which is known to be at most m2 by Lemma 3, we get the statement. Theorem 5 immediately gives us the following corollary in the random access to voters model when no single crossing ordering is known.

Corollary 1 Assume that a proﬁle P is known to be single crossing. However, no ordering of the voters with respect to which P is single crossing is known. Given a random access to voters, there is an PREFERENCE ELICITATION algorithm with query complexity O(mn + m3 log m).

We now show that the query complexity upper bound of Corollary 1 is tight up to constant factors for large number of voters.

Theorem 6 Given a random access to voters, any PREFERENCE ELICITATION algorithm which do not know any ordering of the voters with respect to which the input proﬁle is single crossing has query complexity (mlog m + mn).

Acknowledgments. Palash Dey wishes to gratefully acknowledge support from Google India for providing him with a special fellowship for carrying out his doctoral work. Neeldhara Misra acknowledges support by the INSPIRE Faculty Scheme, DST India (project IFA12-ENG-31).

References [Arrow, 1950] Kenneth J Arrow. A difﬁculty in the concept of so-

cial welfare. The Journal of Political Economy, pages 328 346, 1950. [Ballester and Haeringer, 2011] Miguel A Ballester and Guillaume

Haeringer. A characterization of the single-peaked domain. Social Choice and Welfare, 36(2):305 322, 2011. [Bartholdi III et al., 1989] John Bartholdi III, Craig A Tovey, and

Michael A Trick. Voting schemes for which it can be difﬁcult to tell who won the election. Social Choice and welfare, 6(2):157 165, 1989. [Black et al., 1958] Duncan Black, Robert Albert Newing, Iain

Mc Lean, Alistair Mc Millan, and Burt L Monroe. The theory of committees and elections. Springer, 1958. [Black, 1948] Duncan Black. On the rationale of group decision-

making. The Journal of Political Economy, pages 23 34, 1948. [Brandt et al., 2015] Felix Brandt, Markus Brill, Edith Hemaspaan-

dra, and Lane A Hemaspaandra. Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates. Journal of Artiﬁcial Intelligence Research (JAIR), pages 439 496, 2015. [Conitzer and Sandholm, 2002] Vincent Conitzer and Tuomas Sandholm. Vote elicitation: Complexity and strategy-proofness. In Eighteenth National Conference on Artiﬁcial Intelligence (AAAI), pages 392 397, 2002. [Conitzer and Sandholm, 2005] Vincent Conitzer and Tuomas Sandholm. Communication complexity of common voting rules. In Proceedings of the 6th ACM conference on Electronic Commerce (EC), pages 78 87. ACM, 2005. [Conitzer, 2009] Vincent Conitzer. Eliciting single-peaked preferences using comparison queries. J. Artif. Intell. Res. (JAIR), 35:161 191, 2009. [Cormen, 2009] Thomas H Cormen. Introduction to algorithms. MIT press, 2009. [Cornaz et al., 2013] Denis Cornaz, Lucie Galand, and Olivier

Spanjaard. Kemeny elections with bounded single-peaked or single-crossing width. In Proceedings of the Twenty-Third International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 76 82. AAAI Press, 2013. [Dey and Misra, 2016a] Palash Dey and Neeldhara Misra. Elicita-

tion for preferences single peaked on trees. In Proceedings of the Twenty-Fifth International Joint Conference on Artiﬁcial Intelligence (IJCAI). AAAI Press, 2016. [Dey and Misra, 2016b] Palash Dey and Neeldhara Misra. Prefer-

ence elicitation for single crossing domain. https://arxiv.org/abs/ 1604.05194, 2016. [Ding and Lin, 2013] Ning Ding and Fangzhen Lin. Voting with

partial information: what questions to ask? In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1237 1238. International Foundation for Autonomous Agents and Multiagent Systems, 2013. [Dodgson, 1876] Charles Lutwidge Dodgson. A method of taking

votes on more than two issues. 1876.

[Faliszewski et al., 2014] Piotr Faliszewski, Edith Hemaspaandra,

and Lane A Hemaspaandra. The complexity of manipulative attacks in nearly single-peaked electorates. Artiﬁcial Intelligence, 207:69 99, 2014. [Gibbard, 1973] Allan Gibbard. Manipulation of voting schemes: a

general result. Econometrica: Journal of the Econometric Society, pages 587 601, 1973. [Hemaspaandra et al., 2005] Edith Hemaspaandra, Holger Spakowski, and J org Vogel. The complexity of kemeny elections. Theoretical Computer Science, 349(3):382 391, 2005. [Hinich and Munger, 1997] Melvin J Hinich and Michael C Munger. Analytical politics. Cambridge University Press, 1997. [Kemeny, 1959] John G Kemeny. Mathematics without numbers.

Daedalus, 88(4):577 591, 1959. [Levenglick, 1975] Arthur Levenglick. Fair and reasonable election

systems. Behavioral Science, 20(1):34 46, 1975. [Lu and Boutilier, 2011a] Tyler Lu and Craig Boutilier. Robust ap-

proximation and incremental elicitation in voting protocols. In IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artiﬁcial Intelligence (IJCAI), pages 287 293, 2011. [Lu and Boutilier, 2011b] Tyler Lu and Craig Boutilier. Vote elici-

tation with probabilistic preference models: Empirical estimation and cost tradeoffs. In Algorithmic Decision Theory, pages 135 149. 2011. [Magiera and Faliszewski, 2014] Krzysztof Magiera and Piotr Fal-

iszewski. How hard is control in single-crossing elections. Proceedings of the 21st European Conference on Artiﬁcial Intelligence (ECAI), 2014. [Mirrlees, 1971] James A Mirrlees. An exploration in the theory of

optimum income taxation. The review of economic studies, pages 175 208, 1971. [Moulin, 1991] Hervi Moulin. Axioms of cooperative decision mak-

ing. Number 15. Cambridge University Press, 1991. [Pennock et al., 2000] David M. Pennock, Eric Horvitz, and C. Lee

Giles. Social choice theory and recommender systems: Analysis of the axiomatic foundations of collaborative ﬁltering. In Proceedings of the 17th International Conference on Artiﬁcial Intelligence (AAAI), 2000. [Procaccia et al., 2008] Ariel D Procaccia, Jeffrey S Rosenschein,

and Aviv Zohar. On the complexity of achieving proportional representation. Social Choice and Welfare, 30(3):353 362, 2008. [Roberts, 1977] Kevin WS Roberts. Voting over income tax sched-

ules. Journal of Public Economics, 8(3):329 340, 1977. [Saporiti and Tohm e, 2006] Alejandro Saporiti and Fernando Tohm e. Single-crossing, strategic voting and the median choice rule. Social Choice and Welfare, 26(2):363 383, 2006. [Satterthwaite, 1975] Mark Allen Satterthwaite. Strategy-proofness

and arrow s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic Theory, 10(2):187 217, 1975. [Skowron et al., 2013] Piotr Skowron, Lan Yu, Piotr Faliszewski,

and Edith Elkind. The complexity of fully proportional representation for single-crossing electorates. In Symposium Algorithmic Game Theory (SAGT), pages 1 12. Springer, 2013. [Young, 1977] H Peyton Young. Extending condorcet s rule. Jour-

nal of Economic Theory, 16(2):335 353, 1977.