Keywords

JEL Class:

Arrovian social choice theory provides a theoretical framework for evaluating social choice functions, which aggregates individual ordinal preferences over social alternatives, or candidates, into a collective outcome. In the case where the outcome is a single candidate, asking voters to report their ranking of candidates is not problematic. However, if a committee of several candidates is to be chosen, this informational requirement is hardly implementable in practice. Consider an election of a faculty council involving a dean, a vice-dean for research and a vice-dean for teaching. If there are four candidates per seat, fully expressing preferences means ranking the 64 possible outcomes. Clearly, as the number of seats or the number of candidates for each seat increase, referring to Arrovian social choice functions becomes less and less useful in practice. Designing a seat-wise procedure is a frequent solution that overcomes this difficulty. In a seat-wise procedure, voters report their preferences over candidates seat-wise, and candidates are selected seat-wise. It is well-known that a seat-wise procedure may not lead to the outcome that would prevail for a direct choice procedure where voters report their preferences over the outcomes. This happens when individual preferences exhibit complementarities among candidates, but this may even prevail with separable preferences which prohibits any sort of complementarity.

The potential inconsistency between seat-wise and direct procedures results from the fact that seat-wise preferences describe only partially preferences over outcomes. A rather rich literature dealing with this inconsistency and other potential drawbacks of seat-wise procedures deals with multiple referenda, which is equivalent to a committee choice problem with two candidates per seat. In this setting, each voter is characterized by an ideal committee, and simple majority voting provides a natural seat-wise choice procedure that we denote by Maj. Compound majority voting paradoxes studied in the literature express the fact that Maj may lead to outcomes exhibiting some undesirable properties. The Anscombe’s paradox (Anscombe 1976; Wagner 1984; Laffond and Lainé 2013) shows that a majority of voters may disagree with the outcome of Maj on a majority of seats. The multiple elections paradox (Brams et al. 1998; Scarsini 1998) prevails when the winner for Maj receives zero votes in the direct elections (or, equivalently, may be ranked first by no voter). The Ostrogorski paradox (Ostrogorski 1902; Rae and Daudt 1976; Bezembinder and Van Acker 1985; Deb and Kelsey 1987; Kelly 1989; Shelley 1994; Laffond and Lainé 2006) prevails when another outcome beats the one of Maj according to majority voting under the assumption that committees are compared by means of the Hamming distance criterion.Footnote 1\(^{,}\)Footnote 2

The Hamming distance criterion provides a specific way to relate seat-wise preferences and preferences over committees. Other ways can be considered, each referring to a particular preference extension. Formally, when there are only two candidates per seat, a preference extension rule maps each ideal committee to a (weak) ordering of committees. A usual property retained for a preference extension is separability: if a and b are the two candidates for some seat s, and if a voter ranks a above b, she will rank two committees identical in all seats but s according to her preference over a and b.Footnote 3 Kadane (1972) shows that even under the assumption of a separable extension, Maj may select a Pareto dominated committee. Moreover, Özkal-Sanver and Sanver (2006) show that if there are at least three seats, no anonymous seat-wise procedure guarantees that a Pareto optimal committee will be chosen for all separable preference extensions. However, for the Hamming preference extension rule, Maj always produce a Pareto-optimal committee (Brams et al. 2007). Çuhadaroğlu and Lainé (2012) prove that under a mild richness assumption, the Hamming preference extension defines the largest domain of separable preference extensions for which Maj always picks a Pareto optimal outcome.Footnote 4

All the above mentioned studies deal with the case of two candidates per seat. Less attention has been paid to situations where there are more than two candidates per seat. Benoît and Kornhauser (2010) generalize the result of Özkal-Sanver and Sanver (2006): if any separable preference extension is admissible, and if there are at least three seats or when there are precisely two seats with more than two candidates per seat, a seat-wise procedure selects a Pareto optimal outcome if and only if it is dictatorial. While this strong result disqualifies seat-wise procedures in the full domain of separable preferences extensions, it suggests investigating whether they can perform better under some domain restrictions. This is the route followed in this paper, which addresses the following question: can we characterize the class of preference extensions under which Maj selects a Condorcet winner committee, that is a committee preferred to all other committees by a majority of voters?

