What Do We Elect Committees For? A Voting Committee Model for Multi-Winner Rules

1 Introduction

There are many real-life situations in which we want to select a subset of a given set of candidates. Examples of such situations include selecting a set of movies for an airplane [Skowron et al., 2015], choosing locations for common facilities [Shmoys et al., 1997], short-listing candidates for hiring in a new team, or electing a parliament. These examples differ in their nature and in each of them we might desire the selected group of candidates to exhibit different properties. In this paper we consider the case of selecting a committee, also referred to as a group of representatives, for the agents. However, even if we restrict our analysis to the concrete case of choosing a committee, we might require different representatives to be elected, depending on their rights and responsibilities in the elected body.

Indeed, different views on what the desired properties of committees are have led to inventing a number of multiwinner election rules [Chamberlin and Courant, 1983; Monroe, 1995; Fishburn, 1981; Gehrlein, 1985; Brams et al., 2007; Kilgour, 2010; Debord, 1992]. In this paper we argue that the desired properties of multi-winner rules strongly depend on what we elect the committee for. One of our main conclusions says that for different single-winner rules used by the committee to make final decisions, different multi-winner rules should be used to elect the decision-making committee.

Specifically, we obtain theoretical justification for the following claims. We argue that multi-winner rules that achieve fully proportional representation, such as ChamberlinCourant rule [1983] and Monroe rule [1995] are particularly well-suited for electing committees that need to make unanimous decisions. Unanimity is often required in situations where making a wrong decision implies severe consequences, e.g., in case of juries voting on convictions. Indeed, in such cases we are particularly willing to ensure that minorities are represented in the committees to avoid biased decisions.

Further, our analysis suggests that K-top rules, i.e., scoring rules [Young, 1975] that select K candidates with the highest total utilities, are suitable for electing committees that use the random dictatorship rule to make decisions. It might seem that the significance of this observation is compromised by the low applicability of randomized election rules. Such randomized decision-making processes, however, model situations where decisions are made by individual members of the committee but we are uncertain which issues will be considered by which individuals. As an example of such a group of representatives consider a senior program committee for a conference, where individual experts makes final decisions regarding submitted papers.

We observe that the median OWA rule [Skowron et al., 2015] is suitable for electing committees that make final decisions by majority voting. Informally speaking, in the median OWA rule a voter is satisfied with a committee C if she is satisfied with at least half of the members of C. We recall the formal definition of the class of the OWA rules in Section 2.

We derive the above results by introducing and studying a new formal model that allows us to validate the applicability of multi-winner election rules. In our model, hereinafter referred to as the voting committee model, we assume that an elected committee runs a number of ballots, in which it makes collective decisions regarding various issues. This setting corresponds to, e.g., a parliament voting on law acts, a jury voting on convictions, a supervisory board voting on strategic business decisions, etc. We assume that the ultimate satisfaction of the voters depends solely on the final decisions made by the committee. Consequently, each voter ranks candidates for the committee according to how likely it is that they vote according to her preferences. This new model allows to numerically assess qualities of committees, depending on what election rule these committees use to make the final decisions. Intuitively, the numerical quality of a committee C estimates how likely it is that C makes decisions consistent with voters' preferences.

Our work extends the literature on properties of multiwinner election rules [Simeone and Pukelsheim, 2006; Barber´a and Coelho, 2008; Elkind et al., 2014; Aziz et al., 2015; Gehrlein, 1985; Debord, 1992]. This literature includes, e.g., the works of Barber´a and Coelho [2008] and of Aziz et al. [2015], where the authors define properties that "good" multi-winner rules should satisfy. Elkind et al. [2014] argue that the desirability of many natural properties of multiwinner rules must be evaluated in the context of their specific applications. Our paper extends this discussion by showing an intuitive model and concrete examples concerning this model, for which different multi-winner rules are particularly well applicable.

