Multi-Winner Social Choice with Incomplete Preferences

1 Introduction

Social choice deals with the aggregation of individual preferences over a set of alternatives in order to select a suitable consensus option. While considerable research in computational social choice has focused on single-winner choice problems, only recently has much attention been paid to the algorithmic aspects of multi-winner choice [Potthoff and Brams, 1998; Procaccia et al., 2008; Meir et al., 2008; Lu and Boutilier, 2011a; Skowron et al., 2013; Betzler et al., 2011; Lucier and Oren, 2012]. Multi-winner problems are of critical importance in many settings, the classic being election of legislatures and committees using proportional representation [Chamberlin and Courant, 1983; Monroe, 1995]. However, they are also appropriate for resource allocation, product recommendation, and consumer segmentation problems where: a limited number of options can be offered; budget constraints preclude personalized recommendations; or budget can be traded off against group satisfaction [Kleinberg et al., 2004; Lu and Boutilier, 2011a].

As with any social choice problem, practical deployment of multi-winner choice faces the challenge of preference elicitation: requiring individuals to specify a full preference ranking over the option space poses high, and often unnecessary, costs with respect to cognitive burden, communication and privacy. Furthermore, in settings such as consumer choice, preference information is often limited to revealed choice data (e.g., which products have been purchased) or surveys, in which

Craig Boutilier

University of Toronto Department of Computer Science cebly@cs.toronto.edu

case complete preference information may simply be unavailable. Recent work in vote elicitation has begun to address this problem [Kalech et al., 2011; Lu and Boutilier, 2011b; 2011c; Oren et al., 2013] by designing schemes that effectively elicit only relevant preference information; and constructing methods for winner selection with only partial preferences. In this work, we address the same problem in the context of multiwinner choice, addressing two problems: (a) how to select a bounded slate of (at most) K options given partial preference information; and (b) how to elicit additional preference information incrementally to improve the quality of the slate.

Specifically, we consider the problem of proportional representation using positional scoring functions [Chamberlin and Courant, 1983] under partial preferences. We adapt the minimax regret-based approach of Lu and Boutilier [2011b] for single-winner problems to the problem of choosing a slate of K options, we show that robust optimization is NP-hard, but that robust greedy optimization (i.e., selecting the next best option for the partial slate) can be computed effectively-indeed, the model generalizes regret-based optimization for single-winner voting. We then address the problem of elicitation, adapting the current solution heuristic [Lu and Boutilier, 2011b] to multi-winner choice. Empirical results show that very good slates of options can be found with relatively little preference information.

2 Background

We begin with a brief review of relevant concepts from social choice, outline the Chamberlin-Courant proportional representation scheme, and briefly describe our model of partial preference information.

Preference Profiles. We assume a set of agents (or voters) N = {1, . . . , n} and a set of alternatives (or options) A = {a1, . . . , am}. Let Γ be the set of rankings (or votes) over A (i.e., permutations over A). Alternatives represent any outcome space over which the voters have preferences (e.g., products, elected officials, public projects). Agent i's preferences are represented by a ranking vi ∈ Γ, where i prefers a to a′ , denoted a ≻i a′ , if vi(a) < vi(a′ ). The collection of votes v = (v1, . . . , vn) ∈ Γn is a preference profile.

A positional scoring function (PSF) α : {1, . . . ,m} ↦→ R≥0 maps ranks onto scores such that α(1) ≥ · · · ≥ α(m) ≥ 0. We write αi(a) = α(vi(a)), which can be interpreted as a measure of i's satisfaction with option a. In what follows, we focus on the Borda score, where α(i) = m- i, but most of our results generalize to arbitrary scoring rules.

Proportional Representation. In single-winner social choice, the goal is to select a single option a that reflects some notion of consensus. For example, the Borda winner is the option a with the greatest total Borda score ∑i αi(a) in profile v. Our focus here is on the selection of a set of options a ⊆ A where |a| ≤ K, allowing voters to derive satisfaction from their most preferred candidate. Specifically, given a preference profile v, we define the score of a K-set and the optimal K-set as follows:

(We suppress dependence of S on α since the PSF will be fixed.) When α is the Borda PSF, this corresponds to the proportional representation scheme of Chamberlin and Courant [1983]. It can be viewed as a segmentation problem [Kleinberg et al., 2004]; and it is also a special case of budgeted social choice, specifically, the limited choice form of the problem [Lu and Boutilier, 2011a]. More general forms of proportional representation [Monroe, 1995] and budgeted social choice [Lu and Boutilier, 2011a] allow for assignment functions that map voters to specific options (e.g., to ensure balanced representation, or budget feasibility); but here we assume that the only constraint is on the number of options selected. Sets of size less than K offer no advantage over those of size K in this case.