One difficulty is that Maj is not well-defined with at least three candidates per seat. Indeed, it is well-known that a Condorcet winner for each seat (i.e., a candidate preferred to all other candidates by a majority of voters) may fail to exist. However, well-known restrictions upon voters’ preferences ensure the existence of a seat-wise Condorcet winner are single-peakedness and Sen’s value restriction (Black 1948; Sen 1966). We assume that preferences over candidates for each seat are such that a Condorcet winner exists, and we address the following problem: characterizing the preference extension domain for which the committee formed by all seat-wise Condorcet winners form a Condorcet winner among committees. If Maj selects a Condorcet winner committee, there is no inconsistency between seat-wise majority voting and direct majority voting (where voters rank committees). Hence, characterizing the preference extension domain that precludes this inconsistency solves the problem created by the Arrovian informational requirement: in order to fulfill the majority will for committees, it is sufficient to fulfill the majority will for each seat.

The inconsistency between seat-wise majority voting and direct majority voting arises in two cases, each related to a new voting paradox. The majority committee paradox prevails when a Condorcet winner committee exists and is not selected by Maj. The majority committee weak paradox prevails when either the majority committee paradox holds or a Condorcet winner committee fails to exist (while Maj is well-defined).

Under a neutrality assumption for preference extensions (meaning that candidates’ names play no role), we characterize the preference extension domain immune to the majority committee paradox and the one immune to the majority committee weak paradox in the case of two-seat committees. More precisely, we prove that separability is a necessary and sufficient condition for a neutral preference extension to avoid the majority committee paradox. Moreover, the domain of neutral preference extensions avoiding the majority committee weak paradox is much smaller, it reducing to a unique lexicographic preference extension. According to lexicographic preference extensions all voters agree on a seat as priority seat and compares committees according to their ranking of candidates for that priority seat whenever they differ and if both committees have the same candidate on the priority seat, compares them according to ranking of candidates for other seat.

Our results complement the ones obtained by Hollard and Le Breton (1996) and Vidu (1999, 2002). In the case of two candidates per seat, Hollard and Le Breton (1996) show that any separable tournament over committees can be achieved through seat-wise majority voting. This result is generalized in Vidu (1999) to the case of more than two candidates per seat. Moreover, Vidu (2002) shows that a similar result prevails even when seat-wise preferences are single-peaked (implying the existence of seat-wise Condorcet winners).

The paper is organized as follows. Section 2 provides basic notations and definitions. Majority committee paradoxes are formalized in Sect. 3. Results are stated in Sect. 4. We conclude with several comments about further research.

1 The Model

1.1 Preliminaries

We consider two finite sets \(\mathbb {C}_{1}\) and \(\mathbb {C}_{2}\), with respective cardinalities \(C_{1}\) and \(C_{2}\). Sets \(\mathbb {C}_{1}\) and \( \mathbb {C}_{2}\) are interpreted as sets of candidates competing for seat-1 and for seat-2. We use letters a, b, c to denote arbitrary candidates for seat-1 and x, y, z to denote arbitrary candidates for seat-2. A committee \(\mathcal {C}\) is an element of \(\mathbb {C}=\mathbb {C} _{1}\times \mathbb {C}_{2}\).

We also consider a finite set of voters \(\mathcal {N}=\{1,...,n,...,N\}\) where \(N\in \mathbb {N}\) is odd. For each \(t\in \{1,2\}\), every voter n has preferences over candidates in \(\mathbb {C}_{t}\), called t-preferences, represented by a complete linear order \(P_{n}^{t}\). The upper-contour set of a candidate \(a\in \mathbb {C}_{t}\) for \(P_{n}^{t}\) is defined by \( U(a,P_{n}^{t})=\{b\in \mathbb {C}_{t}:bP_{n}^{t}a\}\). Moreover, the rank of a in \(P_{n}^{t}\) is defined by \(r^{t}(a,P_{n}^{t})=1+\left| U(a,P_{n}^{t})\right| \). Given a finite set X, let \(\mathcal {L}(X)\) denote the set of linear orders over X. Finally, for \(t=1,2\), a t -profile \(\pi ^{t}=(P_{n}^{t})_{n\in \mathcal {N}}\) is an element of \(( \mathcal {L}(\mathbb {C}_{t}))^{N}\).