Many multi-winner election systems are defined as functions selecting such committees that optimize certain metrics, usually related to voters satisfaction [Bock et al., 1998; Chamberlin and Courant, 1983; Monroe, 1995; Brams et al., 2007; Kilgour, 2010; Debord, 1992]. These different optimization metrics capture certain desired properties of election systems. Our paper complements these works by presenting a specific metric that is motivated by the analysis of decisionmaking processes of committees.

Similarly to Fishburn [1981], we explore the idea of comparing multi-winner election systems. Further, our perspective is conceptually close to the ones given by Christian et al. [2007], who study computational problems related to lobbying in direct democracy, where the decisions are made directly by the voters who express their preferences in open referenda (there are no representatives). Our model is also close to the one of Koriyama et al. [2013], who alike assume that the elected committee makes a number of decisions in a sequence of ballots. In such model, they compute the frequency, with which the will of each individual is implemented. They further make some assumptions on how the society evaluates the frequency values, to justify degressive proportionality, the principle of proportional apportionment.

Our methodology is also close in spirit to the one given by Young [1995], who introduced probabilistic models to validate optimality of election rules. In our of such models the decisions are taken by a group of experts-these decisions might be factually either correct or wrong. Young shows the rule that is most adequate in such a setting.

Finally, we note that there exists a broad literature on voting on multi-attribute domains, where agents need to make collective decisions regarding a number of issues [Brams et al., 1998; Lacy and Niou, 2000; Xia et al., 2008; 2010]. We differ from these works by considering an indirect process of decision-making, through an elected committee.

Our contribution is the following: (i) We introduce a new formal model that relates voter satisfaction from a committee to their satisfaction from the committee's decisions. In our model we define the notion of optimality of a multi-winner election rule, given that a certain single-winner rule is used by the elected committee to make the final decisions. (ii) By studying the deterministic variant of our model, we find optimal multi-winner rules for three natural single-winner rules:

majority, unanimity, and random dictatorship. (iii) After relaxing the assumptions regarding the determinism of the model, we show that the class of OWA rules contains all optimal rules for most natural single-winner election systems. (iv) We introduce a definition of the indirect election rule that allows voters to elect not only committees, but also the singlewinner rules used by these committees to make decisions. We discuss the existence of optimal indirect rules.

2 Preliminaries

In this section we first define the notation and basic notions used in the paper. Next, we recall definitions of several known single-winner and multi-winner election rules that we use in our analysis.

2.1 Notation and Basic Definitions

For each set X, by 1X we denote the indicator function of X, defined as: 1X(x) = 1 ⇐⇒ x ∈ X, and 1X(x) = 0 ⇐⇒ x /∈ X. For simplicity, we write 1X instead of 1X(x) if x is clear from the context.

For each finite set X and for each voter i, a utility function of i over X, is a function uti : X → R that quantifies the level of satisfaction of the voter i from the elements of X. We denote the utility that an agent i assigns to a candidate a as ui,a = uti(a). We are specifically interested in the approval model, where utilities come from the binary set {0, 1}. In the approval model, we say that a voter i approves of a candidate a if ui,a = 1. Otherwise we say that i disapproves of a. We do not make any assumptions on where the utility functions come from. For instance, the utilities can be provided directly by the voters, can be extracted from rankings provided by the voters (cf. the work of Young [1975]), etc. For each two finite sets X and Y , with |Y | = y, a utility profile of Y over X is a vector of y utility functions. We denote the set of all possible utility profiles of Y over X as Πy (X).

For each set X and each K ∈ N, by P(X) we denote the set of all subsets of X and by PK(X) the set of all subsets of X of size K. We refer to the elements of PK(X) as to committees of size K, elected from X. A K-multi-winner election rule for a set of voters Y , |Y | = y, and a set of candidates X is a function R1 : Πy (X) → PK(X) that for a given utility profile of Y over X returns a committee of size K. We denote the set of all K-multi-winner election rules for sets Y and X asMW(Y,X,K).

In general, a single-winner election rule for a set of voters Y , |Y | = y, and a set of candidates X is a function R2 : Πy (X) → X that for a given utility profile returns exactly one candidate fromX. Thus, single-winner rules can be seen as 1-multi-winner rules.

