Efficient Vote Elicitation under Candidate Uncertainty

1 Introduction

Social choice has provided valuable foundations for the development of computational approaches to preference aggregation, group decision making and a variety of other problems in recent years. As algorithmic advances and data accessibility make the methods of social choice more broadly applicable, relaxing the assumptions of classical models to fit a richer class of practical problems becomes imperative. To this end, research has begun to address the informational demands of preference aggregation. For example, recent work has considered models in which information about the set of available candidates is imperfect [Lu and Boutilier, 2010; Baldiga and Green, 2011; Boutilier et al., 2012]. Similarly, knowledge of voter preferences may be incomplete [Konczak and Lang, 2005; Xia and Conitzer, 2008; Lu and Boutilier, 2011b].

In this work, we bring together these two lines of research to investigate the feasibility and value of top-k voting. Our first motivation is to use intelligent vote elicitation techniques to minimize the amount of voter preference information required to determine the winner in an election (or more broadly, the desired outcome of a group decision). Vote elicitation has received considerable attention recently [Conitzer and Sandholm, 2005; Conitzer, 2009; Kalech et al., 2011; Lu and Boutilier, 2011b; 2011c; Ding and Lin, 2012], and has proven to be effective in reducing the amount of information-and corresponding cognitive and communication burden-needed to determine winners in practice. Our second motivation is to develop methods that handle uncertainty in the set of available candidates. In many settings, voters may need to specify their preferences over a range of potential candidates prior to knowing which are in fact available or viable for selection [Lu and Boutilier, 2010; Baldiga and Green, 2011; Boutilier et al., 2012]. Examples include ranking job candidates, public projects, or even restaurants. The potential impact of candidate unavailability on vote elicitation is clear: since certain desirable alternatives may turn out to be unavailable, one may need to elicit more preference information than is typical in the case of fully known candidates in order to ensure the correct winner is chosen.

We address the problems of efficient preference elicitation in this context in the form of top-k elicitation. In top-k voting, agents are asked to provide the length k prefix of their preference ranking instead of their full ranking. In the standard "known candidates" model, top-k voting has been used heuristically [Kalech et al., 2011] and the optimal choice of k has been analyzed from a sample-complexity-theoretic perspective [Lu and Boutilier, 2011c]. However, bounds on the required values of k for specific preference distributions and voting rules have remained unaddressed, as has the impact of unavailable candidates on top-k voting.

In this work, we examine two common voting rules, plurality and Borda-these serve as a useful starting point for the investigation of our model, representing rather different extremes in space of so-called scoring rules for voting. Given a prior distribution on the preference profile, and a distribution over the set of available candidates (for which the standard "known candidates" model is a special case), we ask: what is the minimal value of k for which top-k voting determines the true winner (with high probability), with respect to the underlying preference profile? We provide theoretical results, in the form of upper and lower bounds on k, for both worstcase preferences and certain preference distributions (including impartial culture and Mallows distributions). As a special case, we consider zero-elicitation protocols, where k = 0. We show when, as a function of the election parameters, the true winner can be determined with high probability without eliciting any information from voters. We also provide empirical results demonstrating the extent to which top-k voting determines true winners as a function of k.

2 The Model

Let C = {c1, . . . , cm} be the set of (potential) candidates from which a winner is to be selected using some voting rule. Let N = {1, . . . , n} be the set of voters, and let voter i's preference πi be a permutation of C: intuitively, for 1 ≤ j < j ′ ≤ m, πi(j) is preferred by i to πi(j ′ ). Let L denote the set of all preferences over C. A preference profile π = (π1, . . . , πn) ∈ Ln represents the collection of voter preferences. A voting rule v : Ln × 2C → C selects a winner from C given a vote profile and a set of available candidates.

We consider two voting rules: plurality and Borda. In plurality voting, given a profile π, the plurality score of candidate c is the number of times that c is ranked first: scP (c,π) = |{i ∈ N : πi(1) = c}|. The plurality winner is the candidate with maximal plurality score (ties can be handled arbitrarily; the tie-breaking rule used does not impact our results). In Borda voting, the Borda score of c is the number of candidates ranked below it, summed over all preferences πi: scB (c, π) = ∑i∈N [m-π-1 i (c)]. The Borda winner is the candidate with maximal Borda score.

