Preference Elicitation for Single Crossing Domain

1 Introduction

Agents in multiagent systems often have individual preferences which are complete orders over a set of candidates and one would like to find an aggregate ranking or choose the "best" candidate. Classic examples where such a scenario appears are collaborative filtering [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 finds 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 ⌦(mlogm) 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-

Neeldhara Misra

Indian Institute of Technology, Gandhinagar mail@neeldhara.com

ever, if the preferences are not completely arbitrary, but admit additional structure, then possibly we can do better. Indeed, an affirmation 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 define the notion formally later in this section).

There are two reasons for restricting the domain of preferences. The first 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 defining 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 satisfies 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 difficulties 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 difficulties that we outlined above. The domains of single peaked and single crossing profiles 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 al., 2014; Brandt et al., 2015, and references therein]. A profile is called single peaked if the candidates can be arranged in a complete order ￿ such that every preference ￿′ in the profile 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 profile 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 finding 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 ⌦(mn logm) queries even to decide the winner for many commonly used voting rules which matches with the trivial Ο(mnlogm) 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 affirmative, and one can indeed elicit the preferences of the voters using only Ο(mn) many queries for the domain of single peaked preference profiles [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 profiles in various settings. We consider two distinct situations: when an ordering of the voters with respect to which the profile 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-defined sequence. In the sequential access model, we distinguish two cases when the ordering is known: the first 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 profiles; 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 Ο(m). We summarize our results in Table 1.

2 Preliminaries

Single Crossing Domain A profile Π = (￿1↪ ▷ ▷ ▷ ↪ ￿n) of n voters over a set Χ of candidates is called a single crossing profile if there exists a permutation σ ∈ Sn of [n] such that, for every two distinct candidates x↪ y ∈ Χ, 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 definition of single crossing profiles.

For a positive integer `, we denote the set {1↪ ▷ ▷ ▷ ↪ `} by [`]. Let ς = {vi ∶ i ∈ [n]} be a set of n voters and Χ = {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 Χ , ς , m, and n respectively. Every voter vi has a preference ￿i which is a complete order over the set Χ of candidates. We say voter vi prefers a candidate x ∈ Χ over another candidate y ∈ Χ if x ￿i y. We denote the set of all preferences over Χ by Λ(Χ). The n-tuple (￿i)i∈[n] ∈ Λ(Χ)n of the preferences of all the voters is called a profile. 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 specified otherwise.

Observation 1 Suppose a profile Π is single crossing with respect to an ordering σ ∈ Sn of votes. Then Π is single crossing with respect to the ordering ←￿σ too.

Problem Formulation Suppose we have a profile Π with n voters and m candidates. Let us define 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 define the problem.

Definition 1 PREFERENCE ELICITATION

For two distinct candidates x↪ y ∈ Χ and a voter ` , we say a PREFERENCE ELICITATION algorithm Α compares candidates x and y for voter ` , if Α makes a call to either QUERY(x ￿` y) or QUERY(y ￿` x). We define the number of queries made by the algorithm Α , called the query complexity of Α , to be the number of distinct tuples (`↪ x↪ y) ∈ ς × Χ × Χ with x ≠ y such that the algorithm Α compares the candidates x and y for voter ` . Notice that, even if the algorithm Α makes multiple calls to QUERY(⋅) with same tuple (`↪ x↪ y), we count it only once in the query complexity of Α . 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) ￿ `.

Given an oracle access to QUERY(⋅) for a single crossing profile Π , find Π .

Ο(mn+m3 logm) Corollary 1 ⌦(mlogm+mn) Theorem 6

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

Model of Input We study two models of input for PREFERENCE ELICITATION for single crossing profiles.

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

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

3 Results

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 first 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 profile Π 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 Ο(m2 log n).

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

Now, for every ￿m2 ￿ pair of candidates {x↪ y} ⊂ Χ, we perform a binary search over the votes to find 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})

Theorem 1 Suppose a profile Π is single crossing with respect to the identity permutation of votes. Given random access to voters, any PREFERENCE ELICITATION algorithm has query complexity ⌦(m log m + m log n).

and thus we have found Π. ￿ Interestingly, the simple algorithm in Lemma 1 turns out to be optimal up to a multiplicative factor of Ο(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 (logm-1) queries involving only these two candidates x and y. We formalize this idea below.

Proof: The ⌦(mlogm) bound follows from the query complexity lower bound of sorting and the fact that any profile consisting of only one preference ￿∈ Λ(Χ) is single crossing. Let Χ = {c1↪ ▷ ▷ ▷ ↪ cm} be the set of m candidates where m is an even integer. Consider the ordering Q = c1 ￿ c2 ￿ ￿ ￿ cm ∈ Λ(Χ) and the following pairing of the candidates: {c1↪ c2}↪ {c3↪ c4}↪ ▷ ▷ ▷ ↪ {cm-1↪ cm}. Our oracle answers QUERY(⋅) as follows. The oracle fixes 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 fixed if ￿` - ✓i￿ ￿ ￿` - βi￿ and otherwise answers ci+1 ￿ ci and updates βi to ` keeping ✓i fixed (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 (logn - 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 profile 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 (logn - 1) queries for the pair (ci↪ ci+1) thereby making ⌦(mlogn) 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 first 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 Ο(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 Ο(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 fixed, because for these pairs, the one permitted crossing is now used up. We begin with presenting an important subroutine called Elicit(⋅) which finds the preference of a voter ` given another preference Ρ by performing an insertion sort using Ρ as the order of insertion.

Output: Preference ordering ￿` of voter ` on Χ

Algorithm 1 Elicit(Χ , Ρ , ` ) Input: A set of candidates Χ = {ci ∶ i ∈ [m]}, an ordering Ρ = c1 ￿ ￿ ￿ cm of Χ , a voter `

• 1: Θ← c1 ▷Θ will be the preference of the voter `
• 5: return Θ
• 2: for i ← 2 to mdo ▷ ci is inserted in the ith iteration 3: Scan Θ linearly from index i-1 to 1 to find the index j where ci should be inserted according to the preference of voter ` and insert ci in Θ at j 4: end for

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) ∈ Χ × Χ↪ 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: goodCost(⋅) and badCost(⋅) which are the number of queries made between good and respectively bad pair of candidates. In what follows, we show that goodCost(⋅) for Elicit(⋅) is small and the total badCost(⋅) across all the runs of Elicit(⋅) is small.

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

Lemma 2 The goodCost(Elicit(Χ↪Ρ↪ `)) of Elicit(Χ↪Ρ↪ `) is Ο(m) (good is with respect to the preferences Ρ and ￿`).

We now use Algorithm 1 iteratively to find the profile. 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 PreferenceElicit(⇡)

Input: ⇡ ∈ Sn Output: Profile of all the voters

• 2: Ξ ← {⇡(1)} ▷ Set of voters' whose preferences have already been elicited
• 1: Θ[⇡(1)] ← Elicit ￿⇡(1) using Observation 2 ▷ Θ stores the profile
• 3: for i ← 2 to n do ▷Elicit the preference of voter ⇡(i) in iteration i
• 5: Ρ←Θ[k]↪Ξ ←Ξ ∪ {⇡(i)} 6: Θ[⇡(i)] ← Elicit(Χ↪Ρ↪ ⇡(i)) 7: end for
• 4: k ←minj∈Ξ ￿j - i￿ ▷ Find the closest known preference
• 8: return Θ

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 profile Π is single crossing with respect to idn. Let the profile Π be (P1↪P2↪ ▷ ▷ ▷ ↪Pn) ∈ Λ(Χ)n . For two candidates x↪ y ∈ Χ and a voter i ∈ {2↪ ▷ ▷ ▷ ↪ n}, let us define a variable b(x↪ y↪ i) to be one if x and y are compared for the voter i by Elicit(Χ ,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 defined to be zero. Then we have the following.

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

The first inequality follows from Lemma 2, the second equality follows from the definition of b(x↪ y↪ i), and the second inequality follows from the fact that ∑ni=2 b(x↪ y↪ i) ￿ 1 for every pair of candidates (x↪ y) ∈ Χ since the profile Π 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.

Proof: The ⌦(mlogm) bound follows from the fact that any profile consisting of only one preference P ∈ Λ(Χ) is single crossing. By renaming, let us assume without loss of generality that the profile Π is single crossing with respect to the identity permutation of the voters. Suppose we have an even number of candidates and Χ = {c1↪ ▷ ▷ ▷ ↪ cm}. Consider the order Θ = 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 first 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 first 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 Θ′ . 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 Θ . Clearly, the elicitation algorithm fails to correctly elicit the preference of the voter . However, the profiles 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(Χ↪Ρ↪ i) where the current voter is the voter i and Ρ is the preference of the voter which is closest to i according to a single crossing ordering and whose preference has already been elicited

Theorem 3 Assume that the voters are arriving sequentially according to an order with respect to which a profile Π is single crossing. Then any PREFERENCE ELICITATION algorithm has query complexity ⌦(m log m + mn).

by the algorithm.

Theorem 4 Assume that a profile Π 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 Ο(mn + m2 log n).

Proof: By renaming, let us assume, without loss of generality, that the profile Π is single peaked with respect to the identity permutation of the voters. Let the profile Π be (P1↪P2↪ ▷ ▷ ▷ ↪Pn) ∈ Λ(Χ)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 ∈ Χ and voter `, we define b(x↪ y↪ `) analogously as in the proof of Theorem 2. We claim that B(x↪ y) = ∑ni=2 b(x↪ y↪ i) ￿ logn. To see this, we consider any arbitrary pair (x↪ y) ∈ Χ × Χ. Let the set of indices of the voters that have arrived immediately after the first 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 define ∆ 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∆) = Ο(logn) 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 profiles when no single crossing ordering is known. Before we present our PREFERENCE ELICITATION algorithm for this setting, let us first prove a few structural results about single crossing profiles which we will use crucially later. We begin with showing an upper bound on the number of distinct preferences in any single crossing profile.