In our further analysis we consider single-winner election rules for binary sets of candidates only. We also study randomized single-winner rules that for each utility profile, instead of a single candidate from X, return a lottery over X. Thus, hereinafter we use the following definition. For a set of voters Y , |Y | = y, and a binary set of candidates X = {d0, d1}, a (randomized) single-winner election rule R2 is a function R2 : {d0, d1}y →R, that for each vector of y binary values, returns the probability that the value d0 will be selected. We denote a set of all randomized single-winner election rules for sets Y and X as RSW(Y,X).

2.2 Overview of Single-Winner Rules

A uniformly random dictatorship rule selects a candidate d with probability proportional to the number of voters who prefer d over the other candidate. A majority rule deterministically selects d0 if at least half of the voters prefer d0 over d1 (this assumes that ties are resolved in favor of d0). A unanimity rule returns deterministically d0 if and only if all voters prefer d0 over d1 (in case of the unanimity rule it is convenient to think of voting for d0 as of voting for pass and of voting for d1 as of voting for veto).

2.3 Overview of Multi-Winner Rules

A significant part of results that we provide in the paper concerns OWA rules, the broad class of multi-winner election systems defined by Skowron et al. [2015]. Below, we recall the definition this class of rules and describe several of them.

For each voter i, each committee C, and each number j, 1 ≤ j ≤ K, let ui,C(j) denote the utility of the j-th most preferred candidate from C, according to i. In other words: {ui,C(1), . . . , ui,C(K)} = {ui,a : a ∈ C}, and ui,C(1) ≥ · · · ≥ ui,C(K). For each voter i, each committee C, and each K-element vector α, let α(i, C) denote the α-satisfaction of i from C: α(i, C) = ∑Kj=1 αjui,C(j). The α-rule is a rule that selects a committee C that maximizes total α-satisfaction of the voters ∑i α(i, C).

For a given set of candidates X, a set of voters Y , and a size of the committee we want to elect, K, let OWA(X, Y,K) denote the set of all OWA rules that given votes of Y over X return committees of size K:

There are several specifically interesting OWA rules. For instance, if α = 〈1, 0, . . . , 0〉 we get Chamberlin-Courant rule [1983], where each voter "receives satisfaction scores" from her most preferred member of the committee only. If α = 〈1, 1, . . . , 1〉 we get a K-top rule that selects K candidates with the highest total utility. If α has 1 on the k-th positions and 0 on the others, then we get a k-median rule, in which the satisfaction of a voter from a committee C is her satisfaction from the k-th most preferred member of C.

3 The Voting Committee Model

In this section we describe a voting committee model that allows one to assess the qualities of various multi-winner election rules. Let N = {1, 2, . . . , n} be a set of voters, and let A = {a1, a2, . . . , am} be a set of candidates. We assume there is a set D = {D1,D2, . . . ,Dr} of r issues; each issue Dj is a binary set consisting of two alternatives Dj = {d0, d1}. Voters have strict preferences over the alternatives within each issue; by dji we denote the preferred alternative from Dj from the perspective of the voter i. The issues might differ in their importance to different voters. We consider two types of attitudes: a voter i can consider an issue Dj either as important or as insignificant. We denote the set of all the issues important for voter i as Dim(i) ⊆ D.

In the first stage in our model, a committee C of size K is selected through a multi-winner election rule R1; the selected committee consists of K members. In the second stage, the committee C runs r independent ballots, for each ballot using the same single-winner election rule R2. In the i-th ballot, 1 ≤ i ≤ r, the committee makes a collective decision regarding issue Di-for Di the committee can make either decision d0 or decision d1. The final outcome of this two-stage process is described by a vector of r decisions.

Intuitively, the first stage of elections might correspond to e.g., parliamentary elections, elections for supervisory or faculty board, etc. The second stage might be viewed as e.g., a sequence of parliamentary ballots regarding various matters, such as financial and monetary economics, education politics, changes in national health-care system, etc.