Unavailable Candidates. Recent attention has been paid to the possibility of voting over a slate of potential candidates C, prior to determining the availability of the actual set of candidates A ⊆ C. When determining the availability of candidates is costly or risky (e.g., making job offers, determining feasibility of public projects, calling restaurants for reservations), it often makes sense to elicit voter preferences prior to determining availability. Once preferences are known, one can focus availability determination on candidates most likely to be winners relative to the true available set A [Lu and Boutilier, 2010; Baldiga and Green, 2011; Boutilier et al., 2012]. Following these recent models, we assume that each candidate c ∈ C is available i.i.d. with some fixed probability p ∈ (0, 1]. The use of a fixed p simplifies our presentation; but using distinct probabilities pc for different candidates c does not change the nature of our results-all can be adapted accordingly.

Given a set A ⊆ C of available candidates, a reduced preference πi|A is obtained by restricting πi to the candidates in A; we denote by π|A the reduced preference profile obtained in this way. Plurality and Borda voting in the unavailable candidate model are defined in the obvious way, using the scores obtained relative to the reduced profile. Notice that in the unavailable candidates model, it is no longer sufficient to run plurality voting by eliciting just the top-ranked candidate from each voter: in general the entire ranking may be needed.

Top-k voting. Recent research has focused on the use of intelligent preference elicitation schemes to minimize the burden on voters and obviate the need to provide full preference rankings. One especially natural approach is top-k voting, in which voters are asked to list only their k most preferred candidates (or the k-th prefix of their ranking) [Kalech et al., 2011; Lu and Boutilier, 2011b; 2011c]. We discuss below alternative ways in which such votes can be used to determine winners; but here we adopt an especially simple approach.

Given a voting rule v and some k ∈ [m], we denote by (π(k) ) = (π(k) 1 , . . . , π(k) n ) the k-truncated preference profile.

We use this truncated profile to determine plurality scores in the obvious fashion, by counting the number of first place rankings. We compute Borda scores by assigning a score of ˜m - π-1 i (c) to any candidate c in voter i's k-truncated vote, where ˜m is the number of available candidates, and a score of zero otherwise. In the unavailable candidates model, we employ the same technique, restricting the truncated vote to the available set A. Our goal is to determine values of k that suffice to determine the true winner (with high probability) relative to the true (untruncated) preference profile.

If candidates are always available (i.e., p = 1) then k = 1 is sufficient to determine the correct plurality winner, and general top-k voting is of no value. By contrast, the possibility of unavailable candidates intuitively requires that one use larger values of k for plurality and other voting rules.

Probabilistic preference models. It has become increasingly common to analyze voting rules under the assumption that agent preferences are drawn from a prior distribution over permutations. One important class of distributions, widely used in psychometrics, statistics, and machine learning, is the Mallows ϕ-distribution [Mallows, 1957; Marden, 1995]. It is described by two parameters: a reference ranking ˆπ ∈ L, and a dispersion parameter ϕ (controlling variance). The probability of a permutation π under this model is Pr(π) = ϕτ(π,ˆπ)/Zm, where τ(π, ˆπ) is the Kendalltau distance,

and Zm is a normalization constant. Importantly, when ϕ = 1, one obtains the uniform distribution over L, the socalled impartial culture (IC) assumption, a modeling assumption widely used in social choice.

Related Work. As mentioned, vote elicitation has attracted considerable recent attention, usually in the context of standard "known available candidate" models. Of particular relevance is work on top-k voting. Unlike our model, in which we "zero out" the scores of unavailable candidates, other work has treated the uncertainty in the missing candidates more cautiously. Kalech et al. [2011] use top-k ballots to determine possible and necessary winners [Konczak and Lang, 2005] and develop heuristic elicitation schemes to extend these ballots to quickly identify true winners for several different voting rules. Lu and Boutilier [2011b] use minimax regret to measure error in winner determination and to guide elicitation heuristically as well. Both methods show good empirical performance (and handle general partial votes) but provide no theoretical guarantees on the required values of k. The optimal choice of k has been analyzed from a sample-complexity-theoretic perspective by Lu and Boutilier [2011c], who provide bounds on the required number of sampled profiles needed to estimate the required value of k for arbitrary distributions; but this does not provide direct bounds on k itself. Theoretical communication complexity results show that Borda (and other rank-based rules) cannot benefit from the use of top-k voting in the worst-case [Conitzer and Sandholm, 2005], a point to which we return below.