We call preference over committees, or in short preference, of voter n an element \(P_{n}=(P_{n}^{1},P_{n}^{2})\) of \(\mathcal {L}(\mathbb {\ C} _{1})\times \mathcal {L}(\mathbb {C}_{2})\). The \(P_{n}\)-rank vector of committee \(\mathcal {C}=(a,x)\in \mathbb {C}\) is defined by \(r(\mathcal {C} ,P)=(r^{1}(a,P_{n}^{1}),r^{2}(x,P_{n}^{2}))\). A profile is an element \(\pi =(P_{n})_{n\in \mathcal {N}}\) of \((\mathcal {L}(\mathbb {C} _{1})\times \mathcal {L}(\mathbb {C}_{2}))^{N}\).

1.2 Preference Extension

Seat-wise preferences over candidates and preferences are logically related. We assume that preferences over candidates for each seat are extended to preferences by means of a preference extension. Formally, a preference extension is a mapping \(\delta \) from \(\mathcal {L}(\mathbb {C} _{1})\times \mathcal {L}(\mathbb {C}_{2})\) to \(\mathcal {L}(\mathbb {C})\). A preference extension profile is a vector \(\delta ^{\mathcal {N} }=(\delta _{1},...,\delta _{N})\) of preference extensions. Given a profile \( \pi =(P_{n})_{n\in \mathcal {N}}\in (\mathcal {L}(\mathbb {C}_{1})\times \mathcal {L}(\mathbb {C}_{2}))^{N}\), a preference extension profile \(\delta ^{ \mathcal {N}}\) generates the extended profile \(\delta ^{\mathcal {N}}(\pi )=((\delta _{n}(P_{n}))_{n\in \mathcal {N}}\in (\mathcal {L}(\mathbb {C}))^{N}\).

We retain two properties for preference extensions, neutrality and separability. Neutrality prevails if the names of candidates do not matter when comparing committees. In other words, only ranks given to candidates are taken into account.

Definition 1

A preference extension \(\delta \) is neutral if for all \( P=(P^{1},P^{2})\), \(P^{^{\prime }}=(P^{^{\prime }1},P^{^{\prime }2})\in \mathcal {L}(\mathbb {C}_{1})\times \mathcal {L}(\mathbb {C}_{2})\), and for all \( \mathcal {C},\mathcal {C}^{\prime }\in \mathbb {C}\), if \([r(\mathcal {C},P)=r( \mathcal {C},P^{\prime })\) and \(r(\mathcal {C}^{\prime },P)=r(\mathcal {C} ^{\prime },P^{\prime })\) ] then \([\mathcal {C}\delta (P)\mathcal {C}^{\prime }\Leftrightarrow \mathcal {C}\delta (P^{\prime })\mathcal {C}^{\prime }]\).

It follows from Definition 1 that given a preference \(P\in \mathcal {L}( \mathbb {C}_{1})\times \mathcal {L}(\mathbb {C}_{2})\), any neutral preference extension \(\delta \) can be equivalently defined as the linear order \(\gg _{\delta }\) over \(\{1,...,C_{1}\}\times \{1,...,C_{2}\}\) by: for all i, j \(\in \) \(\{1,...,C_{1}\}\times \{1,...,C_{2}\}\), \(i\gg _{\delta }j\) if and only if there exists \(\mathcal {C},\mathcal {C}^{\prime }\in \mathbb {C}\) such that \(\mathcal {C}\delta (P)\mathcal {C}^{\prime }\) where \(r(\mathcal {C},P)=i\) and \(r(\mathcal {C}^{\prime },P)=j\). Hence, a neutral preference extension profile can be equivalently defined by vector \(\gg _{\delta ^{ \mathcal {N}}}=(\gg _{\delta _{1}},...,\gg _{\delta _{N}})\).

We denote the set of neutral preference extensions by \(\varDelta \).

The following example illustrates how a neutral extension operates. Let \( \mathbb {C}_{1}=\{a,b\}\), \(\mathbb {C}_{2}=\{x,y\}\), \(\mathcal {N}=\{1,2,3\}\), and consider the seat-wise profiles \(\pi =(\pi ^{1},\pi ^{2})=((P_{n}^{1},P_{n}^{2})_{n=1,2,3})\) defined below:

figure a

Let \(\gg _{\delta ^{\mathcal {N}}}\) be the following neutral preference extension profile:

figure b

\(\gg _{\delta ^{\mathcal {N}}}\) combined with \(\pi =(\pi ^{1},\pi ^{2})\) lead to the following extended profile:

figure c

Hereafter we refer to neutral preference extensions simply as preference extensions. The second property for preference extension rules we consider, called separability, holds if it is always preferable to assign a seat to a better candidate whoever the other committee member is. Hence, separability precludes any complementarity between candidates for different seats.

Definition 2

A preference extension \(\delta \) is separable if for all \(a,b\in \mathbb {C} _{1}\), for all \(x,y\in \mathbb {C}_{2}\), and for all \(P=(P^{1},P^{2})\in \mathcal {L}(\mathbb {C}_{1})\times \mathcal {L}(\mathbb {C}_{2})\),

  • (ax) \(\delta (P)\) (bx) if and only if a \(P^{1}\) b

  • (ax) \(\delta (P)\) (ay) if and only if x \(P^{2}\) y.

Under neutrality, separability is equivalently defined as follows:

  • for all \((i_{1},i_{2})\ne (j_{1},i_{2})\) \(\in \) \(\{1,...,C_{1}\}\times \{1,...,C_{2}\}\), \((i_{1},i_{2})\gg _{\delta }(j_{1},i_{2})\) if \(i_{1}<j_{1} \)

  • for all \((i_{1},i_{2})\ne (i_{1},j_{2})\) \(\in \) \(\{1,...,C_{1}\}\times \{1,...,C_{2}\}\), \((i_{1},i_{2})\gg _{\delta }(i_{1},j_{2})\) if \(i_{2}<j_{2}\).

The set of neutral and separable extensions is denoted by \(\varDelta ^{sep}\). We introduce below two specific elements of this set:

Definition 3

  • The 1-lexicographic preference extension \(\delta ^{1Lex}\) is defined by:

    \((1,1)\gg (1,2)\gg ...\gg (1,C_{2})\gg ...\gg (C_{1},1)\gg (C_{1},2)...\gg (C_{1},C_{2})\).

  • The 2-lexicographic preference extension, \(\delta ^{2Lex}\) is defined by:

    \((1,1)\gg (2,1)\gg ...\gg (C_{1}, 1)\gg ...\gg (1,C_{2})\gg (2,C_{2})...\gg (C_{1},C_{2})\).

The following definition of a choice problem summarizes all the relevant features of a committee selection procedure:

Definition 4

A choice problem is a 5-tuple \(\mathcal {P}=(\mathbb {C}_{1},\mathbb {C}_{2}, \mathcal {N},\pi ,\delta ^{\mathcal {N}})\) where \(\mathbb {C}_{1}\) and \(\mathbb { C}_{2}\) are the set of candidates for seat-1 and seat-2 respectively, \( \mathcal {N}\) is the set of voters with profile \(\pi \in (\mathcal {L}(\mathbb { C}_{1})\times \mathcal {L}(\mathbb {C}_{2}))^{N}\), and \(\delta ^{\mathcal {N} }\in \varDelta ^{N}\) is a preference extension profile.

2 Majority Voting Paradoxes

We now formalize seat-wise and direct selection procedures based on simple majority voting. This requires formalizing two types of majority tournaments. Given \(t\in \{1,2\}\) together with a t-profile \(\pi ^{t}=(P_{n}^{t})_{n\in \mathcal {N}}\in (\mathcal {L}(\mathbb {C}_{t}))^{N}\), the \(\pi ^{t}-\)majority tournament is the complete and asymmetric binary relation \(T(\pi ^{t})\) defined over \(\mathbb {C}_{t}\times \mathbb {C}_{t}\) by: \(\forall a,b\in \mathbb {C}_{t}\), \(aT(\pi ^{t})b\) if and only if \(\left| \{n\in \mathcal {N}:xP_{n}^{t}y\}\right| >\frac{N}{2}\). If \(aT(\pi ^{t})b\), we say that candidate a defeats candidate b in \( \pi ^{t}\). Similarly, given a profile \(\pi =(P_{n})_{n\in \mathcal {N}}\in ( \mathcal {L}(\mathbb {C}_{1})\times \mathcal {L}(\mathbb {C}_{2}))^{N}\) together with a preference extension profile \(\delta ^{\mathcal {N}}\), the \(\delta ^{ \mathcal {N}}(\pi )-\)majority tournament is the complete and asymmetric binary relation \(T(\delta ^{\mathcal {N}}(\pi ))\) defined over \(\mathbb {C} \times \mathbb {C}\) by: \(\forall \) \(\mathcal {C,C}^{\prime }\in \mathbb {C}\), \( \mathcal {CT(\delta ^{N}(\pi ))C}^{\prime })\) if \(\left| \{n\in \mathbb {N} :\mathcal {C}\ \delta _{n}(P_{n})\ \mathcal {C}^{\prime }\}\right| >\frac{N }{2}\). If \(\mathcal {CT(\delta ^{N}(\pi ))C}^{\prime }\), we say that committee \(\mathcal {C}\) defeats committee \(\mathcal {C}^{\prime }\) in \(\delta ^{\mathcal {N}}(\pi )\). Moreover, \(T(\pi ^{t})\) (resp. \(T(\delta ^{\mathcal {N} }(\pi ))\)) admits a (necessarily unique) Condorcet winner if there exists a candidate \(c(T(\pi ^{t})\in \mathbb {C}_{t}\) (resp. a committee \(c(T(\delta ^{ \mathcal {N}}(\pi ))\)) that defeats all other candidates in \(\pi ^{t}\) (resp. in \(\delta ^{\mathcal {N}}(\pi )\)). We adopt the convention \(c(T(\pi ^{t}))=\varnothing \) (resp. \(c(T(\delta ^{\mathcal {N}}(\pi )))=\varnothing \) ) when the underlying tournament has no Condorcet winner.

The seat-wise procedure consists of selecting a candidate for each seat from the seat-wise majority tournaments \(T(\pi ^{1})\) and \(T(\pi ^{2})\). We assume that preferences over candidates are restricted so as to ensure that both tournaments \(T(\pi ^{1})\) and \(T(\pi ^{2})\) admit a Condorcet winner. The direct procedure on the other hand consists of selecting a committee from the majority tournament over committees \(T(\delta ^{\mathcal {N}}(\pi ))\) . The seat-wise and direct procedures are inconsistent if either there is a Condorcet winner among committees that is not the combination of seat-wise Condorcet winners, or if there is no Condorcet winner among committees. This leads to the following two definitions of voting paradoxes:

Definition 5

The majority committee paradox occurs at choice problem \(\mathcal {P}\) if and only if \(T(\pi _{1})\), \(T(\pi _{2})\), and \(T(\delta ^{\mathcal {N}}(\pi ))\) each admit a Condorcet winner while \(c(T(\pi _{1}))\times c(T(\pi _{2}))\ne c(T(\delta ^{\mathcal {N}}(\pi )))\).

The majority committee paradox is illustrated in the following simple example:

Example 1

Let \(\mathbb {C}_{1}=\{a,b\}\), \(\mathbb {C}_{2}=\{x,y\}\), \(\mathcal {N} =\{1,2,3\}\), and consider the seat-wise profiles \(\pi =(\pi ^{1},\pi ^{2})\) defined below:

figure d

For \(i=1,2,3\) let \(\gg _{\delta _{i}}\) be \((2,1)\gg _{\delta _{i}}(1,2)\gg _{\delta _{i}}(1,1)\gg _{\delta _{i}}(2,2)\), combined with \(\pi \), leading to the following extended profile:

figure e

Clearly, \(c(T(\pi ^{1}))\times c(T(\pi ^{2}))=(a,x)\) and \(c(T(\delta ^{ \mathcal {N}}(\pi ))=(b,x)\), thus the majority committee paradox holds.Footnote 5

Definition 6

The majority committee weak paradox occurs at choice problem \(\mathcal {P}\) if and only if \(T(\pi _{1})\) and \(T(\pi _{2})\) both admit a Condorcet winner while \(c(T(\pi _{1}))\times c(T(\pi _{2}))\ne c(T(\delta ^{\mathcal {N}}(\pi ))\).

The majority paradox implies the weak majority paradox, while the opposite is not true. Moreover, it is straightforward to show that the majority paradox never prevails when there are two candidates per seat.

The next example will illustrate the majority committee weak paradox.

Example 2

Let \(\mathbb {C}_{1}=\{a,b\}\), \(\mathbb {C}_{2}=\{x,y\}\), \(\mathcal {N} =\{1,2,3\}\), and consider the seat-wise profiles \(\pi =(\pi ^{1},\pi ^{2})\) defined below:

figure f

Let \(\gg _{\delta ^{\mathcal {N}}}\) be such that

  • \((1,1)\gg _{\delta _{i}}(2,1)\gg _{\delta _{i}}(1,2)\gg _{\delta _{i}}(2,2) \) for \(i=1,3\).

  • \((1,1)\gg _{\delta _{3}}(1,2)\gg _{\delta _{3}}(2,1)\gg _{\delta _{3}}(2,2) \).

Combination of \(\gg _{\delta ^{\mathcal {N}}}\) with \(\pi \) leads to the following extended profile:

figure g

(ax) defeats (bx), (bx) defeats (ay), (ay) defeats (by), and finally, (by) defeats (ax) in \(\delta ^{\mathcal {N}}(\pi )\), So, there is no Condorcet winner among committees while \(\pi _{1}\) and \(\pi _{2}\) both admit condorcet winners. Thus, majority committee weak paradox holds.Footnote 6

3 Results

We define an extension domain as a non-empty subset \(\mathcal {D}\) of \(\varDelta \). First, we characterize the domain of preference extensions that are immune to the majority committee paradox in the following sense: \(\mathcal {D} \subseteq \varDelta \) is immune to majority committee paradox if and only if for all choice problems \(\mathcal {P}=(\mathbb {C}_{1},\mathbb {C}_{2},\mathcal { N},\pi ,\delta ^{\mathcal {N}})\) such that \(c(T(\pi _{1}))\ne \varnothing \), \(c(T(\pi _{2}))\ne \varnothing \) and \(c(T(\delta ^{\mathcal {N}}(\pi )))\ne \varnothing \); \(\delta ^{\mathcal {N}}\subseteq \mathcal {D}^{N}\) implies \( c(T(\pi _{1}))\times c(T(\pi _{2}))=c(T(\delta ^{\mathcal {N}}(\pi )))\). That is, a domain of preference extensions is immune to the majority committee paradox if and only if at any choice problem where all the voters use a preference extension from this domain and both seat-wise and committee-wise Condorcet winners exist; the combination of seat-wise Condorcet winners is the Condorcet winning committee.

Theorem 1

A preference extension domain \(\mathcal {D}\) is immune to the majority paradox if and only if \(\mathcal {D} \subseteq \varDelta ^{sep}\).

Our second result is a similar characterization for the weak majority weak paradox. Following an almost identical construction, we characterize the domain of preference extensions that are immune to the majority committee weak paradox in the following sense: \(\mathcal {D}\subseteq \varDelta \) is immune to majority committee paradox if and only if for all choice problems \( \mathcal {P}=(\mathbb {C}_{1},\mathbb {C}_{2},\mathcal {N},\pi ,\delta ^{ \mathcal {N}})\) such that \(c(T(\pi _{1}))\ne \varnothing \) and \(c(T(\pi _{2}))\ne \varnothing \); \(\delta ^{\mathcal {N}}\subseteq \mathcal {D}^{N}\) implies \(c(T(\pi _{1}))\times c(T(\pi _{2}))=c(T(\delta ^{\mathcal {N}}(\pi )))\). That is, a domain of preference extensions is immune to the majority committee weak paradox if and only if at any choice problem where all the voters use a preference extension from this domain and both seat-wise Condorcet winners exist; Condorcet winning committee exists and is equal to the combination of seat-wise Condorcet winners.

Theorem 2

A preference extension domain \(\mathcal {D}\) is immune to the majority weak paradox if and only if either \(\mathcal {D}=\{\delta ^{1Lex}\}\) or \(\mathcal { \ D}=\{\delta ^{2Lex}\}\).

4 Further Comments

Two routes are open for further research. The first is considering committee choice problems involving more than two seats. We strongly conjecture that results similar to Theorems 1 and 2 hold in this general setting. Finally, it would be interesting to characterize the domain of neutral preference extensions ensuring the existence of a Condorcet winning committee under the assumption that seat-wise Condorcet winners exist, disregarding whether the former is combination of latter ones.