The ultimate satisfaction of voter i depends solely on the final outcome of the r ballots. Nevertheless, the voters need to select the committee members first and, thus, they need a way of judging the qualities of the committees. Intuitively, voter i considers committee C as good, if for i's important issues, i.e., issues fromDim(i), C is likely to make decisions consistent with i's preferences. More formally, we introduce the following probabilistic model.

For each voter i ∈ N and each candidate a ∈ A we set pi,a, the probability of representation of i by a, to be the probability that a for each i's important issue Dj ∈ Dim(i) will vote for dji , i.e., according to i's preferences. For the sake of simplicity of notation, we also use qi,a = 1 - pi,a. We assume that the voters know these probabilities, and that in the considered utility functions the values that voters assign to the candidates are function of the probabilities of representation only. More formally, we assume there exists an injective function P : R → R, such that a voter i assigns utility u to the candidate a, if and only if u = P(pi,a).

We are specifically interested in the approval model, where there are only two "allowed" values of utilities, and thus two values of probabilities of representation: p = P -1 (1) and q = P -1 (0). As a distinguished special case of the approval model, we consider a variant in which the values of probabilities of representation come from the binary set {0, 1} (p = 1 and q = 0). In such case, hereinafter referred to as the deterministic model, for each voter i there are two types of candidates: the candidates that perfectly represent i, i.e., deterministically vote according to i's preferences in all issues important for i (and these candidates are approved of by i) and the others that perfectly misrepresent i, i.e., deterministically vote contrarily to i's preferences (and so, are disapproved of).

For each voter i, each important issue Dj ∈ Dim(i) for i, each committee C, and each committee vote v ∈ DK j , let PC(v) denote the probability that members of C cast vote v:

Let R2 : {d0, d1}K → R be a randomized single-winner election rule used by the committee to make decisions over issues. By PR2 (i|v) we denote the probability that the rule R2, given vote v, makes decision dij :

For each committee C, each voter i, and each important issue Dj ∈ Dim(i), by PC,R2 (i) we denote the probability that C makes decision consistent with i's preferences:

Now, we can define the expected ultimate satisfaction of a voter i from the committee C, as PC,R2 (i)-this is the expected fraction of issues important for i, for which the committee C would make decisions consistent with i's preferences.

Finally, we can define the central notion of this paper.

Definition 1. Let R2 be a single-winner election rule used by the committee to make final decisions, and let K denote the size of the committee to be elected. A committee C is optimal in the utilitarian sense if:

Analogously, we can define committees optimal in the egalitarian sense, by replacing "sum" with "max" in Definition 1. For the sake of concreteness, in this paper we focus on the utilitarian case and refer to the optimality in the utilitarian case as to the optimality.

4 Optimality for Known Single-Winner Rules

In this section we show that several known multi-winner election rules can be viewed as optimal in our voting committee model. Each such a rule is optimal for different single-winner election system R2, used by the selected committee to make final decisions. Thus, our results give intuition regarding the applicability of different multi-winner election rules, depending on for what kind of decision making the committee is elected for.

Definition 2. Let R2 be a single-winner election rule used in the second stage of the election model. A multi-winner election rule R1 is optimal for R2 if for each preferences of voters it elects an optimal committee.

For multi-winner approval rules and deterministic model, we will add the additional word "deterministically" to the notion of optimality.

We start with presenting four theorems characterizing four multi-winner election rules in which voters express their preferences by approving subsets of candidates. These rules are optimal for majority, random dictatorship, and unanimity single-winner election systems.

Theorem 1. Assume K is odd. The K+1 2 -median election system is deterministically optimal for the majority rule.

Proof. We calculate PC,R2 (i), the ultimate satisfaction of a voter i from a committee C, assuming C uses majority rule to make final decisions. Since the model is fully deterministic, and a committee member a ∈ C votes according to i's preferences if and only if a is approved by i, a committee C makes decisions consistent with i's preferences, if it contains at least K+1 2 members approved by i. Thus, the satisfaction PC,R2 (i) of i fromC is equal to 1 if C contains at least K+1 2 members approved by i, otherwise it is equal to 0.