None of the models above consider candidate unavailability. The idea of voting with unavailable candidates was considered by Lu and Boutilier [2010] and Baldiga and Green

[2011], who study the impact of missing candidates on the fidelity of a winner using voting rules such as Borda, and how close ranking policies for selecting winners approximate the true winner. More general querying policies, assuming costly availability tests, were studied by Boutilier et al. [2012]. Unavailable candidate models also bear a strong connection to the study of manipulation by candidate addition and deletion [Hemaspaandra et al., 2007; Bartholdi III et al., 1992]. These models do not consider partial preferences. Chevalyre et al. [2010] analyze the possible and necessary winner problem under (general) partial preferences, when new candidates are added to an election, for several voting rules, but do not consider elicitation or quantifying the amount of information needed to determine a necessary winner.

Our results. In most of our theoretical bounds, we say that a value of k produces a correct winner with high probability (w.h.p.) if the probability that top-k voting returns the true (full profile) winner is 1 - o(1), where o(1) → 0 as m → ∞. For plurality, we provide an upper bound of O(logm) on the k that produces the correct winner w.h.p., if n is polynomial in m, even if the preference profile is selected by an adversary. If n is exponentially larger than m, we show that under impartial culture we require k = Θ(log m), while k = Ω(m) is needed in the worst case. For Borda, we show that for a sufficiently large n (polynomial in m), k is Ω(m/ logm) under impartial culture, even if p = 1; and it has a lower-bound of k = Ω(m) in the worst case. Our top-k results are summarized in Table 1.

We also consider the case where preferences are distributed according to a Mallows model with reference ranking ˆπ. In this model, we provide theoretical results for the special case of k = 0, in other words zero elicitation protocols. We provide lower bounds on the required number of voters n needed to find winners w.h.p., as a function of ϕ and m. For plurality, we show that if n = Ω(logm/(1 - ϕ)3 ), then the top candidate in ˆπ is the winner w.h.p. For Borda, we derive a lower bound of lnm · Γ(ϕ) on n, where Γ(ϕ) = (8(1 + ϕ)2 (1 - ϕ)3 + (1 + ϕ))/(1 - ϕ)7 .

We support our theoretical findings by testing the performance of top-k voting (including the special case of zero elicitation) under varying parameter values (k, n, m, ϕ). Our empirical results suggest that when the dispersion parameter is bounded away from 1, fairly low values of k are sufficient for correct winner determination.

Space limitations preclude the inclusion of proofs of certain results. Omitted proofs can be found in an extended version of this paper. 1

1 See www.cs.toronto.edu/∼cebly/papers.html.

3 Top-k Voting and Plurality Scoring

We start with a theoretical analysis of the performance of top-k voting with plurality scoring, assessing the values of k needed to determine the true plurality winner w.h.p. As noted above, if the candidate availability probability p is 1, setting k = 1 trivially guarantees correct winner selection. Therefore, in this section we assume that p is a fixed probability, bounded away from 1. We distinguish: (a) worst-case results, in which an adversarial preference profile is selected to minimize the odds of correct winner selection, and expectations are taken over available candidate sets A; and (b) averagecase results, in which profiles are drawn from some distribution (e.g., impartial culture), and expectations are taken over both profiles and available sets.

We first show that, even in the worst case, when the number of voters n is "small" relative to the number of candidates m, a small value of k suffices for plurality:

Theorem 1 (Worst-case upper bound, poly. n). If n = poly(m), then top-k voting with k = O(logm) determines the correct plurality winner w.h.p. in the worst case.

Proof. Consider a vote π ∈ L. Set k = 2 logn/ log( 1 1-p ). The probability that all top-k candidates are unavailable is 1/n2 . Taking a union bound over all votes, the probability that some vote has all top-k candidates unavailable is 1 - 1/n = 1 - o(1).

Since this O(logm) upper bound applies in the worst case, it also applies to the average case for any profile distribution. However, in the worst case, having n sub-exponential in m is required if we want a small k.

Theorem 2 (Worst-case lower bound, exp. n). If n = exp(poly(m)), top-k voting requires k = Ω(m) to determine the correct plurality winner w.h.p. in the worst-case.