Partial Preferences. To represent partial information about the preferences of voters, we let a partial ranking for a voter i be a partially ordered set over A, or equivalently (the transitive closure of) a collection of consistent pairwise comparisons of the form a ≻i a′ . Most natural constraints on preferences, including the responses to natural queries (e.g., pairwise comparison, top-t preferences) can be represented this way. Let pi be i's partial ranking. We will simply write a ≻i a′ to indicate that this preference can be inferred from pi when the partial ranking is clear from context. A completion of pi is any vote vi that extends pi. Let C(pi) denote the set of completions of pi. When preferences are uncertain, we write αi(a, vi) to emphasize the dependence of voter i's score on her vote. A partial profile is a collection of partial votes p = 〈p1, . . . , pn〉. Let C(p) = C(p1) × . . . × C(pn) be the set of completions of p.

Related Work. Multi-winner problems of the form Eq. 2 were proposed by Chamberlin and Courant [1983] as a form of proportional representation (PR). Monroe [1995] considered a variant of this model in which representatives on the winning slate must have roughly balanced numbers of voters, requiring the use of assignment functions (so certain voters may not be "represented" by their most preferred option). Lu and Boutilier [2011a] generalize the model further by considering both fixed and unit costs. Computing optimal slates, even in the simple PR/limited choice model given by Eq. 2, is NP-hard [Lu and Boutilier, 2011a; Meir et al., 2008] (also see parameterized complexity results [Betzler et al., 2011]). But optimal slates in the PR model (and also in Monroe's scheme) can be computed greedily with a 1 - 1e approximation ratio [Lu and Boutilier, 2011a; Skowron et al., 2013]; see [Potthoff and Brams, 1998; Procaccia et al., 2008; Lucier and Oren, 2012] for additional computational results on the problem (including online variants). Segmentation [Kleinberg et al., 2004], facility location [Hajiaghayi et al., 2003] and maximum coverage problems [Cohen and Katzir, 2008] all bear close connection to the general budgeted problem (see [Lu and Boutilier, 2011a]).

While multi-winner problems with partial preferences have not been addressed in the literature to the best of our knowledge, winner determination in standard single-winner elections with partial preferences has received attention, both in the form of possible and necessary winners [Konczak and Lang, 2005; Xia and Conitzer, 2008], and using minimax regret [Lu and Boutilier, 2011b] to provide quality guarantees. We define the latter notion below and draw heavily on this approach in our work. Recent work on incremental vote elicitation has shown strong promise for reducing the informational requirements of various voting schemes in single-winner problems (including Borda and other PSFbased methods), despite seemingly discouraging worst-case communication complexity results [Conitzer and Sandholm, 2005]. Kalech et al. [2011] develop schemes based on the notion of possible and necessary winners. Lu and Boutilier [2011b; 2011c] use minimax regret to determine appropriate queries, an approach we generalize below.

3 Robust Multi-winner Optimization

We first consider the problem of selecting an optimal K-set of options when we have only a partial preference profile p rather than a complete profile v. Partial preferences may be common in applications involving limited surveying, partial customer purchase or rating data, or situations in which voters can complete partial ballots. Just as importantly, reasoning with partial profiles is vital for incremental vote elicitation.

Following Lu and Boutilier [2011b], we adopt minimax regret as a robustness criterion for making decisions with incomplete information. We first present definitions (for sets of fixed size K) then explain the intuitions:

Given a vote profile v, Regret(a, v) describes the loss in satisfaction associated with offering set a rather than the optimal K-set. Give a partial profile p, the pairwise max regret PMR(a,w, p) is the worst-case loss that could be incurred, under all possible realizations of voter preferences, by offering a rather than w. Note that our definition of PMR does not impose constraints on set sizes, a fact we exploit below. The max regret MR(a, p) of set a is the worst-case loss relative to the optimal K-set under all preference realizations: this bounds the loss associated with a given our preference uncertainty. Finally, a minimax optimal set a∗p is one with minimal max regret or minimax regret MMR(p).

Observation 1. If MMR(p) = 0, then a∗p is an optimal slate of alternatives for any v ∈ C(p).

3.1 ComputingMinimax Optimal Sets

Before discussing computation of minimax regret, we begin with the simpler problem of computing pairwise max regret. From Eqs. 4-6, we see that the regret-optimal slate a∗p can be determined by first computing PMR(a, w, p) for all pairs of K-sets a, w, maximizing over w to determine MR(a, p), then minimizing over these terms to compute MMR(p). If K is small, then robust optimization is efficient if PMR can be computed effectively, a problem to which we now turn. (We discuss an approach for large K in the next subsection.)

One can show PMR is additively decomposable:

Thus we can compute the contributions of each voter i to PMR individually. When i is presented with slate a, she will choose her most preferred element form a and similarly for slate w. Define the undominated elements in any set a to be:

Only undominated elements in a set can be chosen in any completion of i's preferences. In the ranking vi ∈ C(pi) that maximizes pairwise regret, only one element in w will be chosen by i (the most preferred), which defines PMR:

Given this, there are two cases to consider in determining the adversarial completion vi ∈ C(pi) that maximizes PMR(ui(a), {w}, pi).

Case 1. Suppose there is an a ∈ a such that a ≻i w. This means in there is no completion in which i would choose w, so PMR is negative. Maximizing pairwise regret requires reducing the "gap" between the most preferred a∗ ∈ a and w. The only options that must lie between the most preferred a and w are undominated elements ui(a) of a that dominate w, or those b known to lie between such an a and w. Define

Bi(a,w) includes all options that must lie between the best a ∈ a and w (the specific choice or placement of the elements in these two sets has no impact on PMR). Every other option can consistently be ordered above the best a or below w depending on constraints in pi. 1 Thus we have:

PMR(ui(a), {w}, pi) = -|ui(a)+w | - |Bi(a, w)|. See Fig. 1(case 1) for an illustration.

Case 2. Now suppose that for voter i, no element in a ∈ a is known to be preferred to w. If w ∈ ui(a) then PMR(ui(a), {w}, pi) = 0, since any adversarial completion can place w above all items in ui(a) \ {w} (otherwise regret would be negative). Otherwise the desired completion must maximize the gap between w and any item in ui(a). The following options can be placed between w and a:

The relative ordering of these items does not impact regret. With B′i (a, w) placed below w, some item from ui(a) must lie immediately below the last element of this set (becoming the most preferred a ∈ a). Thus, we have:

See Fig. 1(case 2) for an illustration (where w ̸∈ ui(a)).

In both cases, the undominated sets ui(a) and ui(w) can be computed in O(K2 ) time. In case 1, ui(a)+w can be computed in O(K) time once ui(a) is known, and Bi(a,w) can be computed in O(mK) time by checking if each b ∈ A satisfies the constraints w.r.t. ui(a)+w and w. For case 2, B′i (a, w) can be found in time O(mK) by checking each b ∈ A with w and the options in ui(a). Using Eqs. 9 and 8, PMR(a, w, p) can be computed in O(n(K2 +K(K+mK))) = O(nmK2 ) time. Note that for K = 1, the approach is identical to PMR computation proposed by Lu and Boutilier [2011b]. Putting this together we have:

Theorem 2. PMR(a,w, p) is given by:

and is computable in O(nmK2 ) time.

1 For "nonlinear" scoring rules, where the score difference for two options depends not just on relative, but also absolute rank position, placement of options above or below a and w requires more care, but is straightforward in most cases.

The minimax optimal slate a∗p can be computed by computing max regret MR(a, p) for each size K slate a (and selecting the slate a∗p that minimizes regret); and in turn MR(a, p) can be computed by determining its pairwise max regret for each size K witness set w. Hence:

Proposition 3. The minimax regret optimal slate a∗p can be found in time O(nm2K+1K2 ).

The additive decomposability of PMR has the nice computational consequence that, during the course of incremental elicitation (see Sec. 4), one need only update the contributions to PMR of those agents who have their partial preferences updated by responding to a query.

For slates of small bounded size K, enumeration of option sets may be practical-with bounded K, slates can be computed in polynomial time (in n,m). However, since this form of proportional representation and budgeted social choice is an NP-hard optimization problem [Lu and Boutilier, 2011b] (as are related forms [Procaccia et al., 2008]), finding the minimax optimal slate is also NP-hard (simply let p be a full preference profile). Indeed, even simply computing MR(a, p) is NP-hard:

Theorem 4. Given threshold r ≥ 0, partial profile p, set size K, and set a of size at most K, deciding if MR(a, p) ≥ r (i.e., does some set w of size at most K satisfy PMR(a, w, p) ≥ r) is NP-hard.

Proof. This is easy to see using a simple reduction from from the limited choice (LC) problem (with Borda scoring), which is NP-hard [Lu and Boutilier, 2011a]. Given any LC instance with budget K and complete profile v over m items, we transform it into a partial profile p with m+K items (the m original items plus K "dummy" items). Set a to be the dummy items. Define each partial pi to be identical to vi on the top-m ranked items, while the rest of the ranking is unspecified. Computing whether some slate w of size at most K has PMR(a, w, p) ≥ r can then be used to determine if there is a slate w′ with score above a threshold in the LC instance.

3.2 AGreedy Algorithm

Due to the lack of a (general) efficient algorithm to compute a∗p, we develop a heuristic approach that will be practical for large K. It turns out that a relatively simple greedy optimization procedure can be used for this purpose. To this end, define the following problem, which we call the additional option problem: assume a partial profile p and a fixed set a of k - 1 options; if one can add a kth option to the set, which next option minimizes maximum regret under the PR/limited choice model? We define this problem in the obvious way:

(Note that setting k = 1 gives the (single-winner) robust voting problem of [Lu and Boutilier, 2011b].)

The additional option problem can be solved in polynomial time. We can explicitly compute the pairwise max regret PMR(a,w, p|a) of all m2 pairs of alternatives (a,w) (where a is a proposed additional option and w is an adversarial witness), using intuitions very similar to those above (as we discuss below). Note that while we can apply our previous algorithm for finding the pairwise max regret for arbitrary pairs of slates (a,w), the algorithm and analysis for PMR(a,w, p|a) that we provide below provides a factor k speedup. With PMR in hand, we can readily determine minimax regret using Eqs. 12 and 13. We need only show that PMR can be computed in polynomial time. As above, we can compute each voter's i's contribution PMR(a, w, pi|a) independently. We again consider two cases.

Case 1. If a ≻i w, then PMR(a, w, pi|a) ≤ 0 since adding w to a cannot improve i's score any more than adding a. Assuming a ≻i w, if there is some b ∈ a such that a ̸≻i b, then b can be ordered over a and PMR(a,w, pi|a) = 0. However, if a ≻i b for all b ∈ a, regret must be negative. PMR(a, w, pi|a) is then maximized (or negative regret minimized) by placing as few options as possible between a and the best element of a ∪ {w}. For any a ≻i b, define

Then regret is maximized by ordering the options in ui(a ∪ {w}) such that the element with the fewest possible options between it and a is ranked first. This gives:

Case 2. If a ̸≻i w, then PMR(a,w, pi|a) ≥ 0. In this case, if there is some b ∈ a such that b ≻i w, then w can never be selected; but since w can be ordered over a, PMR(a,w, pi|a) = 0. However, if there is no b ∈ a with b ≻i w, then regret is maximized by maximizing the gap between w and the best element of a ∪ {a}. In particular, the options B′i (a ∪ {a}, w), as defined above, can all be ordered between w and the best such option. This gives us:

Taken together, this shows that PMR(a,w, pi|a) for the additional option problem can be computed in polynomial time. This gives rise to a very simple greedy algorithm for approximating a minimax optimal K-set: starting with the empty slate a0 = ∅, at each of iteration k ≤ K we add option a∗k = a∗ak-1,p, i.e., the option with least max regret given the prior items, to slate ak-1. The method is detailed in Algorithm 1. While this algorithm comes with no strong approximation guarantees (but see below), we show in Sec. 5 that it works extremely well in practice.

In terms of run time, Case 1 takes O(mk) time (at the kth iteration) and Case 2, as discussed previously, takes O(k2 + mk) = O(mk) time. Computing pairwise max regret for all pairs (a,w), across all agents, and finding the next best item a∗ak,p for each of the K spots on slate a results in a total running time of O(nm3K2 ).

There are two reasons the greedy algorithm cannot guarantee that we find the minimax optimal slate. The first is

Algorithm 1 Greedy algorithm

1: a ← ∅ 2: for k = 1 to K do 3: MMR←∞ 4: for a ∈ A do 5: MR←-∞ 6: for w ∈ A : w ̸= a do 7: for i ∈ N do 8: if a ≻i w then 9: PMR ← PMR+maxb∈ui(a∪{w}) -|Ti(a, b)| - 1 10: else 11: PMR ← PMR+|B′i(a ∪ {a}, w)| + 1 12: end if 13: end for 14: if PMR > MR then 15: MR ← PMR 16: end if 17: end for 18: if MR < MMR then 19: MMR ← MR 20: a∗ ← a 21: end if 22: end for 23: a ← a ∪ {a∗ }. 24: end for

unrelated to preference uncertainty: even with complete preference information, the greedy algorithm is unable to provide an optimal K-slate. In other words, it can produce a slate that has positive max regret. However, the greedy algorithm does provide a 1 - 1e approximation in the full information setting. It is not hard to see that if we have sufficient information to make the "optimal greedy choice" at each stage, then the regret-based approach will correspond to the exact greedy algorithm described by Lu and Boutilier [2011a]:

Proposition 5. If MR(a∗k , p|ak-1) = 0 for all k ≤ K, then the greedy-MMR set aK is identical to the set produced by the (full-information) greedy algorithm given any v ∈ C(p).

If the last element added has non-zero max-regret, we are assured that true minimax regret is also nonzero:

Observation 6. If MR(a∗K, p|aK-1)>0, then MMR(p)>0.

However, we cannot be sure that if only the last element has zero regret that we have found the greedy-optimal slate. But even if the minimax-optimal option a∗i does not have zero max regret, we can still obtain bounds on the quality of the solution. Based on known results for "approximate" greedy optimization [Goundan and Schulz, 2007], we obtain:

Proposition 7. Let v be an (unknown) complete preference profile. Let mk be any lower bound on the marginal value of the kth item added to the slate by the full information greedy algorithm. That is, mk ≤ S(ak-1 ∪ {a∗k }, v) - S(ak-1, v) where ak-1 consists of the first k - 1 greedily selected items. If MR(a∗k , p|ak-1) ≤ mk/(1 - α) for all k ≤ K, for some α ≥ 1, then the greedy-MMR set aK is within a factor of 1- 1 e1/α of the optimal (full-information) option slate.

4 Preference Elicitation

We now turn our attention to the question of incremental elicitation of voter preferences. With a partial preference profile p, we cannot guarantee that an optimal slate can be obtained (regardless of whether we resort to greedy or exact optimization): specifically, if MMR(p) > 0, no slate can be guaranteed to be optimal. To improve the quality of the slate, further information must be elicited from one or more voters. Our goal is to reduce relevant uncertainty, i.e., find those queries that have the greatest potential to reduce minimax regret. To do this we adopt a general technique known as the current solution strategy (CSS). This has been used effectively in both (single-agent) robust optimization [Boutilier et al., 2006; Braziunas and Boutilier, 2010], voting [Lu and Boutilier, 2011b] and stable matching [Drummond and Boutilier, 2013] settings, and relies on eliciting information that helps assess the relative degree of preference between the minimax optimal solution and the adversarial witness. We focus here on pairwise comparison queries, in which some voter i is asked whether a ≻i a′ ; but the basic principles can be applied to other forms of queries (e.g., top-t queries, where a voter is asked to reveal their tth-most preferred alternative if they have already provided their top t - 1).

In our model, the use of CSS differs depending on whether we are using the greedy heuristic or optimal MMR computation to determine K-sets. We present our approach in the context of greedy MMR computation since it is the more practical method for problems involving slates of reasonable size. The general principles can be readily adapted to optimal MMR computation as well. Our elicitation scheme works by using the greedy algorithm to compute an (approximately) minimax optimal slate a∗p = 〈a∗1 , . . . , a∗K 〉 given the current partial profile p. If MR(a∗K , p|a∗K-1 ) = 0, we treat this as an (approximately) minimax optimal slate and stop. Otherwise, we know that MMR(p) > 0, so we select a voter i and pairwise comparison query a ≻i a′ with the greatest potential to reduce MR(a∗K , p|a∗K-1 ), using CSS. Let a∗K be the last item added to the slate and wK be the witness option (i.e., where MR(a∗K , p|a∗K-1 ) = PMR(a∗K ,wK, p|a∗K-1 ). CSS identifies the appropriate query (and its potential) for a particular voter i based on several specific cases/sub-cases.

Case 1: Suppose a∗K ≻i wK. Then i's contribution PMRi to PMR(a∗K , wK, p|a∗K-1 ) must be PMRi ≤ 0. If PMRi = 0, then either: (i) a∗K is dominated in i's partial order pi by some aj ∈ a∗K-1 , or (ii) a∗K is not dominated by any such aj. In case (i), no query can reduce MR(a∗K , p|a∗K-1 ) since voter i would never select either of a∗K or wK given the rest of the slate a∗K-1 , so no query is asked of i. In case (ii), the adversary can set PMRi = 0 by ordering some option aj ∈ a∗K-1 over a∗K (if no such option were possible, PMRi would have to be negative). In this case, any query that prevents aj from being orderable above ak can reduce PMRi (by making it negative). Specifically, any query of the form b ≻i c for b ∈ a∗K ∪ {a : a∗K ≻i a} and c ∈ aj ∪ {a : a ≻i aj} will suffice. Since the degree of PMRi is determined by the relationship of a∗K to wK and not the gap with aj , we choose query a∗K ≻i aj since it is implied by any other.

If PMRi < 0, then (iii) a∗K dominates each aj ∈ a∗K-1 as well as wK. Queries that can extend the advantage over the best item of w∗ ∈ ui({wK} ∪ a∗K-1 ) (i.e., make PMRi even smaller) take two forms: learning that a∗K ≻i c for some ancestor c of w∗ (since we do not know w∗ , we choose an arbitrary item in ui({wK}∪a∗K-1 )); or learning that d ≻i w∗ for some descendant d of a∗K . The query with the greatest potential is that with the largest number of descendants (resp. ancestors) lying between it and c (resp. d) in pi.

Case 2: Suppose a∗K ̸≻i wK. Then i's contribution PMRi to PMR(a∗K ,wk, p|a∗K-1 ) must be PMRi ≥ 0. (i) If PMRi = 0, then we must have wK dominated by some aj ∈ a∗K-1 . In this case we ask no query. (ii) If PMRi > 0, then wK is not dominated by any aj ∈ a∗K (i.e., by none of the K items). Then regret can be reduced only by asking a query that removes elements from the set B′i (a∗K , wK) by either placing wK (or one of its ancestors) below some aj (it is only necessary to consider those in ui(a∗K )); by placing some aj ∈ ui(a∗K ) (or one of its descendants) above wK; or placing some element that is incomparable to both a∗K and wK either above wK (hence placing its ancestors above as well) or below a∗K (hence placing its descendants below as well). In the case that wK dominates all of a∗K , one can ask queries that either (a) move a descendant d of wK, where d is not an ancestor of some aj ∈ a∗K , below such an aj; or (b) move an ancestor c of some aj, where c is not a descendent of wK, above wK. The potential of a query to reduce PMRi is measured by the number of elements it removes from the set B′i (a∗K , wK).

We note that if PMR(a∗K ,wk, p|a∗K-1 ) > 0, then one of the query-generating cases above must hold for at least one voter. As a consequence, CSS cannot "stall" as long as the last item added to the slate has non-zero max regret.

5 Experimental Evaluation

We present a set of experiments designed to test the ability of greedy slate optimization method described in Sec. 3.2, coupled with the CSS elicitation strategy, to find good (or even optimal) slates of options with few voter queries. We evaluate the approach on two real datasets as well as on more systematically generated random data. The Sushi data set [Kamishima et al., 2005] consists of 5000 complete user preference rankings over 10 varieties of sushi. We consider aggregation problems (or elections) of 100 users, drawing full preference profiles at random from this set. The Irish dataset consists of partial (top-t) preferences of voters from the 2002 Dublin West constituency elections, involving nine candidates and 29,988 voters; we consider elections of 100 voters by drawing random profiles from among the 3800 full rankings in the dataset. In the Sushi experiment we set slate size to be K = 3 and in Irish, K = 4. To test our methods more systematically, we generate random profiles of 100 voter rankings over 10 items, using the Mallows distribution to generate the preferences of each voter [Mallows, 1957; Marden, 1995]. The Mallows model is quite flexible: the dispersion parameter φ ∈ (0, 1] controls how concentrated preferences are: when φ = 1, we obtain uniformly random preferences, or impartial culture, while we approach a distribution where all mass is placed on a single-ranking (i.e., all voters have identical rankings) as φ → 0. In the Mallows experiments, we set K = 3 and analyze elicitation performance as we vary φ.

Experimentally, each instance consists of a full profile. We start with no vote information then, using CSS to generate queries, elicit pairwise comparisons from voters (who respond accurately based on their underlying preference). After each query or round, we use the greedy algorithm to compute an (approximately) optimal K-slate. Elicitation terminates once the conditional max regret (CondMR) of the Kth item added to the slate, MR(a∗K , p|a∗K-1 ), is zero. We also compare this to the use of exact minimax regret computation at each iteration to determine the truly optimal K-slate.

Results in Fig. 2 (a) and (b) show performance for the Sushi and Irish data. The plots show, for the slate produced by Greedy after each query, its conditional max regret (CondMR), its true max regret and two dotted lines of one standard deviation above and below its max regret (results are averaged over 20 randomly drawn profiles). We also show the performance of CSS when exact MMR is computed and the optimal slate is generated at each iteration. We also compare CSS with a baseline random strategy that randomly picks a voter and pairwise query (ensuring this query is not implied by that voter's partial ranking), using Greedy to compute a slate at each round and measuring its max regret. Dotted lines above and below indicate a range of one standard deviation. We see that CSS works very well: it finds a slate with zero max regret "per voter" with only about 20 queries per user in Sushi (resp., 15 in Irish), even with the relatively large ratio of K to m in each setting (30% and 44%, resp.). CSS also reaches near-zero regret in about 10 queries (resp., 8) per user; thus, its anytime profile is very encouraging for settings where approximately optimal solutions that reduce elicitation burden are permissible. Note that the true regret may be zero even if max regret is not. We contrast the number of queries needed by CSS with the demands of complete sorting to provide a full ranking, which requires O(mlog(m)) pairwise comparisons using methods with good average case performance, or equivalently 34 (resp., 29) queries. Random requires 25 (resp., 22) queries per user to reach zero regret, and has a much worse anytime profile.

Notice that the greedy algorithm itself works extremely well: it almost always finds the minimax optimal slate-the MR Greedy and MMR curves coincide almost exactly-and in the rare cases that it does not, Greedy MR is very close to true MMR. MR may not decrease monotonically, as preference updates may "mislead" Greedy into choosing an inferior slate (by contrast, true MMR is non-increasing). CondMR is also a good proxy for true max regret: in Sushi, the per-voter difference is at most 0.41 and in Irish at most 0.24. Thus, CondMR-which can be computed efficiently-is an excellent surrogate for MR-which is NP-hard-as a quality measure and a stopping criterion for elicitation.

Mallows results in Fig. 2 (c) show how the same quantities change as a function of the total number of queries, for different dispersion values φ. The results show that, unsurprisingly, more concentrated preference distributions (smaller φ) require fewer queries to find good slates. This is consistent with observations in single winner voting [Lu and Boutilier, 2011b].

Table 1 shows wall clock runtimes of Greedy for different values of m (candidates) and K (slate size) on a 3.0GHz Intel Xeon processor. Results are averaged over "complete" CSS elicitation runs (i.e., elicitation proceeds until CondMR is zero), on random profiles of n = 40 voters drawn from a Mallows distribution with φ = .7. Average runtime increases significantly with the number of candidates m, but less dramatically with K. This is consistent with the "quadratic in K" and "cubic in m" computational results above. Still, Greedy is very practical, taking only 6.3s. to find optimal slates for m = 50 and K = 8.

6 Conclusion

We have provided a new model for analyzing the quality of slates of options with incomplete preference profiles, and developed algorithms for the exact and greedy optimization of K-slates with minimax regret. The greedy method has been shown to be quite practical. We also adapted the CSS elicitation heuristic to this setting and demonstrated that-when coupled with the greedy method for producing slate, and the efficiently computable conditional max-regret criterion as a proxy for max regret-it finds optimal slates while requiring relatively little preference information from voters. Moreover, it has an excellent anytime profile, finding slates with very low max regret very quickly, and important property in low-stakes domains where decision quality may be sacrificed for increased informational, cognitive, and communication efficiency or privacy.

This work raises a number of interesting questions for future research. Developing regret-based methods for additional scoring/voting rules and other multi-winner criteria would be of significant value. Theoretical analysis of the communication complexity for multi-winner social choice would advance our understanding of elicitation methods. Finally, developing elicitation and optimization methods that exploit preference distributions could further reduce information requirements.

Acknowledgements: Lu was supported by a Google Ph.D. Fellowship. Lu and Boutilier acknowledge the support of the the Natural Sciences and Engineering Research Council (NSERC).