The same formula defines satisfaction of i from C in the K+1 2 -median election system. Finally, we note that in the K+1 2 -median election system, the committee that maximizes voters' total satisfaction is selected, which completes the proof.

Theorem 2. The K-approval election system is optimal for the uniformly random dictatorship rule.

Proof. For a committee C, let apprvi(C) denote the number of candidates from C that are approved of by i. Let p and q denote the probability of representation of i by candidates approved of and disapproved of by i, respectively. Naturally, p > q. For each important for i issue Dj ∈ Dim(i) and each committee C let P(C, a) denote the probability that, during the uniformly random dictatorship ballot regarding Dj, the final decision will be made by the committee member a. Naturally, P(C, a) = 1K . The probability that C will vote according to i's preferences is equal to:

Consequently, a committee C is optimal if it has the maximal value ∑i apprvi(C). Exactly such committee is elected by the K-approval election system.

Theorems 1, and 2 are quite powerful in a sense that they claim the optimality of the K+1 2 -median and K-approval multi-winner election rules, for the corresponding singlewinner rules, irrespectively of the preferences of the voters over the issues. Unfortunately, this is not always the case, which is expressed by the following two theorems.

Before we proceed further, we introduce two new definitions that describe two extreme classes of voters' preferences over the issues. The intuitive meaning of these two classes can be better expressed if we rename the alternatives d0 and d1 to pass and veto, respectively. We say that voters are rejection-oriented if for each voter i, and each Dj ∈ Dim(i), dji = d1 (after renaming, dji = veto), meaning that each voter gets utility only from rejecting important issues. Analogously, we say that the voters are acceptance-oriented if for each voter i, and each Dj ∈ Dim(i), dji = pass.

Theorem 3. For rejection-oriented voters, ChamberlinCourant system with approval votes is deterministically optimal for the unanimity system.

Proof. Here, the reasoning is very similar to the proof of Theorem 1. The ultimate satisfaction of a voter i from a committee C, PC,R2 (i), is equal to 1 if C contains at least one candidate approved by i, and is equal to 0 otherwise. This is equivalent to the definition of voters' satisfaction in the Chamberlin-Courant election rule, which completes the proof.

Theorem 4. For acceptance-oriented voters, the K-median system with approval votes is deterministically optimal for the unanimity system.

Theorems 3 and 4 suggest that Chamberlin-Courant's rule and K-median rule are suitable for electing committees that have veto rights. One should choose one of them depending on the voters' satisfaction model. For instance, if passing a wrong decision has much more severe consequences than rejecting a good one (which is captured by modeling the voters as rejection-oriented), a committee should be selected with Chamberlin-Courant's rule, and it should use unanimity rule to make final decisions. If passing a wrong decision has relatively low cost compared to rejecting a good one, the committee should be selected with a K-median rule

Below, we show a more general result that characterizes a class of optimal election systems for most natural singlewinner election rules R2 : {0, 1}K → R. These "natural" rules are those which satisfy neutrality, anonymity and monotonicity (for the definitions of these properties we refer the reader to the work of Endriss [2015]). Intuitively, the outcomes of such rules depend on the number of votes given to certain alternatives only.

Definition 3. A nondeterministic rule R2 : {0, 1}K → R is normal if there exists a non-decreasing function Rn : N → R such that R2(v) = Rn(|{i : v[i] = 0}|), and such that for each j, Rn(j) = 1 - Rn(K - j).

In Definition 3, the requirement that for each j, Rn(j) = 1 -Rn(K - j) enforces that the probability of selecting the value 0 given j votes for 0 is equal to the probability of selecting 1, given j votes for 1, thus, it follows from neutrality.

Theorem 5. For each normal election systemR2, in the approval model there exists a K-element vector α, such that α-rule with approval votes is optimal for R2.

Proof. Let Rn be as in Definition 3. Let Cℓ,i denote the committee that has exactly ℓ members approved of by i, and let P(i, s, ℓ) be the probability that exactly s members of Cℓ,i will vote accordingly to i's preferences. We have:

We can see that P(i, s, ℓ) does not depend on i. Further, let PR2 (i|s) be the probability that the rule R2 makes decision consistent with i's preferences, assuming s members of Cℓ,i votes accordingly to i's preferences.

Since either dji = dj,0 or dji = dj,1 and since Rn(s) = (1 -Rn(K - s)), we get that PR2 (i|s) = Rn(s), and thus PR2 (i|s) does not depend on i. Consequently, for each important for i issue Dj ∈ Dim(i) we can calculate the expected ultimate satisfaction PCℓ,i,R2 (i) of a voter i from a committee Cℓ,i, so that this value does not depend on i:

Because PCℓ,i,R2 (i) does not depend on i, we will denote it as PCℓ,R2 . Naturally, since p ≥ q, we have PCℓ+1,R2 ≥ PCℓ,R2 , for each ℓ. Now, we can see that the following vector:

satisfies the requirement from the thesis. Indeed, in the αrule the satisfaction of a voter from a committee with ℓ approved members is the sum of first ℓ coefficients of α, which is PCℓ,R2 . This completes the proof.

The above theorem can be viewed as an evidence of the expressiveness and power of OWA election rules. Unfortunately, OWA election rules are not sufficiently expressive to describe the non-approval model. To get characterization similar to the one given in Theorem 5, but for arbitrary utilities, we would need to consider a more general class of election rules, that is rules in which the satisfaction of a single voter i from a committee C is expressed as a linear combination of products of i' utilities from individuals: ∑C′⊆C ∏a∈C′ ui(a) (in contrast to a linear combination of utilities only). Such rules that consider inseparable committees were considered e.g., by Ratliff [2006; 2003]. Nevertheless, for the case of arbitrary utilities, we can get a result similar to the one given in Theorem 2.

Theorem 6. There exists a utility function P : R → R transforming voters' utilities to representation probabilities, such that K-top election system is optimal for the uniformly random dictatorship rule.

Proof. Let us define P(C, a) as in the proof of Theorem 2. The probability that C will vote according to i's preferences is equal to:

Let P be the identity function. The rule that maximizes the total score of selected candidates, also maximizes their total expected ultimate satisfaction. This completes the proof.

5 Optimality of Indirect Election Rules

In the previous section we studied the optimality of multiwinner election rules, given information on what singlewinner election system the committee will use to make final decisions. In this section we show that in our probabilistic model we can compare qualities of the pairs of multi-winner and single-winner systems. Thus, our results not only suggest which multi-winner election rule is suitable for electing a committee, but also indicates which single-winner rule should be used by the committee to make final decisions. We start with introducing the definition of the indirect election rule. This definition uses an interesting concept: it allows the voters to elect not only committees, but also single-winner rules that these committees use to make final decisions.

Definition 4. An indirect election rule is a function F : Πn (N) → P(A) × SW that for each utility profile πn ∈ Πn (N) returns a pair F(πn ) = (C,R2), where C ∈ P(A)

is the elected committee, and R2 ∈ SW is the single-winner election rule that C will use when making final decisions. We use the notation F(πn )[1] = C and F(πn )[2] = R2.

Definition 5. Let P : R → R be a function transforming voters' utilities to representation probabilities. An indirect election rule F weakly dominates an indirect election rule G for P, if for each utility profile πn ∈ Πn (N), F returns a committee and a single-winner rule that gives the total expected ultimate satisfaction of the voters at least as high as the one given by a committee and a single-winner rule returned by G:

F strongly dominates G for P if it weakly dominates G and if there exists profile πn ∈ Πn (N) for which:

An indirect election rule F is optimal for P if it weakly dominates every other indirect election rule.

Definition 6. For a multi-winner rule R1 and a single-winner rule R2, by R1 followed by R2 we call the indirect function that selects committee using R1 and, independently of voters' preferences, always uses R2 to make final decisions.