Proof. Let C = {c1, . . . , cm} ∪ {a, b}, and p = 1/2. A key observation is that the unavailable set has size at least m/2 with probability very close to 1/2 (we assume for simplicity that m is even). We create a scenario in which a and b have very close plurality scores, requiring a large value of k to tell which has the higher score. Consider the set H = {S ⊆ C : |S| = m/2} containing all subsets of C of size m/2. We show that k ≥ m/2 is required. Create two sets of votes:

1. V1: This set ensures a and b have the two highest scores if they are available (which occurs with constant probability, so assume both are). Let t = 2 · |H|, and for a set S ⊆ C, let lin(S) be an arbitrary ordering of S. Create t + 1 copies of a > lin(C \ {a}), and t copies of b ≻ lin(C \ b). Note: a gets one more vote than b in V1.
2. V2: For every S ∈ H, create two copies of the ranking lin(S) ≻ b ≻ a ≻ lin(C \ (S ∪ {a, b})).

Now, suppose the unavailable set has size at least m/2. The plurality score of a is t+1, the score of b is at least t+2, and so b is the true winner. Otherwise, the score of a is t+1, that of b is t, and a is the winner. (All other candidates have score at most t.) If k ≤ m/2 then the voting scheme doesn't see b in the set V2, and so it gives incorrect results with probability roughly p2/2.

Thus, for large n, we must set k ≥ m/2 in the worstcase. However, under impartial culture, a small value of k = O(logm) again suffices for the average case:

Theorem 3 (Avg. case upper bound, exp. n). If n = exp(Ω(m)), then top-k voting with k = O(log m) determines the correct plurality winner w.h.p. under impartial culture.

Proof. Let V be an arbitrary vote profile. Partition V into two sets: V1 = {πi ∈ V : one of πi(1), . . . , πi(k) is available}, V2 = V \ V1. Let A ⊆ C be the available set, let ˜m = |A|, n1 = |V1|, n2 = |V2|. For c ∈ C, let scP1 (c) and scP2 (c) be its plurality scores in elections (V1,A), (V2,A), respectively. W.l.o.g., order candidates based on scP1 (·): scP1 (c1) ≥ scP1 (c2) ≥ · · · ≥ scP1 (c ˜m). We prove that c1 is the true winner w.h.p.

By a simple Chernoff-bound argument, m·p 2 ≤ ˜m≤ 2m·p, w.h.p. Similarly, a simple calculation shows that E[n2] = n · (1 - p)k , and using a Chernoff bound we obtain n2 ≤ 2n · (1 - p)k w.h.p. Hence, n1 ≥ n - 2n · (1 - p)k w.h.p.

We now give an anti-concentration argument about the difference between the scores according to V1. We let D1 i,j = scP1 (ci) - scP1 (cj) (we define D2 i,j similarly).

Proof. After conditioning on A, consider the votes V1 sequentially. By a simple balls and bins argument, the difference between the scores of ci and cj increases by 1 due to vote πt (t = 1, . . . , n1) with probability 1/ ˜m, decreases by 1 with probability 1/ ˜m, and does not change with probability 1 - 2/ ˜m. We can thus treat this change as a random variable Xt, rewriting D1 i,j = ∑n1 t=1 Xt, where Xt = 1,Xt = -1 each with probability 1/ ˜m, and Xt = 0 with probability 1 - 2/ ˜m. Then V ar(Xt) = E[X2 i ] = 2˜m , E[D1 i,j ] = 2n1 ˜m , and ρ = E[|Xt|3 ] = 2 ˜m . The Berry-Esseen Theorem allows us to prove that D1 1,2 (and hence D1 1,j for every j s.t. cj ∈ A) is "large enough."

Lemma 5 (Berry-Esseen [Korolev and Shevtsova, 2010]). Let X = X1+· · ·+Xn be the sum of i.i.d. zero-mean random variables s.t. E[X2 i ] = σ2 > 0, E[|Xi|3 ] = ρ < ∞. Let Fn(·) be the cdf of X, and let Φ(·) be the cdf of the normal distribution. Then:

where 0 < C ≤ 0.4784.