Lemma 3 Let Π be a profile on a set Χ of candidates which is single crossing. Then the number of distinct preferences in Π is at most ￿m2 ￿ + 1.

We show next that in every single crossing profile Π where all the preferences are distinct, there exists a pair of candidates (x↪ y) ∈ Χ × Χ such that nearly half of the voters in Π prefer x over y and the other voters prefer y over x.

Proof: By renaming, let us assume, without loss of generality, that the profile Π 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) ∈ Χ × Χ 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) ∈ Χ ×Χ, 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. ￿

Lemma 4 Let Π be a profile of n voters such that all the preferences are distinct. Then there exists a pair of candidates (x↪ y) ∈ Χ 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 Π .

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

(x↪ y) ∈ Χ × Χ 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 profile Π 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 Θ of all the distinct preferences that we have already elicited completely and we have to elicit the preference of a voter `. We first search the set of votes Θ for a preference which is possibly same as the preference ￿` of the voter `. It turns out that we can find a possible match ￿∈ Θ using Ο(log ￿Θ￿) queries due to Lemma 4 which is Ο(log m) due to Lemma 3. We then check whether the preference of the voter ` is indeed the same as ￿ or not using Ο(m) queries. If ￿ is the same as ￿`, then we have elicited ￿` using Ο(m) queries. Otherwise, we elicit ￿` using Ο(mlogm) queries using Observation 2. Fortunately, Lemma 3 tells us that we would use the algorithm in Observation 2 at most Ο(m2 ) times. We present the pseudocode of our PREFERENCE ELICITATION algorithm in this setting in Algorithm 4.

Algorithm 3 Same(Ρ , ` ) Input: Ρ = c1 ￿ c2 ￿ ￿ ￿ cm ∈ Λ(Χ)↪ ` ∈ [n] Output: TRUE if the preference of the `th voter is Ρ ; FALSE otherwise 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 profile Π is known to be single crossing. However, no ordering of the voters with respect to which Π 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 Ο(mn + m3 log m). Proof: We present the pesudocode in Algorithm 4. We maintain two arrays in the algorithm. The array Ρ is of length n and the j th entry stores the preference of voter j. The other array Θ stores all the votes seen so far after removing duplicate votes; more specifically, if some specific preference ￿ has been seen ` many times for any ` > 0, Θ stores only one copy of ￿. Upon arrival of voter i, we first check whether there is a preference in Θ which is "potentially" same as the preference of voter i. At the beginning of the search, our search space Θ′ = Θ for a potential match in Θ is of size ￿Θ￿. We next iteratively keep halving the search space as follows. We find a pair of candidates (x↪ y) ∈ Χ×Χ such that at least ￿￿Θ′ ￿￿2￿ preferences in Θ′ prefer x over y and at least ￿￿Θ′ ￿￿2￿ preferences prefer y over x. The existence of such a pair of candidates is guaranteed by Lemma 4 and can be found in Ο(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 Θ′

Algorithm 4 PreferenceElicitUnknownSCOrdering(⇡)

for a potential match in Θ to a set of size at most ￿￿Θ′ ￿￿2￿ + 1. Hence, in Ο(logm) queries, the search space reduces to only one preference since we have ￿Θ￿ ￿ m2 by Lemma 3. Once we find a potential match w in Θ (line 12 in Algorithm 4), we check whether the preference of voter i is the same as w or not using Ο(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 Ο(mlogm) queries and put the preference of voter i in Θ . Since the number of times we need to use the algorithm in Observation 2 is at most the number of distinct votes in Π which is known to be at most m2 by Lemma 3, we get the statement.

• Input: ⇡ ∈ Sn Output: Profile of all the voters 1: Ρ↪Θ←￿ ▷Θ stores all the votes seen so far without duplicate. Ρ stores the profile. 2: for i ← 1 to n do ▷Elicit preference of the ith voter in ith iteration of this for loop. 3: Θ′ ←Θ 4: while ￿Θ′ ￿ > 1 do ▷Search Θ to find a vote potentially same as the preference of ⇡(i) 5: Let x↪ y ∈ Χ be two candidates such that at least ￿￿Θ′ ￿￿2￿ votes in Θ′ prefer x over y and at least ￿￿Θ′ ￿￿2￿ votes in Θ′ prefer y over x. 6: if QUERY(x ￿⇡(i) y) = TRUE then 7: Θ′ ← {v ∈ Θ′ ∶ v prefers x over y} 8: else 9: Θ′ ← {v ∈ Θ′ ∶ v prefers y oer x} 10: end if 11: end while 12: Let w be the only vote in Θ′ ▷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: Ρ[⇡(i)] ← w 15: else 16: Ρ[⇡(i)] ← Elicit using Observation 2 17: Θ ← Θ ∪ {Ρ[⇡(i)]} 18: end if 19: end for 20: return Ρ

￿ 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 profile Π is known to be single crossing. However, no ordering of the voters with respect to which Π is single crossing is known. Given a random access to voters, there is an PREFERENCE ELICITATION algorithm with query complexity Ο(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 profile is single crossing has query complexity ⌦(mlogm+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).