We show how to apply Definition 5 in perhaps the simplest variant, that is in the deterministic approval model. First, we define a new election rule COMB as a combination of K+1 2 - median rule followed by majority rule with the K-approval rule followed by uniformly random dictatorship rule.

Definition 7. The rule COMB is defined as follows. Let C and C ′ be committees elected by K-approval rule and by K+1 2 -median rule, respectively. Let apprv be the total approval score of C and let owa be the total OWA score of C ′ . If apprv K > owa, then COMB returns the pair (C, uniformly random dictatorship). Otherwise, COMB returns the pair (C′ , majority).

In our deterministic model, the new rule COMB strongly dominates both rules that it is derived from.

Proposition 1. In the deterministic model, COMB strongly dominates K+1 2 -median followed by majority, and Kapproval followed by uniformly random dictatorship.

Proof. Let apprv and owa be defined as in Definition 7. Repeating the analysis from the proofs of Theorems 1 and 2, we get that the total ultimate satisfaction of voters under K+1 2 -median followed by majority is equal to owa, under Kapproval followed by uniformly random dictatorship is equal to apprv K , and under COMB is equal tomax( apprv K , owa). This completes the proof.

The natural question is whether we can find an optimal rule in our general probabilistic model. Unfortunately, this seems unlikely, as the societal quality of a rule also depends on the underlying voters' utility model. For instance, if for each j, Dj = {pass, veto}, and the voters are rejection-oriented, they prefer rules in which committees can more easily make a collective decision veto. In fact, for the rejection-oriented voters we can show that any multi-winner rule followed by the constant single-winner rule that always returns veto is optimal. Such rules, on the other hand, are highly disliked by the acceptance-oriented voters. Interestingly, if we restrict ourselves to normal single-winner rules to make final decisions, and to the deterministic model, then there exists an optimal indirect rule.

Theorem 7. In the deterministic model, if we consider only normal single-winner rules used for making the final decisions, then there exists an optimal indirect election rule.

Proof. The proof is constructive. FromDefinition 3 we recall that a normal single-winner rule R2 can be described by K values Rn(1), . . . ,Rn(K). We use notation from the proof of Theorem 5. In the deterministic model P(i, s, ℓ) = 1s=ℓ. Consequently, for a committee Cℓ with ℓ approved members, we have PCℓ,R2 = Rn(ℓ). Let 1ℓ,i(C) denote a function that returns 1 if C contains ℓ elements approved of by i, and 0 otherwise. For a given committee C we can find an optimal single-winner election rule R2 by solving the following linear program:

subject to:

The optimal indirect rule tries all committees and selects such that gives the best solution to the integer program. From the solution of the integer program we can extract values Rn(1), . . . ,Rn(K) that describe the optimal single-winner election rule that should be used to make final decisions.

6 Conclusion

We defined a new model, called the voting committee model, which explores scenarios where a group of representatives is elected to make decisions on behalf of the voters. This model links utilities of the voters from the elected committee to their utilities from the committee's decisions regarding various matters. Intuitively, a satisfaction of voter i from a committee C is proportional to the probability that for the issues important for i, C's decisions are consistent with i's preferences.

Most of our results are for a restricted version of the model, called the approval model, in which each voter distinguish only two types of candidates: the candidates who represent her well and those who do not.

Our main conclusion says that different multi-winner election systems are suitable for choosing committees, depending on the rule used by the elected committee to make decisions. In particular, we justified which known multi-winner rules are suitable for which single-winner ones. Further, under some simplifying assumptions, we showed that the class of OWA rules contains all optimal multi-winner election systems.

We introduced the notion of an indirect rule, in which voters elect a decisive committee along with the single-winner rule to be used. Under some assumptions, we showed that there exists an optimal indirect rule and we described the way how it can be constructed.

There is a number of natural questions and open directions for future work. For instance, it is interesting to find out whether the optimal indirect rule can compute winning committees in polynomial time. Another appealing direction is to extend our model beyond binary domains and to analyze a variety of other single-winner rules.

Acknowledgements. The author was supported by Polish National Science Centre grant Preludium 2013/09/N/ST6/03661.