In our case: Cρ σ3√n = C √n1 · 2˜m · ( ˜m2 )3/2 = C ′ ·√ ˜m n1 . Hence, we may assume that D1 i,j is effectively given by the normal distribution N(0, σ2 = 2n1 ˜m ), which gives us:

Setting t = √n1 ˜m3.5 and taking the union bound over all possible pairs (i, j) gives D1 1,2 = Ω( n1 m3.5 ) with probability

1-O(1/ ˜m) = 1-o(1), where the last equality follows from the concentration bound on ˜m.

A concentration bound on D2 1,j (for all cj ∈ A \ {c1}) follows from a Chernoff bound and a union bound over all j:

We now summarize by showing that, w.h.p., D1 1,2 > D2 1,j :

As m > ˜m and √m > 1, it suffices to show:

The above holds (for n,m sufficiently large) if we set (1 - p)k = m-8 , which gives k = O(logm), as required.

A matching lower-bound shows this upper-bound is tight:

Theorem 6 (Avg. case lower bound). If n = exp(Ω(m)), k = Ω(logm) is necessary for top-k voting to produce the true plurality winner w.h.p. under impartial culture.

Proof. The proof is largely symmetric to the proof of the upper-bound. We use the same notation as in the previous proof. We first provide an upper-bound on the difference between the score of the highest-ranking candidate and the second-highest. As before, order C based on their scores in V1: scP1 (c1) > scP1 (c2) . . . (for completeness, let unavailable candidates have score 0). Also, recall that D1 i,j = scP1 (ci) - scP1 (cj). The following lemma asserts that the top two scores are likely to be close to one another. 2

Proof. Let A ⊆ C be the available set (|A| = ˜m), and partition A into two (roughly) equal size sets: A1,A2 ⊂ A, such that |A1| = ⌊ ˜m/2⌋ , |A2| = ⌈ ˜m/2⌉. Define two random variables: t1 = maxc∈A1 scP1 (c), t2 = maxc∈A2 scP1 (c). It it easy to see that D1 1,2 ≤ |t1 - t2|, so we prove the claim by upper-bounding the r.h.s. of the inequality. The number of the votes in V1 that rank candidates in A1 (A2) first is bounded away from n1/2 by O(√n1) w.h.p. So the score of each candidate in A1 and A2 is distributed according to a typical balls-and-bins process, in which n1/2 ± o(n1) balls are thrown into ˜m/2 bins, at random. Using Thm. 1 of [Raab and Steger, 1998], we have |ti - E[ti]| = Θ (√ n1 log ˜m ˜m √(1 - (1 + ϵ) log log ˜m 2 log ˜m )), for ϵ > 0 w.h.p., for i = 1, 2. Using our bounds on ˜m, n1, and the approximation √1-x = 1 - Θ(x), we derive |t1 - t2| = O(√ n·log m m log logm logm ) = O( n log2 logm logm ), w.h.p.

Lemma 8. Let k = o(logm). Then D2 2,1 = Ω(√n/m) with constant probability.

2 We thank Neal Young for the idea of the proof.

The proof is similar to that of Lemma 4.

To summarize, we see that top-k voting can be very effective for plurality voting with the possibility of unavailable candidates under the impartial culture model, requiring elicitation of only the O(logm) most-preferred candidates from each voter to ensure the correct winner w.h.p. (this upper bound is tight). If one wants worst-case assurances, this same bound suffices for "small" elections (with a number of voters polynomial in n); but for "large" elections (with an exponential number of voters), top-k voting offers no savings.

4 Top-k Voting and Borda Scoring

We now turn our attention to Borda scoring, and provide similar results. As with plurality, we begin with a worst-case lower bound on k. We note that the following result follows quite directly from a general result on the (deterministic) communication complexity of any rank-based voting rule: Conitzer and Sandholm [2005] show that such rules require O(nmlogm) bits of communication in the worst case (i.e., essentially elicitation of full rankings). However, we provide a direct construction for Borda.

Theorem 9 (Worst case lower bound). Top-k voting requires k = Ω(m) to determine the correct Borda winner w.h.p. in the worst-case, even when p = 1.

Proof. Assume for simplicity that |C| is odd and larger than 5. Let A be an available set and C = {c} ∪ A for some designated candidate c. Let π be an arbitrary ordering of A, and πr its reverse. Let (π1, π2) be a profile with two votes, where π1 and π2 are obtained by placing c between the candidates ranked in positions m-1 2 - 1 and m-1 2 in each of π and πr . If k = m-1 2 - 1, c will not be the top-k Borda winner, even though it is the true Borda winner-its average score is m+1 2 , whereas the average score of all other candidates is m-1 2 .

We now provide an average-case lower bound on k under the impartial culture assumption.

Theorem10 (Avg. case lower bound). If n = Ω(m3 ·logm), then k = Ω(m/ logm) is necessary for top-k voting to produce the true Borda winner w.h.p. under impartial culture, even when p = 1.

Sketch of Proof We provide a brief proof sketch. The proof idea is similar to that for plurality: we upper bound the observed difference in score between the winner and any other candidate under top-k voting. We then show that with constant probability, the score difference between winner and the second-highest candidate vanishes as a result of the vote truncation due to top-k voting. Given the true Borda scores scBi (·) of the candidates in vote πi, let αi(c) = scBi (c) if scBi (c) ≥ m - k, and αi = 0, otherwise. That is, αi(c) is the Borda score of c under top-k voting. Similarly, let βi(c) = scBi (c) if scBi (c) < m- k and βi(c) = 0 otherwise; i.e., βi(c) reflects the score that is "lost" due to the truncation caused by top-k voting. We let α(c) = ∑i∈N αi(c) and β(c) = ∑i∈N βi(c). Finally, for any two distinct candidates c, c′ ∈ C, let DT (c, c′ ) = α(c) - α(c′ ) and DB (c, c′ ) = β(c) - β(c′ ). We argue that if c and c′ are the highest and second-highest scoring candidates under topk voting, if k = o(m/ logm), DT (c, c′ ) < DB (c′ , c) with constant probability.

Lemma 11. If k = o(m/ logm), then for all c, c′ ∈ C, DT (c, c′ ) = o(√n m log m ) with high probability.

The above lemma can be proved by bounding the variance of DT (c, c′ ) and applying the Bernstein inequality.

Next, we claim that difference in uncounted scores due to truncation can be greater than this observed gap between the highest and second-highest scores, impacting the true winner.

Lemma 12. If k = O(m/ logm) then DB (c′ , c) = Ω(m√n) with constant probability, where c and c′ are the candidates with the highest and second-highest scores.

The proof of Lemma 12 is similar to Lemma 4 (albeit somewhat more involved) and requires the bounding of the second and third moment of DB (c′ , c) and making use of the Berry-Esseen theorem.

Combining Lemma 11 and Lemma 12 we see that D(c, c′ ) = DB (c, c′ ) + DT (c, c′ ) < 0 with constant probability, which proves the theorem.

To summarize, top-k voting cannot ease the elicitation burden in Borda elections in the worst case. Under impartial culture, there is hope for some elicitation savings for elections of reasonable size, as indicated by our lower bound of k = Ω(m/ logm), which suggests that O(m/ logm) might suffice. But these savings are not nearly as substantial as in the case of plurality, nor are they guaranteed without a matching upper bound. A matching upper bound, or a stronger lower bound-for instance, perhaps our proof could be strengthened to give a lower bound of Ω(m)-is an important result needed to complete the picture regarding Borda under impartial culture. Despite this, we will see below that top-k voting can, in fact, help substantially in Borda voting under other, more realistic preference distributions.

5 Zero-elicitation Protocols

It is widely recognized that the impartial culture assumption does not provide a realistic model of real-world preferences or voting situations [Regenwetter et al., 2006]. For this reason, exploring the ability to limit elicitation under other, more realistic probabilistic models of voter preference is of great import. We consider one such model in this work, namely the Mallows model, since it allows us to generalize the impartial culture model (which is a special case) by simply varying the dispersion or degree of concentration of voter preferences in a natural way. While we do not claim that the Mallows model is an ideal model for all social choice situations (though it serves as an important backbone for mixture models of preferences [Murphy and Martin, 2003; Busse et al., 2007; Lu and Boutilier, 2011a]), it represents an important starting point for the broader investigation of top-k voting.

In this section, we theoretically analyze the special case of zero elicitation protocols-that is, top-k voting when we set k = 0-under Mallows model distributions. Specifically, we ask how concentrated voter preferences need to be-what dispersion values ϕ suffice-to ensure that correct plurality and Borda winners can be selected w.h.p. without eliciting any information from voters. For ease of presentation, we assume p = 1 (i.e., all candidates are available); however, our proofs can be modified to accommodate p < 1, using simple applications of Chernoff and union bounds to account for missing candidates. In the next section, we empirically analyze top-k voting for both zero elicitation and more general values of k under Mallows models.

It is important to recognize that voting is often used for two distinct purposes, aggregation of preferences as discussed above, and aggregation of information [Condorcet, 1785; Young, 1995]. In the latter case, it is often assumed that some true (objective) latent ranking of alternatives gives rise to the reported rankings of voters, with the aim of recovering this latent ranking from the votes (e.g., using some form of maximum likelihood estimation). In such a case, having the mean ranking ˆπ given a priori via a Mallows model leaves no reason to actually elicit votes (since the ranking to be estimated is given as input). However, voting does offer value when aggregating preferences: The ranking ˆπ may represent, for example, an ordering of candidates based on some observable characteristic that correlates voter preferences, but does not actually determine them. If our aim is to maximize societal satisfaction using a specific voting rule (as opposed to estimating the objective ranking itself), then preference elicitation is generally needed. Our aim in this section is analyze how concentrated preferences need to be to support preference aggregation with no elicitation.

Assume a Mallows model (ˆπ, ϕ) over m candidates C. With no elicitation, the candidate with the expected highest (plurality or Borda) score is obviously the highest ranked candidate ˆπ(1), and it has the highest probability of winning if ϕ < 1 (if ϕ = 1, all candidates are equally likely to be winners). Under plurality voting, we can show that with a sufficiently large voter population, this approach performs well.

Thm. 13 can be proven using the Bernstein inequality and union bound to bound the probability that the highest-ranked candidate in ˆπ is dominated by another.

We can derive a similar bound for Borda voting.

Theorem 14. If n ≥ Γ(ϕ) lnm, where Γ(ϕ) = (8(1 + ϕ)2 (1 - ϕ)3 + (1 + ϕ))/(1 - ϕ)7 , then the highest-ranked candidate ˆπ(1) is the Borda winner w.h.p.

Sketch of Proof As before, assume without loss of generality that the candidates are numbered according to their rank in ˆπ. We make use of the following straightforward lemma:

The lemma follows from a simple coupling argument and the definition of the Mallows distribution. As before, we let Di = scB (c1) - scB (ci). Lemma 15 implies that the expected Borda score E[ci] are a non-increasing with i:

We proceed as before by bounding the probability that the score of c1 is lower than the Borda score of some other candidate; i.e., that Di < 0 for some i > 2.

We can now bound E[D2] and the k'th moment of D2.

Lemma 17. The following bounds hold for the expectation E[D2], the second, and the k'th moments of D2:

Proof. Using the definition of the Mallows distribution and Lemma 15 we obtain E[D2] = n ϕ-m·ϕm+m·ϕm+2-ϕ2m+1 (1+ϕ)(1-ϕm)(ϕ-ϕm) . By observing that the above expectation is nondecreasing in m, setting m = 2 and taking the limit m → ∞, we obtain the first part of the lemma. Also, using the definition of the Mallows distribution, we have:

Applying similar methods to Eq.6 gives parts (2) and (3).

In order to use Bernstein's inequality, we need to find a constant c such that E[|D2|k ] ≤ 0.5 · k!E[D2 2 ] · ck-2 . It can be verified that c = 2/(1-ϕ)5 satisfies this inequality. Now, applying Bernstein's inequality we get:

Applying Corollary 16 and taking the union bound over the m candidates gives the bound on n.

Notice that our proof implies an even stronger result, that for a sufficiently large population of voters, the entire ranking induced by the Borda scores of the candidates corresponds to the reference ranking.

6 Empirical Results

The bounds above provide some theoretical justification for the use of top-k voting; however, they do not prescribe precise values for the choice of k with respect to specific priors and election sizes (m, n). In this section we present simulation results for small elections with m = 10 candidates and n = 100 to 5000 voters to illustrate the probability of correct winner selection in both plurality and Borda elections using top-k voting for several values of k (including zero elicitation), under Mallows models with a range of dispersion value ϕ. In our experiments, we generate 10,000 random preference profiles for each parameter setting by drawing voter rankings i.i.d. from the appropriate Mallows model, and measure the fraction of such profiles in which top-k delivers the true winning candidate. We assume a candidate availability probability of p = 0.5 throughout, except for results concerning zero-elicitation (in which all candidates are available).

k

k

n

n

Figure 2: Correctness of zero-elicitation: m = 10, varying n, ϕ.

In all tests of top-k voting with dispersion ϕ < 0.7, winner prediction was essentially perfect, even with k = 1, regardless of the other parameters. As a consequence, we focus our discussion on values of ϕ ≥ 0.7. Fig. 1 shows the success rate (i.e., rate of correct winner selection) of top-k voting for both plurality and Borda voting, with ϕ = 0.7 and m = 10, as we vary k and the number of voters. In all cases top-k converges to the correct prediction, and is near-perfect when k = 3. With a greater number of voters, performance is better, but the dependence is slight and almost negligible for k = 3.

To analyze zero-elicitation, we measured how often the first-ranked candidate in the mallows reference ranking (i.e., the winner under zero-elicitation) is the true election winner under both plurality and Borda voting. We set m = 10, and assume p = 1 for simplicity. We vary ϕ and n, and show results averaged over 10,000 elections for each setting in Fig. 2. For ϕ ≤ 0.8, predictions are near-perfect for n ≥ 700; and with ϕ ≤ 0.7, n ≥ 400 suffices for near 100% accuracy. We note that results are better for Borda than for plurality. For populations with an extremely high degree of dispersion (ϕ = 0.9), the success rate for plurality is only 0.8 at n = 1000, and the Borda success rate is only 0.92. This is consistent with the trends suggested by our theoretical bounds in the sense that the success probability depends exponentially on ϕ, which means that it decreases dramatically for larger values of ϕ.

We also measured how frequently the entire societal ranking induced by plurality or Borda voting corresponds to the Mallows reference ranking ˆπ. This measures the extent to which ˆπ, hence zero-elicitation, accurately reflects the entire societal preference ranking (not just the winner at the top of the ranking). Results are depicted in Fig. 3. Unsurprisingly, the probability of complete ranking accuracy is significantly lower than the probability with which zero-elicitation correctly forecasts just the winner. However, with n = 1000, almost perfect reconstruction is achieved for Borda scoring

n

n

Figure 3: Reconstruction rates of zero-elicitation: m = 10, varying n, ϕ.

when ϕ ≤ 0.8. Notice that the difference between plurality and Borda is even more pronounced than in winner prediction. Under Borda, n = 5000 suffices for accurate assessment of the entire ranking with zero-elicitation, even for ϕ = 0.9, while for plurality, results for ϕ = 0.9 are much worse (about 0.6), and even for ϕ = 0.7 do not reach 100%.

7 Conclusions

We have provided a detailed analysis of top-k voting, allowing for the possibility of unavailable candidates, for both plurality and Borda voting. Our theoretical results place bounds (in some cases tight) on the required values of k needed to determine the correct winner w.h.p., in both a worst-case sense and an average-case sense under impartial culture. We also derived conditions under which zero-elicitation admits correct winner prediction using Mallows models. Our empirical results further demonstrate that relatively small values of k work very well in practice. Even zero-elicitation shows strong promise when preferences exhibit only mild degrees of correlation in elections with a sufficient number of voters.

There are a number of interesting directions for future research. Extending our analysis to other voting rules is of great interest. For example, preliminary results suggest that Copeland exhibits behavior similar to Borda, requiring large k for impartial culture; do certain voting rules exhibit behavior that is intermediate between plurality and Borda? Extending our analysis to a richer class of realistic preference distributions, such as the Plackett-Luce model, or Mallows mixtures, is an important next step, as is testing our approach on real data sets.

A third direction is the investigation of multi-round elicitation protocols [Lu and Boutilier, 2011c], where voting data is elicited in stages, and the protocol terminates when the winner can be determined with high probability. Such protocols are adaptive and dynamic, eliciting information in a given stage conditioned on information gleaned in earlier stages. An important question is whether it is possible to elicit less information on average with such a protocol.

Acknowledgements

Thanks to Neal Young and the anonymous reviewers for helpful suggestions. Boutilier acknowledges the support of NSERC.