extfieldsofstudy:
Economics
Computer Science
Mathematics

text:
Manipulability of consular election rules

The Gibbard-Satterthwaite theorem is a cornerstone of social choice theory, stating that an onto social choice function cannot be both strategy-proof and non-dictatorial if the number of alternatives is at least three. The Duggan-Schwartz theorem proves an analogue in the case of set-valued elections: if the function is onto with respect to singletons, and can be manipulated by neither an optimist nor a pessimist, it must have a weak dictator. However, the assumption that the function is onto with respect to singletons makes the Duggan-Schwartz theorem inapplicable to elections which necessarily select a committee with multiple members. In this paper we make a start on this problem by considering elections which elect a committee of size two (such as the consulship of ancient Rome). We establish that if such a consular election rule cannot be expressed as the union of two disjoint social choice functions, then strategy-proofness implies the existence of a dictator. Although we suspect that a similar result holds for larger sized committees, there appear to be many obstacles to proving it, which we discuss in detail.

Introduction
From that time on Caesar managed all the affairs of state alone and after his own pleasure; so that sundry witty fellows, pretending by way of jest to sign and seal testamentary documents, wrote "Done in the consulship of Julius and Caesar." -Suetonius, Lives of the Caesars. Chapter XX. Dummett and Farquharson [1961] conjectured what later became the Gibbard-Satterthwaite theorem [Gibbard, 1973, Satterthwaite, 1975, one form of which is: if a social choice function has at least 3 viable alternatives and is strategy-proof, then it is dictatorial. This result, though fundamental, is not applicable in many common situations, because symmetric voting rules must have ties. Gibbard [1977] extended the result to the case where ties are broken randomly, showing that such a rule is strategy-proof only if it is a mixture of rules that can only be affected by one voter, and rules that limit the outcome to two alternatives. While Gibbard did not mention it as such, this paper represents one of the first attempts at studying strategy-proof social choice correspondences, which output a set of alternatives, as opposed to a social choice function which outputs only one.
The fundamental difficulty in studying the manipulability of social choice correspondences is that, in a certain sense, the problem is ill-defined. To manipulate a social choice function, a voter submits an insincere preference ordering to obtain an outcome that is better than he would have obtained had he voted sincerely. To verify that the outcome is better, we can compare it against the voter's sincere ballot. In the case of a social choice correspondence the voter submits a preference order over alternatives, but the function produces a set of alternatives. We are not given enough information to deduce how the voter will assess the outcome, as there is no unique way to extend an order over a set to an order over the power set. Indeed, the subject of set ranking has been studied in detail (see Barberà et al. [2004] for a survey).
Supported by the NZ Marsden fund, grant UOA3706352. The authors acknowledge useful conversations with Arkadii Slinko.
A common approach taken by the early papers on strategy-proof social choice correspondences (e.g. Barberà [1977]; Kelly [1977]; Pattanaik and Dutta [1978]) is to assume some properties on what an extension from an ordering of alternatives to an ordering of sets must satisfy, and show that it implies some notion of dictatoriality, although to achieve these results the authors had to make further assumptions about the domains and behaviour of their functions. For example, under the positive response assumption of Barberà [1977] if a set X is elected at a profile P , and P 1 is obtained by a single voter bumping some x P X up their ballot, x becomes the unique winner under P 1 ; this condition is satisfied by, for example, Borda's rule, but is not satisfied by many other natural rules. The Duggan-Schwartz theorem [Duggan and Schwartz, 1992] stood out from these results because of how little it had to assume -that the correspondence be onto with respect to singletons -to achieve their result. That said, the Duggan-Schwartz theorem is difficult to compare with the previous work, because there is a subtle difference in the frameworks used. Duggan and Schwartz do not consider an extension of a preference order, but of a notion of manipulability. The two are not interchangeable as there are certain properties we expect from an order -at the very least, transitivity, desirably, completeness, and ideally, anti-symmetry -whereas just about any binary relation can serve for manipulability. In particular, the optimistic/pessimistic manipulation of Duggan-Schwartz does not induce a transitive preference order, as it is possible for a voter to optimistically prefer X to Y and pessimistically prefer Y to X (see Section 2 and 4 for more details). For a more thorough overview of the history of strategy-proofness, the reader is recommended to see Barberà [2010].
In this paper we concentrate on social choice correspondences that must always output a set of fixed size k, which we call committee selection rules [Skowron et al., 2016]. In this setup, the assumptions of the abovementioned papers are unnatural or vacuous -for example, being onto with respect to singletons can never happen. Thus a different approach is needed. This is not the first paper on strategy-proof committee selection rules.Özyurt and Sanver [2008] and Reffgen [2011] are the most relevant to the enquiry pursued here. The general approach of those two papers is the same: demonstrate that a certain extension of a preference order from A to fixed-size committees over A results in what Aswal et al. [2003] define as a linked domain, and appeal to a theorem of Aswal et al. [2003] that states that a unanimous social choice function on a linked domain is dictatorial.Özyurt and Sanver [2008] demonstrate that all reasonable extensions, roughly speaking extensions which have a clear first and second choice, result in linked domains, and Reffgen [2011] deals with extensions that satisfy the axiom used by Kelly [1977]. Neither paper implies our result, but our general approach is the same -construct a linked domain and invoke Aswal et al. [2003].
To obtain our result we use a lexicographic extension of preferences over alternatives to preferences over sets: a voter compares X and Y by first comparing his favourite elements in X and Y , then the second favourite, and so on. While this is not equivalent to the Duggan-Schwartz conditions, in the case of a rule that elects a pair of alternatives it is strictly narrowerevery lexicographic manipulation is either an optimistic or a pessimistic manipulation. Thus an impossibility result for lexicographic manipulations implies, a fortiori, an impossibility result for pessimistic/optimistic manipulation.Özyurt and Sanver [2009] and Campbell and Kelly [2002] also work in the framework of lexicographic manipulation and their results imply a weakened version of our main theorem -an impossibility result for manipulating an onto selection rule, but do not imply our more general result.
1.1. Our contribution. We work in the manipulation framework of Duggan-Schwartz: setvalued functions that cannot be manipulated by an optimist and cannot be manipulated by a pessimist. In particular, we are interested in committee selection rules that select a committee of size two. Since the Duggan-Schwartz assumption that a correspondence is onto with respect to singletons is meaningless here, we replace it with the assumption that it is possible for every alternative to be on some winning committee. This does not imply that all possible committees lie in the range of the function, as we demonstrate in Fact 5.1. This, in turn, forces us to consider a new notion of dictatorship (Definition 5.17). Roughly speaking, a dictator is a voter who gets his "best" outcome no matter what, but the difficulty is in showing that this notion is well-defined.
We start with the observation that such rules can be defined in two categories: those that can be reduced to the union of two disjoint social choice functions (reducible rules) and those that cannot (irreducible). It turns out that irreducible rules can have a non-trivial structure to their range, which we characterise by modelling the range as a graph. This interpretation may be useful in the future, as it establishes an interesting connection between strategy-proofness and a structural property of graphs (Proposition 5.14).
Our main result (Corollary 6.12) shows that for irreducible rules, strategy-proofness for optimists and pessimists implies that some voter always gets his favourite viable committee elected.
For reducible rules, we observe that the Gibbard-Satterthwaite theorem dictates that if the number of viable alternatives is at least five then the function will have a "partial" dictator on part of the domain, but it may not have an overall dictator -these rules are non-dictatorial, but in a very trivial sense. In the special case where one of the component social choice functions has a domain of size one, i.e. it always elects the same alternative, some voter always gets his favourite committee elected if the number of viable alternatives is at least four.

Preliminaries
We use S k pXq to denote the set of all k-element subsets of a set X. When we are talking about a preference order P i , we use the standard infix notation: ľ i for the non-strict order, ą i for the strict counterpart, and x " i y for indifference.
Definition 2.1. Let V be a finite set of voters, A a finite set of alternatives.
A profile P consists of a linear order over A (also known as a preference order or a ballot), P i , for every voter i. The set of all profiles of voters V over alternatives A is denoted PpV, Aq. We use P´i to refer to the ballots of all voters except i. Hence, P " P i P´i and P 1 i P´i is obtained from profile P by replacing P i with P 1 i . A social choice function maps a profile to a single alternative, F : PpV, Aq Ñ A. A social choice correspondence produces a nonempty set of alternatives, F : PpV, Aq Ñ 2 A zt H u. A k-committee selection rule produces a set of alternatives of size k, F : PpV, Aq Ñ S k pAq. A 2-committee selection rule is called a consular election rule.
Definition 2.2. Let H ‰ W Ď A. We use bestpP i , W q to denote the best alternative in W according to P i , worstpP i , W q the worst.
We extend ľ i into three relations over 2 A zt H u: A committee selection rule is strategy-proof for pessimists (SPP) if for all P 1 i , whenever F pP i P´iq " W and F pP 1 i P´iq " W 1 , W ľ P i W 1 . Duggan and Schwartz define viability to be the notion that for every a P A, there exists a P such that F pP q " t a u. This is reasonable in the context of a social choice correspondence -an election rule that allows a certain candidate to be tied for victory, but never to win outright, seems rather strange. In the case of k-committee selection rules it is a vacuous concept. We use a weaker notion of viability where every alternative has the chance to appear on some winning committee, but we make no assumptions on whom the alternative might have to share the privilege with.
Definition 2.3. A committee selection rule satisfies weak viability if for every a P A, there exists P such that a P F pP q.
A committee rule is unanimous if whenever bestpP i , Aq " a for all i, necessarily a P F pP q (if all the voters agree on the best alternative, it is on the committee).
A committee rule satisfies veto if whenever worstpP i , Aq " a for all i, necessarily a R F pP q (if the voters agree on the worst alternative, it is not on the committee).
The notion of a dictator in the case of a social choice function is straightforward -every voter has a unique first choice alternative, so if that voter is a dictator it stands to reason that the first choice will be elected. In the literature on social choice correspondences this notion is typically extended by defining a dictator to be a voter who always gets an outcome that is maximal in the extension of his preferences to sets.
However, Duggan-Schwartz manipulability does not extend to a preference order over 2 A zt H u. To see this, consider a voter with preferences a There are, however, two natural notions of dictatorship we can define without appealing to preferences over sets.
Definition 2.4. A social choice function F is dictatorial if there is some i P V such that F pP q is always the first choice of i. Given a committee selection rule F , a weak dictator is some i P V such that the first choice of i is always in F pP q. Given a k-committee selection rule F , a strong dictator is some i P V such that F pP q consists of the top k choices of i.
Note that there is a duality at play here. A weak dictator is precisely a voter who gets a maximal outcome under ľ O i and a strong dictator gets a maximal (in fact, the maximum) outcome under ľ P i . This suggests a natural definition of a dictator in the Duggan-Schwartz case: a voter that gets an outcome that is maximal under both preference orders. However, as at this point we have no guarantee that such a notion is well-defined (a priori, there is no reason to assume that there is an element in the range of an election that is maximal under both orders), we shall postpone introducing it until Definition 5.17.

Monotonicity
It is common to obtain impossibility results in social choice by showing that the concept in question implies some sort of monotonicity on ballots. This typically takes the form that swapping two alternatives in some ballot either does not change the outcome of an election, or changes it in a very predictable way. Our approach is no different. We will show that in elections which satisfy SPP and SPO, moving an alternative up or down a ballot affects only whether that alternative features on the winning committee or not.

Auxiliary results.
Definition 3.1. P iÒs is the profile obtained from P by swapping s in P i with the alternative directly above it, and P Òs i :" pP iÒs q i is the resulting order for voter i. We start with a simple observation: if we swap a candidate upward, it may become the most preferred but will not change the least preferred element. Note that bestpP Òs i , W q " s can only occur if s is the second-most preferred element of W .
Lemma 3.2. Let W Ď A. Let t :" bestpP i , W q " t, b :" worstpP i , W q, and suppose s ‰ t, b. Then bestpP Òs i , W q " t or s, and worstpP Òs i , W q " b. Likewise, let t :" bestpP Òs i , W q, b :" worstpP Òs i , W q " b, s ‰ t, b. Then bestpP i , W q " t and worstpP i , W q " b or s. If there are at least two elements in the chosen committee and F is strategy-proof, then swapping a third element upward in one preference order leads to a small list of possibilities.
Lemma 3.3. Let F be a committee selection rule satisfying SPO and SPP, F pP q " W , Let s ‰ t, b, F pP iÒs q " W 1 . The following are true: (1) bestpP Òs i , W 1 q " t or s.
Proof. Let a :" bestpP Òs i , W 1 q and suppose a ‰ t, a ‰ s. Suppose a ą i t. By Lemma 3.2, bestpP i , W 1 q " a, and hence voter i has an optimistic manipulation from P to P iÒs . Now suppose a ă i t. By Lemma 3.2, bestpP Òs i , W q " s or t. If it is t, voter i has an optimistic manipulation from P iÒs to P . If it is s then, seeing how t P W , it must be the case that s ą Òs i t ą Òs i a, and we have an optimistic manipulation again. This yields (i).
For (ii), let a :" worstpP Òs i , W 1 q, a ‰ b, s. Suppose a ą i b. By Lemma 3.2, worstpP i , W 1 q " a or s. If it is a, voter i has a pessimistic manipulation from P to P iÒs . If it is s, then we consider two further cases. If s ą i b, we have a pessimistic manipulation from P to P iÒs . If s ă i b, observe the following: (1) s P W 1 , else it could not be the worst element of W 1 under P i .
(2) s ă i b ă i a. In other words, s is at least two positions below a in P i .
(3) worstpP Òs i , W 1 q " a. This gives us a contradiction -s moved up one position from P i to P Òs i so, given 2, s ă Òs i a. Given 1, that s P W 1 , this contradicts 3. In sum, if s ă i b then worstpP Òs i , W 1 q ‰ a. Suppose a ă i b. By Lemma 3.2, worstpP Òs i , W q " b. Voter i has a pessimistic manipulation from P iÒs to P .
Given a strategy-proof rule, swapping a voter's most preferred element of the chosen committee member upward in that voter's order preserves that voter's most and least preferred members of the committee.
Lemma 3.4. Let F be a committee selection rule satisfying SPO and SPP, F pP q " W , bestpP i , W q " s, worstpP i , W q " b.
Proof. Let bestpP Òs i , W 1 q " a, a ‰ s. Suppose a ą i s. By Lemma 3.2, bestpP i , W 1 q " a. Voter i has an optimistic manipulation from P to P iÒs . Suppose a ă i s. By Lemma 3.2, bestpP Òs i , W q " s or s, that is bestpP Òs i , W q " s . Voter i has an optimistic manipulation from P iÒs to P . Let worstpP Òs i , W 1 q " a, a ‰ b. Suppose a ą i b. By Lemma 3.2, worstpP i , W 1 q " a or s. If it is s, observe that if s ‰ b, s ą i b, giving voter i a pessimistic manipulation from P i to P iÒs . It follows that in this case s " b, which satisfies the lemma statement. If it is a, voter i has a pessimistic manipulation from P to P iÒs .
Suppose a ă i b. By Lemma 3.2, worstpP Òs i , W q " b. Voter i has a pessimistic manipulation from P iÒs to P .
Note that the preceding lemmata applied to all committee selection rules. The following applies only to consular election rules. It says that for a strategy-proof rule, swapping a voter's worst element of the elected committee upward in that voter's order does not change the elected committee.
Lemma 3.5. Let F be a consular election rule satisfying SPO and SPP, F pP q " W , bestpP i , W q " t, worstpP i , W q " s.
Let F pP iÒs q " W 1 . It follows that: Voter i has an optimistic manipulation from P to P iÒs .
Suppose a ă i t. By Lemma 3.2, bestpP Òs i , W q " t or s. If it is t, voter i has an optimistic manipulation from P iÒs to P . If it is s, we consider two cases. If it is the case that s ą Òs i a, voter i has an optimistic manipulation from P iÒs to P . If it is the case that s ă Òs i a, note that the assumption that bestpP Òs i , W q " s implies that s ą Òs i t. This is a contradiction as a ă Òs i t. Let worstpP Òs i , W 1 q " a, a ‰ s, t. Suppose a ą i s. By Lemma 3.2, worstpP i , W 1 q " a or s. If it is a, voter i has an optimistic manipulation from P to P iÒs . If it is s, then as |W 1 | " 2 it follows that W 1 " t s, a u. As worstpP Òs i , W 1 q " a, bestpP Òs i , W 1 q " s. Now observe that a ą i s, s ą Òs i a, implies that t is at least two positions above s in P i . This means that t ą Òs i s, and voter i has an optimistic manipulation from P iÒs to P .
Suppose a ă i s. By Lemma 3.2, worstpP Òs i , W q " s, which gives voter i a pessimistic manipulation from P iÒs to P .
3.2. Key monotonicity lemmata. We now show that for a strategy-proof consular election rule, swapping an alternative s upward in some voter's order usually does not change the elected committee, and the only possible change is that s overtakes some committee member and replaces it.
Lemma 3.6 (Upwards monotonicity). Let F be a consular election rule satisfying SPP and SPO.
Let F pP q " t a, b u. Let P 1 i be the ballot obtained from P i by moving s up some number of positions.
If s " a or s " b: uq " s, then by applying Lemma 3.4 repeatedly, we see that no matter how many times we bump s up one position, the winning committee remains unchanged. If worstpP i , t a, b uq " s, then we can apply Lemma 3.5 repeatedly to show that as long as s remains the least favourite element in the set, the winning committee remains unchanged. Once s becomes the favourite element in the set, we can apply Lemma 3.4. Now suppose s is distinct from a and b. By applying Lemma 3.3, we can see that each time we move s up one position, either the two elements in the set remain unchanged, or one of them is replaced by s. In the former case, we get 1 from the lemma statement. In the latter, we get 2. It remains to show that the latter case can only happen if s overtakes the element it supplants from P i to P 1 i .
Suppose, for contradiction, that this is not the case. That is, F pP q " t a, b u, F pP 1 i P´iq " t s, b u and either a ą i s and a ą 1 i s, or s ą i a and s ą 1 i a. First let a ą i s and a ą 1 i s. Suppose worstpP 1 i , t a, b uq " a. By transitivity, worstpP 1 i , t s, b uq " s. As a ą 1 i s, this gives i a pessimistic manipulation from P 1 i to P i . Now suppose bestpP 1 i , t a, b uq " a. It follows that a ą 1 i bestpP 1 i , t s, b uq. This gives i an optimistic manipulation from P 1 i to P i . Now, let s ą i a and s ą 1 i a. Suppose bestpP i , t a, b uq " a. By transitivity, bestpP i , t s, b uq " s. As a ą i s, this gives i an optimistic manipulation from P i to P 1 i . Now suppose worstpP i , t a, b uq " a. It follows that worstpP i , t s, b uq ą i a. This gives i a pessimistic manipulation from P i to P 1 i . As such, SPP and SPO prevents the possibility of s entering the winning committee without overtaking the element it replaces. As such, 2 can only happen if the overtaking takes place.
Corollary 3.7. Let F be a weakly viable consular election rule satisfying SPP and SPO. Then F is unanimous.
Proof. Let a P A. By weak viability there is some profile P with a P F pP . By Lemma 3.6, if we swap a to the top of all voters' preference orders, the elected committee does not change.
Similarly, if we move s downward in some voter's order, s may be replaced on the committee by an alternative that overtook it, and otherwise there is no change to the committee.
Lemma 3.8 (Downwards monotonicity). Let F be a consular election rule satisfying SPP and SPO.
Let F pP q " t a, b u. Let P 1 i be the ballot obtained from P i by moving s down some number of positions.
If s ‰ a, b: Proof. If s ‰ a, b, then observe that if s moves down the ballot from P i to P 1 i , then it moves up the ballot from P 1 i to P i . By upwards monotonicity, either F pP q " F pP 1 i P´iq or s P F pP q. As s R t a, b u, it follows that F pP q " F pP 1 i P´iq. If s " a, we consider four possibilities for F pP i P´iq: In case 1, we start at P i P´i and move s up the ballot. By upwards monotonicity, we find that F pP q " F pP i P´iq.
In case 2, we start at P i P´i and move s up the ballot. By upwards monotonicity, if s P F pP q then it can only enter after it overtakes the element it replaces. As F pP q " t s, b u, it follows that s enters after it overtakes c, and as a consequence F pP i P´iq " t b, c u only if s drops below c as we move from P i to P 1 i . In case 3, by upwards monotonicity F pP q " t s, c u. As such, case 3 cannot occur. In case 4, by upwards monotonicity F pP q is one of t c, d u, t s, c u or t s, d u. As it is none of these, case 4 cannot occur.

Strategy-Proofness and Reducible elections
4.1. Two classic impossibilities. We first state the classic result in the area, for committees of size 1.
Duggan and Schwarz proved an analogue of this for variable sized committees. In fact they give two rather different-looking versions in Schwartz [1992, 2000]. Taylor [2002] gave a more readable presentation which has been widely described as the "Duggan-Schwartz Theorem", and we use this version.
Theorem 4.2. Let F be a committee selection rule that satisfies SPP, SPO and is onto with respect to singletons. That is, for every a P A there exists a P such that F pP q " t a u. Then for |A| ě 3, F has a weak dictator.
We aim to extend this last result to the case of consular election rules, replacing being onto for singletons with weak viability. This work will not be as straightforward as expected, and will take until Section 6 to complete. We first deal with some annoying trivialities.
4.2. The case of Marius. One might, in light of the Duggan-Schwartz theorem, assume that the Gibbard-Satterthwaite theorem can be extended directly extended to committee selection rules: with |A| ě 3, a weakly viable committee selection rule satisfying SPP and SPO has a dictator of some sort. However, it is not difficult to construct a counterexample.  Proof. Majority vote on the second consul with lexicographic tie-breaking.
Of course, what is going on here is that even though three alternatives are present, only two sets are in the range of the function. If we increase the number of alternatives to four, and hence the size of the range to three, we recover a form of dictatoriality.
Proposition 4.5. If |A| ě 4, every Marian consular election rule that satisfies SPO, SPP and weak viability has a weak dictator.
Proof. Let m be Marius. Consider the social choice function F 1 : PpV, Azt m uq Ñ Azt m u such that F 1 pP q " a where a P F pP˚q, a ‰ m. P˚is obtained from P by ranking m last in every ballot. Once we establish the following we can invoke the Gibbard-Sattherwaite theorem: (1) |Azt m u| ě 3.
For 3, assume there is a P P PpN, Azt m uq such that there is some P i for which F 1 pP q " a ă i F 1 pP i P´iq " b. Extend P to P˚by ranking m last in every ballot. It follows that F pP˚q " t a, m u and F ppP i P´iq˚q " t b, m u, giving voter i an optimistic manipulation. The reader will note that the above proof only used the SPP assumption. It could likewise be rewritten to only use SPO. This should not be surprising as Marian election rules are, essentially, social choice functions in disguise, and manipulating a singleton by an optimist or a pessimist is the same thing.
We have earlier shown that strategy-proof consular election rules are unanimous. With the further assumption that they are non-Marian, we can show that they satisfy veto.
Fact 4.6. Let F be a non-Marian, weakly viable consular election rule satisfying SPP and SPO. Then F satisfies veto.
Proof. Let P be any profile where a loses. Such a profile must exist because F is non-Marian. Once a is moved to the bottom of every ballot it still loses by monotonicity.
4.3. The general case. Marian election rules are a special case of a more general class of elections.
Definition 4.7. A k-committee selection rule F is said to be reducible if there exists an integer j and a partition of A into two sets, A " B Z C, such that F pP q " GpP |Bq Y HpP |Cq for a j-committee selection rule G : PpV, Bq Ñ S j pBq and a pk´jq-committee selection rule H : PpV, Cq Ñ S k´j pCq.
Note that in many cases this is an entirely natural way to select a committee -we might want a committee formed of a fixed number of men and women, plebeians and patricians, Lords Temporal and Lords Spiritual. However, from a formal point of view these are not very interesting; a reducible k-committee selection rule is not, in some sense, a "true" k-committee selection rule, and it does not add anything to the theory. Reducible rules also complicate any attempt to gracefully extend the Duggan-Schwartz theorem.
Fact 4.8. There exist non-Marian consular election rules with |A| " 4 that satisfy SPP, SPO and weak viability and do not have a weak dictator.
Proof. Divide A into two halves and have majority voting on each.
It is true that for |A| ě 5 every reducible, strategy-proof and viable consular election rule has a "partial" dictator, as the Gibbard-Satterthwaite theorem ensures that one of the two social choice functions must be dictatorial. However, it will not have a weak dictator over the entire domain unless the same voter is the dictator of both social choice functions. Thus, in a very boring sense, the Duggan-Schwartz theorem fails. We can have committee selection rules that are both strategy-proof and non-dictatorial.
It is worth noting that a reducible consular election rule is strategy-proof in the Duggan-Schwartz sense precisely when the component functions are strategy-proof in the classical sense.
Proposition 4.9. Let F be a consular election rule that is reducible to social choice functions G and H. Then F satisfies SPP and SPO if and only if G and H are strategy-proof.
Proof. Let B Z C " A, F pP q " GpP |Bq Y HpP |Cq.
Suppose F satisfies SPP and SPO, and let voter i have a profitable deviation from Q i to Q 1 i in G. That is, GpQ i Q´iq " a, GpQ 1 i Q´iq " b and b ą i a. Let P be any profile whatsoever over A for which P |B " Q. Observe that F pP q " t a, x u, for some x P C. Modify P into R by moving all the alternatives in B to the top of the ballots, without changing the order within B and C. Applying Lemma 3.6 we see that F pRq " F pP q -a remains a winning alternative because no alternative overtakes it, so the only way the winning committee can change is if some y P B replaces x, but F pRq " t a, y u is impossible because one element of F pRq must come from B and one from C, and a already comes from B. Now consider what happens when voter i deviates from R i to R 1 i with the property that R 1 i |B " Q 1 and R 1 i |C " R i |C. Since R 1 i |B " Q 1 , G must elect b, and R 1 i |C " R i |C implies H still elects x. Thus F pR 1 i R´iq " t b, x u. If b ą i x, this is an optimistic manipulation, and if x ą i b, this is a pessimistic manipulation, neither of which can take place.
For the other direction, suppose G and H are strategy-proof. The only possible functions these could be are dictatorship, imposed rule, and majority voting between two alternatives. It is easy to see that a disjoint union of any of these cannot be manipulated by either an optimist or a pessimist.

The range of an election
Our quest for an impossibility result has had a rocky start. Marian elections only obtain a weak dictator with at least four alternatives, and reducible elections in general need at least five alternatives for an even weaker notion of a partial dictator.
In response to this, we can argue that so far we have only considered a somewhat degenerate class of committee selection rules -sure, we can obtain a consular election rule by gluing two social choice functions together, and in some cases it may even be natural to do so, but the behaviour of such an election is determined entirely by the behaviour of its components, and studying it sheds no light on the mathematics of selecting a committee in general. What we would like to do is to understand elections that are not reducible.
Intuitively, reducible rules occur because their range does not cover sufficiently many possible committees. It is clear that, for |A| ě 3, an onto rule is irreducible. It would have been nice had this been the end of the story -perhaps the combination of strategy-proofness, viability and irreducibility are sufficiently strong conditions to force every committee to be viable?
We start with a counterexample.
Fact 5.1. There exist irreducible consular election rules satisfying SPP, SPO and weak viability that are not onto.
Proof. Let A " t a, b, c, d u, |V | " 1. Have F behave as follows: (1) If the voter's first two choices are t a, b u, t a, c u, t b, c u or t b, d u, the voter gets his first two choices.
(2) If the voter's first two choices are t a, d u, he gets his first and third choice.
For intuition, suppose t b, c u are apples, t a, d u oranges, and the voter is asked to pick a pair that contains at least one apple.
The rule F clearly satisfies weak viability. To see that it is strategy-proof, observe that the only potentially manipulable profiles involve the voter ranking a first and d second, or d first and a second -in every other case the voter already gets his top two choices elected.
Without loss of generality, suppose the voter's preference order is a ą 1 d ą 1 b ą 1 c. The current election outcome is t a, b u. The voter cannot manipulate optimistically, because he already gets his top choice elected. The only member of S 2 pAq that is pessimistically preferred to t a, b u is t a, d u, and that is not in the range of the election, so the voter cannot manipulate pessimistically either.
Corollary 5.2. There exist irreducible consular election rules satisfying SPP, SPO and weak viability that do not have a strong dictator.
It turns out, then, that the range of a strategy-proof election can be a non-trivial affair, and we need to understand this range if we are to have any hope of determining how these elections behave.
The key observation in this section is that the range of a consular election rule can be visualised as a graph, with the alternatives playing the role of vertices and an edge existing between a and b if and only if t a, b u is a committee in the range of the funcion.
Definition 5.3. The range graph of a consular election rule F , GpF q, is a graph with vertex set A and edge set RangepF q.
Fact 5.4. Let F be a consular election rule. Then F is weakly viable if and only if GpF q has no isolated vertices, and F is onto if and only if GpF q is a complete graph.
Reducible elections are easily interpreted in this setting.
Fact 5.5. If F is reducible then GpF q is bipartite. If GpF q is bipartite and F satisfies SPP and SPO, then F is reducible.
Proof. The first is obvious -A can be partitioned into B and C such that social choice functions G and H select elements from B and C respectively. As such, there can be no edge within B or within C.
For the second part, let B and C, B Z C " A, partition A into the two halves of GpF q. Define G : P|B Ñ B to be the following social choice function: where P C is obtained from P by appending the elements from C in lexicographic order at the end of every ballot in P . That is, G completes a profile over B into a profile over A by adding C at the end of the ballots, computes F , and returns the element of B chosen by F . Define H : P|C Ñ C analogously. We claim that : F pP q " t GpP |Bq, HpP |Cq u.
Suppose, for contradiction, that there exists a P such that F pP q ‰ t GpP |Bq, HpP |Cq u. Without loss of generality, let G be the culprit. That is, F pP q " t x P B, y P C u, x ‰ GpP |Bq. Modify P by moving the elements in C until they are at the bottom of every ballot, in lexicographical order. By monotonocity, this should only change y. However, now we have a profile that must force F to agree with G.
Corollary 5.6. Let F satisfy SPP and SPO. Then F is reducible if and only if GpF q is bipartite.
Example 5.7. In general (without strategy-proofness) F can be irreducible and GpF q bipartite. Consider F with A " t a, b, c, d u and one voter, defined as follows: (1) If the voter prefers c to d, then a is on the committee. Else, b is on the committee.
(2) If the voter prefers a to b, then c is on the committee. Else, d is on the committee. The possible committees are t a, c u, t a, d u, t b, c u and t b, d u. As such, GpF q is bipartite. However, F is irreducible -the decision on whether to include a on the committee is contingent on the relative ranking of c and d, so there can be no G : PpV, t a, b uq Ñ t a, b u that makes the decision.
Fact 5.8. Let F be a weakly viable reducible consular election rule satisfying SPP and SPO. Then GpF q is a complete bipartite graph.
Proof. Let A " B Z C, the two halves of a bipartite graph. Suppose for contradiction that there exist x P B, y P C such that x and y are not isolated, but px, yq R GpF q. Let F pP q " t x, z u. Move y to the top of each ballot. By unanimity, y must be a winner. By reducibility, it must replace z.
Corollary 5.9. Let F be a weakly viable reducible consular election rule satisfying SPP and SPO. Then F is a Marian election if and only if GpF q is acyclic.
Proof. Irreducible elections are non-bipartite, hence they contain an odd cycle. The only complete bipartite graph that is acyclic is a tree of depth 1. Now that we know what the range of a reducible election looks like, we of course know exactly what the strategy-proof irreducible elections are: simply those F for which GpF q has an odd cycle. This does not give us a lot to work with, so we must look further. The proof above relied on the fact that strategy-proof elections are unanimous, which allows us to prove that certain edges in the range graph must exist by considering the profiles where all voters rank some alternative first. Rather than using strategy-proofness in an ad-hoc way through this section, we can use it to prove a much stronger property about the range graphs of strategy-proof elections.
Definition 5.10. We say a graph G satisfies edge-connectivity if, whenever t a, b u and t c, d u are non-incident edges, we have: (1) t a, c u or t a, d u is an edge.
(2) t b, c u or t b, d u is an edge. Note that the relation is symmetric. Namely, if t a, b u and t c, d u are non-incident edges, then so are t c, d u and t a, b u. Thus, edge connectivity also implies that: (1) t a, c u or t b, c u is an edge.
(2) t a, d u or t b, d u is an edge. It is easier to visualise what this property entails by observing that a graph is edge-connected if and only if it does not contain any of the following as induced subgraphs: Example 5.11. The Lex Licinia Sextia was a series of laws passed in 367 BC to address the disproportionate dominance patricians enjoyed in the Roman state. Under the new laws at least one of the two consuls of the Roman republic was required to be plebeian. Thus the valid configurations of the consulship were: a patrician and a plebeian, or two plebs (Jupiter forbid). The range graph of this election would thus consist of a clique X of plebeians, and a totally disconnected set Y of patricians with the property that: for x P X and y P Y , t x, y u is an edge. This graph satisfies edge-connectivity. Other families of edge-connected graphs include the complete and complete bipartite graphs. In Fig. 1 we illustrate all the edge-connected graphs of orders 4, 5 and 6 that are neither complete nor bipartite. This includes the plebeian/patrician family as well as others.
Edge-connectivity is not merely a consequence of strategy-proofness, it is the closest we can get to a characterisation of the property if we focus on the range of an election alone. Crucial to this is the fact that if the range of an election is edge-connected, then any given voter will be able to identify a unique "best" committee: a pair which is neither pessimistically nor optimistically dominated by any other pair in the range.
Definition 5.12. Consider an X Ď S 2 pAq, and a voter i. Voter i's favourite committee in X, if it exists, is an element that is maximal under ľ P i and ľ O i over X. Proposition 5.13. Suppose GpF q is edge-connected. Then each voter has a unique favourite committee in GpF q.
Proof. Let G be an edge-connected graph with at least one edge. Consider a voter i with preferences P i , and the induced optimistic and pessimistic orders ľ O i and ľ P i . Let t a, b u be a maximal element under ľ O i . Without loss of generality, suppose a ą i b. We will show that one of the following is true: Figure 1. All edge-connected graphs of orders 4, 5 and 6 that are neither complete nor bipartite.
(1) t a, b u is maximal under ľ P i , or (2) There exists a t a, c u such that t a, c u ą P i t a, b u and t a, c u is maximal under ľ O i . Since the graph in question is finite, repeatedly applying 2 will eventually yield us 1 -the existence of an element maximal in both orders.
Suppose t a, b u is not maximal under ľ P i . There must exist some X ą P i t a, b u. If X is of the form t a, c u, we are done. Suppose X " t c, d u, for c, d distinct from a. Observe that this implies that c, d ą i b. We have assumed that t a, b u and t c, d u are both edges. By edge-connectivity, either t a, c u or t a, d u is an edge, and both of these pessimistically dominate t a, b u.
This establishes that there exists a t a, b u that is maximal in both the pessimistic and the optimistic order. To see that it is unique, observe simply that an edge maximal optimistically must include a, else t a, b u would dominate, and likewise an edge maximal pessimistically must include b.
Edge-connectedness is strongly connected to strategy-proofness for consular election rules.
Proposition 5.14. If F satisfies SPP and SPO then GpF q satisfies edge-connectivity. Conversely if G is a graph with at least one edge that satisfies edge-connectivity, then there exists an F satisfying SPP and SPO such that GpF q " G.
Proof. To show that strategy-proofness implies edge-connectivity, take an F satisfying SPP and SPO and let F pP q " t a, b u. Let t c, d u be in the range of F . Move c to the top of P . By unanimity and upwards monotonicity, F pP q " t a, c u or t b, c u. Repeat for d.
For the other direction, given an edge-connected G, fix a voter i and let F be the function that gives i the unique edge of G that is maximal under both ľ P i and ľ O i . First, observe that GpF q " G -given an edge t a, b u, construct a profile P where i ranks a and b first. F pP q " t a, b u, so the range of F is precisely the edges of G. That F satisfies SPP and SPO follows from the fact that the i is getting his favourite committee -an element maximal under both the pessimistic and the optimistic order -from which no manipulation is possible.
Corollary 5.15. Let F be a consular election rule satisfying SPP and SPO. Then each voter has a unique favourite committee in GpF q.
Corollary 5.16. Let F be a consular election satisfying weak viability, SPP and SPO. GpF q has diameter 2.
Proof. Let a and b be arbitrary vertices in GpF q. By weak viability, there exist vertices c and d, not necessarily distinct, for which t a, c u and t b, d u are edges. If c " b or d " a, then the distance between a and b is one. If c " d, then the distance between a and b is at most two.
Suppose then that c and d are distinct from a, b, and each other. By edge-connectivity, at least one of t a, b u and t a, d u must be an edge. If it is t a, b u, the distance between a and b is one. If it is t a, d u, then the distance between a and b is at most two.
Naturally, this introduces a new notion of dictatorship: Definition 5.17. A range dictator is a voter such that for every profile, that voter's favourite committee is elected.
Under the assumption of weak viability, a range dictator is a stronger notion than a weak dictator, and collapses to a strong dictator in the case of an onto election.
Edge-connectivity is a very strong property, and it allows us to use the fact that an irreducible election has an odd cycle to prove a much stronger statement about its structure.
Fact 5.18. If F is irreducible, SPP, SPO and weakly viable then every vertex in GpF q belongs to a 3-cycle.
Proof. GpF q is not bipartite, so an odd length cycle exists. Suppose the smallest such cycle is of length 2k`1, k ą 1. Let t a, b u, t b, c u, t c, d u be edges of this cycle. By Proposition 5.14 either t a, d u or t b, d u is an edge. If it is t a, d u, then we have a 2k´1 cycle by replacing t a, b u, t b, c u, t c, d u with t a, d u. If it is t b, d u, then we have a 3-cycle t b, c u, t c, d u, t b, d u. Either way, 2k`1 is not the smallest length of an odd cycle.
Given that a 3-cycle exists, assume there exists an a that does not belong to a 3-cycle. By connectivity (diameter 2), we can choose a such that a is adjacent to b, and b, c, d is a 3-cycle. Let F pP q " t c, d u. Move a to the top of the ballots. The winner is either t a, c u or t a, d u, giving the 3-cycle pa, b, cq or pa, b, dq.
This leads to the following corollary, which will prove crucial in the proof of Proposition 6.11.
Corollary 5.19. Let F be an irreducible election satisfying SPP, SPO and weak viability. If a and b are connected by an edge, they also form a 3-cycle with some c.
Proof. By Fact 5.18, a belongs to some 3-cycle. If this cycle contains b, we are done. Else, let this cycle be pa, c 1 , c 2 q. By edge connectivity, either t b, c 1 u or t b, c 2 u is an edge, so that pb, c 1 , aq or pb, c 2 , aq is a cycle.

Irreducible elections and linked domains
We are finally in a position to state exactly what we are trying to prove: an irreducible consular election rule that is manipulable by neither an optimist nor a pessimist has a range dictator. We do not even have to assume that |A| ě 3 -the only consular election rule over two alternatives is both reducible and dictatorial.
While a direct proof of the theorem is possible using the standard techniques of social choice theory, a shorter and more elegant solution involves following the footsteps ofÖzyurt and Sanver [2008] and Reffgen [2011] by using a theorem of Aswal et al. [2003]. We define an extension from preferences over A to preferences over S 2 pAq, and apply the result of Aswal et al. [2003] to show that the resulting social choice function is dictatorial.
Definition 6.1. Let D be a domain of linear orders. Two alternatives, a, b P A, are connected in D if there exist P, P 1 P D such that in P , a is ranked first and b second, while in P 1 , b is ranked first, and a second.
Definition 6.2. A domain D is said to be linked if it is possible to order A " t a 1 , . . . , a m u in a way that: (1) a 1 is connected to a 2 .
(2) For i ě 3, a i is connected to at least two elements in t a 1 , . . . , a i´1 u.
Theorem 6.3 (Aswal et al. [2003]). Let D be a linked domain of preferences over A, |A| ě 3, and F : D n Ñ A be a unanimous social choice function. Then F is strategy-proof if and only if F is dictatorial.
The plan is, given an F : PpV, Aq Ñ S 2 pAq, to define an extension map α that transforms a linear order over A into a linear order over S 2 pAq. We then define the social choice function F : αpPpV, Aqq Ñ S 2 pAq by FpαpP qq " F pP q. If we show that αpPpV, Aqq is linked and F is unanimous, we can invoke Theorem 6.3 to show that F is dictatorial. Since F mirrors the output of F , this must mean that F is dictatorial as well -provided, of course, that α is defined in a way voter i's first choice in αpP i q corresponds to voter i's favourite committee in S 2 pAq.
The first issue we face is in extending the preferences. As we have previously argued, Duggan-Schwartz manipulation, which can be expressed as ą O i Y ą P i , does not define a transitive order. 2 What we can do instead is to compose the two lexicographically. That is, define ľ L i by: 2 Among other problems. If we take ą O i Y ą P i to represent a voter's strict preferences, we have to posit that a voter is able to at once strictly prefer X to Y and Y to X -what is sometimes known as conflicted preferences in the literature.
That is, the voter ranks committees by the best element first, and then uses the worst element as a tie-breaker. This clearly yields a linear order.
Of course, manipulation by ľ L i is not the same thing as manipulation by an optimist or a pessimist. However, in the case of a consular election rule, lexicographic manipulation is a strictly narrower notion. As a consequence, a function that satisfies SPP and SPO also satisfies ľ L istrategy-proofness. If we thus show that ľ L i -strategy-proofness is enough to ensure dictatoriality, we will a fortiori show that elections that satisfy SPP and SPO are dictatorial.
Fact 6.4. A consular election rule F is ą L i -strategy-proof only if it satisfies SPP and SPO. Our next problem is that, in general, F is not going to be unanimous -unanimity would imply that F is onto, and we have argued that many natural irreducible elections fail that property. To address this, we will consider the restriction of F to the relevant committees.
Definition 6.5. Let F : PpV, Aq Ñ S 2 pAq be a weakly viable consular election rule satisfying SPP and SPO, and let F : αpPpV, Aqq Ñ S 2 pAq be the induced social choice function.
At first glance, F 1 may appear ill-defined: there may exist αpP q ‰ αpP 1 q such that αpP q|GpF q " αpP 1 q|GpF q. However, this is not the case -αpP q is the lexicographic order over pairs defined by the linear orders in P . As such, no matter how many pairs we remove from αpP q to obtain αpP q|GpF q, there remains a unique way to reconstruct the order.
Example 6.6. The dense notation of the above statement can hide the fact that we are talking about a very simple operation. Let F be the function from Fact 5.1 -one voter is asked to pick a pair from t a, b, c, d u, at least one element of which is from t b, c u.
Consider a voter with preference a ą 1 d ą 1 b ą 1 c. The extension α turns his preferences into: The function F is then the function that gives voter 1 his first choice, unless it happens to be t a, d u, in which case it gives him his second choice. F is not unanimous, as it is not onto, and unsurprisingly F is not dictatorial. The graph GpF q does not include t a, d u as an edge. If we restrict voter 1's preferences to GpF q, then we get αpP q|GpF q: t a, b u ą 1 t a, c u ą 1 t b, d u ą 1 t c, d u ą 1 t b, c u. Now, F 1 is simply the function that gives voter 1 his first choice. This function is unanimous and dictatorial.
That the function in the example above is unanimous is not an accident.
Lemma 6.7. Let F be a consular election satisfying SPP and SPO. Then voter i's first choice in αpP i q|GpF q is his favourite committee.
Proof. Let t a, b u be voter i's first choice in αpP i q|GpF q. Recall that the favourite committee is an element maximal under both ľ O i and ľ P i . That the t a, b u is maximal under ľ O i is obviousľ L i ranks pairs by the best element first. Without loss of generality, let the best element be a. In Proposition 5.13, we have established that voter i has a unique favourite committee in GpF q. In order to be maximal under ľ O i , the favourite committee must contain a. However, it cannot be some t a, c ‰ b u; if b ą i c, then the favourite committee is not maximal under ľ P i , and if c ą i b then t a, b u is not the first choice in αpP i q|GpF q. Thus the favourite committee and the first choice in αpP i q|GpF q must coincide.
Lemma 6.8. Let F be a consular election satisfying SPP, SPO. The pair t a, b u is elected whenever t a, b u is the favourite committee of every voter.
Proof. By Proposition 5.13, t a, b u is in the range of F . Let P 1 be a profile such that F pP 1 q " t a, b u. Move a and b to the top of every ballot. By monotonicity, the winning committee is still t a, b u. Now move the other alternatives, voter by voter, to the positions they occupy in P . By monotonicity, if the winning committee changes during this process then that must mean some c overtook, without loss of generality, a and the winning committee became t b, c u. However, this must mean that some voter prefers t b, c u to t a, b u, which contradicts t a, b u being the favourite committee.
We now have a unanimous function. We next consider whether its domain is linked. The graph interpretation is of use here, as it turns out that connected committees are exactly the incident edges.
Lemma 6.10. Let F : PpV, Aq Ñ S 2 pAq be a weakly viable consular election rule satisfying SPP and SPO. Then two committees, X, Y P S 2 pAq, X ‰ Y , are connected in αpPpV, Aqq|GpF q if and only if the edges X and Y are incident in GpF q.
Proof. Let X " t a, b u and Y " t b, c u. Let P be a linear order ranking b ą a ą c ą . . . and P 1 ranking b ą c ą a ą . . . . Recall that αpP q|GpF q is the lexicographic order ľ L i . The first element is clearly t a, b u and the second t b, c u. Likewise for αpP 1 q|GpF q, the first element is t b, c u and the second t a, b u. Now suppose X " t a, b u and Y " t c, d u, all a, b, c, d distinct. Let P be any preference order for which the first element in αpP q|GpF q is t a, b u. As αpP q|GpF q is the lexicographic order, either a or b have to be ranked first. Without loss of generality, let it be a. Obseve that one of the following must be true: (1) The second element in αpP q|GpF q is t a, e u for some e.
(2) t a, b u is the only edge in GpF q incident on a. If the first is true, t c, d u cannot be ranked second, and hence X and Y cannot be connected. If the second is true, we violate edge connectivityt a, b u and t c, d u are both edges, so either t a, c u or t a, d u must be an edge.
Proposition 6.11. Let F : PpV, Aq Ñ S 2 pAq be an irreducible, weakly viable consular election rule satisfying SPP and SPO. Then αpPpV, Aqq|GpF q is linked.
Proof. Applying Lemma 6.10 to Definition 6.2, we want to show that it is possible to order the edges X 1 , . . . , X q of GpF q in a way that: (1) X 1 is incident on X 2 .
(2) For i ě 3, X i is incident on at least two elements of t X 1 , . . . , X i´1 u. To obtain 1, observe that irreducibility implies |A| ě 3, and weak viability implies that no vertex is isolated. To connect three vertices we need at least two edges, call them t a, b u and t c, d u. If a, b, c, d are not distinct, the two edges are incident. If a, b, c, d are distinct, edge connectivity implies either t a, c u or t a, d u is an edge, both of which are incident on t a, b u.
To obtain 2, we will demonstrate that given a set of edges I Ă GpF q which satisfies the property that every that every e P I is incident on at least one other member of I (i.e. I has no isolated edges). we can find a e 1 R I such that e 1 is incident on at least two members of I. The reader will note that this means that I Y t e 1 u also satisfies the property that every e P I Y t e 1 u is incident on at least one other member of I Y t e 1 u. As such, starting with a set of two incident edges, it is possible to continually add edges until the entire graph is shown to satisfy 2.
Let I be such a set. As the graph is connected, there must exist a t x, y u R I such that t x, y u is incident on I. Without loss of generality, suppose x belongs to an edge in I. If y also belongs to an edge in I we are donet x, y u is incident on t x, v u and t y, w u for some t x, v u, t y, w u P I. Suppose then that y does not belong to an edge in I.
Let t x, w u be an edge in I. Recall that t x, w u is incident on at least one member of I. If that member is t x, v u, we are donet x, y u is incident on t x, w u and t x, v u, and we can add it to I. If that member is t v, w u, we can visualise the situation as follows, taking the vertices at the top to belong to I.
x v w y By Corollary 5.19, there exists a z such that t x, z u and t y, z u are both edges. If z " v we are donet y, v u is incident on two edges in I, so we can add it to the set. If z ‰ v belongs to an edge in I we are also done, as t x, y u is incident on t x, z u and t x, v u. Suppose then that z does not belong to an edge in I.
x v w y z If no other edges are present, this is a forbidden induced subgraph. We must posit that either t y, v u or t v, z u is an edge. If it is t y, v u, we can add t y, v u, incident on t x, v u and t v, w u, to I. If it is t v, z u, we can add t v, z u, incident on t x, z u and t x, v u, to I. Either way we increase the size of I.
We finally achieve the promised main result.
Proof. By Proposition 6.11 the domain is linked, and by Corollary 6.9 the function is unanimous. We can apply Theorem 6.3.
As a sanity check, we can verify that Marian elections also have a linked domain, whereas non-Marian reducible elections do not.
Proposition 6.13. Let F : PpV, Aq Ñ S 2 pAq be a Marian, weakly viable consular election rule satisfying SPP and SPO. Then αpPpV, Aqq|GpF q is linked.
Proof. Every edge is incident on each other. This gives us Proposition 4.5.
Corollary 6.14. For |A| ě 4, a Marian, weakly viable election satisfying SPP and SPO has a weak/range dictator (the two notions coincide).
Proof. For |A| ě 4, the range graph of the election has at least three edges. This means that αpPpV, Aqq|GpF q is a linked domain over the set of alternatives S 2 pAq|GpF q, with |S 2 pAq|GpF q| ě 3, so we can invoke Theorem 6.3.
Proposition 6.15. Let F : PpV, Aq Ñ S 2 pAq be a non-Marian, reducible, weakly viable consular election rule satisfying SPP and SPO. Then αpPpV, Aqq|GpF q is not linked.
Proof. Recall that GpF q is a complete bipartite graph that is not acyclic (i.e., not a star graph). Let X 1 " t a, b u and X 2 " t a, c u be any two incident edges. Let V 1 and V 2 be the two halves of GpF q, a P V 1 and b, c P V 2 . Observe that the only way to expand t X 1 , X 2 u consistent with Definition 6.2 is to add some t a, d u to the set. As GpF q is not a star graph, by doing so we can never cover the entire graph.

Summary
We have demonstrated that the condition of weak viability allows for the existence of non-trivial structure in the range of an election, which we have visualised as a property of the resulting range graphs.
For reducible elections, we have shown the following: ‚ If the election is Marian, for |A| ě 4 a range dictator exists. ‚ If the election is non-Marian then a dictator may not exist. However, for |A| ě 5 a "partial dictator" exists, in the sense that some voter can unilaterally decide which element of B Ă A is present on the winning committee.
For irreducible elections we have a dictatoriality result: ‚ For |A| ě 4, a range dictator exists.
7.1.1. Extending the results. According to Livy, the last king of Rome was overthrown in 509 BC by a body of citizens led by Lucius Junius Brutus. The first act of Brutus after the expulsion of the king was to have the people swear an oath to never let a single man govern Rome. It is on this basis that the Romans justified the duplication of the post of consul and other key positions in government. Like most Roman political experiments, this one eventually ended in failure. Two is not a good number in government. Any disagreement results in an even split, which means that to avoid political deadlock, elaborate schemes of power sharing need to be devised. One such scheme used by the Romans involved the consuls commanding the army on alternating days -this led to the farcical prelude to the Battle of Cannae where Varro ordered the army to advance during his days of command, and Paullus held it back during his. The purpose of this historical aside is to suggest that while the case of k " 2 raises many interesting issues, it should nevertheless be seen as a stepping stone to studying larger committee sizes, rather than an end in itself.
The argument as presented here fails to generalise fairly quickly -Lemma 3.5 already relies on the fact that the winning committee is of size two. Without Lemma 3.5 there is no monotonicity, and without monotonicity there is nothing to be said. Admittedly, we did not spend a great deal of time attempting to generalise these lemmas to arbitrary k, and intuitively we suspect some version of monotonicity for general committee selection rules should not be too difficult to establish. The more serious issue arises when dealing with the range of such elections. In the case of k " 2, we were abetted greatly by the fact that we could visualise the range of an election as a graph, and use results and intuitions from graph theory to guide us along. To replicate this approach in the case of k " 3 would require us to either consider a hypergraph, or to index a range graph by the perspective of a voter, adding an edge between the best and worst alternative of every committee. It is unclear that either of these approaches will give us the insights we need, nor is there any a priori reason to believe that in such a context voters would still have a favourite committee, without which a range dictator is ill-defined. The case of variable size committees is even worse: now the hypergraph is not even uniform. Moreover, in the case of fixed k-committees we could potentially side step the issue and study onto rules only; such a result would be interesting enough in itself. In the case of variable size committees the onto case is trivialised by the Duggan-Schwartz theorem, so tackling the range of the election is unavoidable.
The specific technique used in Proposition 6.11 is also particular to the case k " 2 -in this case the lexicographic order we defined is strictly narrower than Duggan-Schwartz manipulation and hence a dictatoriality result for the former implies, a fortiori, the latter. This is no longer the case with k " 3. A voter with preferences a ą 1 b ą 1 c ą 1 d ą 1 e has a pessimistic manipulation from t a, b, e u to t a, c, d u but no lexicographic manipulation; and a lexicographic manipulation from t a, c, d u to t a, b, d u even though pessimistically he is worse off. However, we suspect this difficulty to be less serious than the issue of the range. 7.1.2. Committees of arbitrary size. In recent years, social choice correspondences have reappeared in the literature under a number of names: multi-winner voting rules [Meir et al., 2008], resolute social choice correspondences [Özyurt and Sanver, 2008], irresolute voting rules [Moulin et al., 2016], social dichotomy rules [Duddy et al., 2014]. Mathematically, these are the same concepta function that takes a tuple of preference orders over A to a non-empty subset of A. What is different is the interpretation. In classical social choice theory, alternatives are taken to mean mutually exclusive states of the world. A social choice correspondence, then, could take the economic needs of a population to a set of compatible equilibria, or a nation's political preferences to a shortlist of presidential candidates, with the assumption that some tie-breaking procedure will pick one, and only one, of these alternatives at a later date. However, the same mathematical formalism can be used to study an algorithm which aggregates film rankings to produce a library for an aeroplane's entertainment system, or an election that directly picks members of parliament, in which case the outcome of the function is the final result for society, and not a tie to be resolved in the future.
In this paper we have dealt with the special case of rules which must output a committee of fixed size. If we relax this to allow committees of arbitrary size, then all the impossibility results established for social choice correspondences apply. However, the assumptions underlying these results may be inappropriate for the given interpretation. In particular, the viability assumptions of the Duggan-Schwartz theorem, requiring that a correspondence be onto with respect to singletons, may be unjustifiably strong -there is no a priori reason to privilege singletons over any other committee size. For example, imagine a situation where certain singletons are allowed and others are not -in a catering scenario it might be the case that a menu consisting of a vegetarian option only is acceptable, but meat only is not. Thus there may still be room in the literature for a new strategy-proofness result applicable to the committee interpretation, with more natural assumptions. 7.1.3. Manipulation model. The assumptions of the Duggan-Schwartz theorem make the most sense in the context of a social choice function that generally elects singletons, but occasionally produces a tie which is broken in a non-deterministic manner. In this setting the requirement that the function be onto with respect to singletons is a natural analogue of a social choice; the fact that the value of a committee is assessed only by the individual values of the alternatives on that committee makes sense because after the tie-breaking mechanism is invoked only one alternative will be selected; and the optimistic and pessimistic preference orderings used, while extreme, are nevertheless natural ways to assess the outcome of the tie.
In the case of a committee selection rule sets do not represent ties to be resolved, but the final outcome of the election process. Given that the committee is intended to govern together, assessing its value by the value of its individual members is no longer appropriate, as we need to consider the externalities the members impose on each other -Octavian and Mark Antony individually were the most respected men in Rome, but governing together their power struggle tore apart the republic. Finally, assessing a committee by the min and the max introduces additional problems in this setting. For instance, under a multiwinner election rule a voter with min/max preferences will strictly prefer the committee t a u over every other committee in which a is the best element, but it is not difficult to think of a context where larger committees are more beneficial by virtue of being large.
Throughout this paper we have replaced the requirement that a social correspondence be onto singletons with weak viability. Weak viability appears to be the appropriate notion in this setting; anything weaker would imply that there exists an a that does not feature on any winning committee, and under the assumptions of strategy-proofness such an a would not affect the outcome of any election. A stronger notion is unnecessary as weak viability is sufficient to obtain a dictatoriality result.
The fact that we continue to evaluate committees solely on the basis of the committee's members is the greatest weakness of this paper, but this weakness is unavoidable in the setting of a committee selection rule as established in the literature: the input to our function is a profile of linear orders over alternatives. We simply have no way to distinguish between a voter that ranks a first, b second, and feels that a and b would make a great pairing, and a voter that ranks a first, b second, but would never want to see the two elected together. If we cannot distinguish between them, we must treat them the same, and thus it is impossible to handle the externalities committee members impose on each other within the standard framework of committee selection rules. If we are to study more realistic preferences over committees, we need to move to a setting where a ballot allows a voter to express such preferences, but that brings us to the familiar problem of how do we fit an order over 2 A into the space of one ballot.
Evaluating a committee by the min and the max, while problematic in the case of general committee selection rules, turns out to be natural and appropriate in the case of consular election rules. Voter i's favourite committee is t a, b u such that for every t c, d u, any member of t a, b u is at least as good as any member of t c, d u and one is strictly better -in other words, Pareto dominance. If, however, we are to extend the enquiry to larger committees, the Duggan-Schwartz model of manipulation might need further justification or to be abandoned entirely.


extfieldsofstudy:
Computer Science
Economics

text:
Incentives for early adoption of carbon capture technology: further considerations from a European perspective

This note details two comments on a recent policy proposal in Comello and Reichelstein (2014) aimed at favouring the early adoption of Carbon Capture (CC) technology in the next generation of thermal-based power plants to be installed in the United States.

Introduction
The prohibitively high cost of CC technology for first-of-a-kind plants is recurrently cited as a major barrier to its large-scale deployment. To overcome this problem, Comello and Reichelstein (2014) recently articulate an innovative policy proposal to enable substantial cost reductions by leveraging the sizeable deployment of thermal-based power generation projected in the U.S. during the period 2017-2027. The proposal combines two ingredients: a binding and inflexible emission standard; and the "Accelerated Carbon Capture Deployment" (ACCD) -a preannounced schedule of Investment Tax Credits (ITC) and Production Tax Credits (PTC) -aimed at providing an incentive for newly built power plants in the U.S. to adopt CC immediately.
This brief note extends the analysis by considering two issues. In a first section, we apply the framework detailed in the original article 1 to generate a schedule of tax-credits that is robust to alternative scenarios for CC deployments outside the U.S. In a second section, we reflect on the possible emergence of a coordination game capable of hampering the desired early deployment of that technology and propose a modified schedule of tax-credits that is sufficient to overcome that problem.

-The role of early CC deployments outside the U.S.
Using a list of proposed but still undecided projects (GCCSI, 2013), the authors assume the installation of nearly 3 GW of foreign CC capabilities between 2014 and 2020. However, in Europe, the funding of large CC projects has recently proven to be difficult causing delays and several project cancelations (Lupion and Herzog, 2013). As early foreign projects are posited to engender international spillovers, one may wonder whether these withdrawals could undermine the proposal's success.
To render the proposal robust to the vicissitudes impacting foreign projects, we consider a 'worstcase' scenario whereby foreign deployments are restricted to the unique Canadian 130MW power plant finalized in 2014. To compensate for the absence of foreign early investments, augmented ITC and PTC schedules are needed (cf., Figure 1) but our evaluations confirm that this robust version is almost as attractive as the initial version: 2 • The Levelized Cost of Electricity (LCOE) obtained with a facility that becomes operational by the end of 2027 is approximately 7.9 ¢/kWh if CC technology is consistently adopted by all the newly built U.S. thermal power plants. 3 • The magnitude of the tax-credit levels remain politically acceptable (cf., Figure 1).
• Overall, the cumulated (undiscounted) foregone tax revenue to the U.S. Treasury reaches about $8.2 billion. 4 This robust schedule of incentives thus represents a cost-effective solution for achieving a large scale deployment of this innovative technology.

-Strategic interactions among CC adopters
Recent European literature on CC and storage has highlighted the interactions that exist among CC adopters connected to a common infrastructure system (Mendelevitch, 2014;Massol, et al., 2015). In the present paper, infrastructure issues are neglected but the use of an experience curve de facto generates some interactions. It is instructive to examine these interactions further.
Our discussion is structured as follows. A first subsection reviews the evaluation of the schedule of tax-credits used in the original article. The second subsection focuses on CC adoption in a given year by several players and proves that the incentives offered that year may not be sufficient to rule out the possible occurrence of a coordination game with multiple equilibria. As uniqueness is not achieved, these players may select an equilibrium where some emitters rationally prefer to delay CC adoption.
As that phenomenon may jeopardize the desired policy outcomes, the third subsection identifies an appropriately augmented minimum level of incentives that is sufficient to overcome that issue. The last subsection reports the numerical results obtained using the associated ITC and PTC schedules. For the sake of brevity, all the formal proofs are provided in a Supporting Document.

A -The subsidy scheme in Comello and Reichelstein (2014)
We consider a given year t in { } In year t , we do not model the tax-credits but simply assume that their effect is to lower the LCOE measured on a power plant that early adopts CC capabilities. We let t S be the levelized subsidy and Recall that the ACCD tax-credits are set so that, for a facility to be installed in a given year, it becomes advantageous to adopt CC capabilities immediately compared to retrofitting that plant by the end of 2027. The evaluation of the schedule of tax-credits presented in the original paper is detailed in an associated spreadsheet model: the "NGCC + CC Calculator" (Comello and Reichelstein, 2014). In this model, CC adoption at the maximum level is assumed in each year t so that the cumulated CC capacity available at the beginning of the next year is The authors underline that, by construction, the tax-credits prevent possible 'deviation' from what they name an 'equilibrium path' of early CC adoption. Indeed, if one models CC adoption as a one-shot game involving 11 players (one for each year) where each player faces a binary choice with respect to early CC adoption for the entire capacity t K , the proposed subsidy makes 'early adoption' the best response of every player when the other players also jointly decide 'early adoption'. In this game, the proposed schedule of tax-credits thus makes the decision vector stating 'early adoption' for every player a pure strategy Nash Equilibrium (NE).

B -Is that proposed subsidy sufficient?
In reality, the problem at hand involves a sequence of annual decisions and the cumulated impact of is the cumulated CC capacity in operation at that time. 7 As discussed in the original paper, this LCOE figure takes into consideration a 10% first-of-a-kind premium if the cumulated capacity x is lower than the first 3 GW.
several power stations will be installed in some years (particularly during the period 2023 -2027). As these plants are likely to be owned by independent companies, one may wonder whether, in each year t , the threshold level t S is sufficient to induce the joint early adoption of CC capability by all the plants to be installed that year.
To address this issue, one has to examine the strategic interactions among the plants to be installed in a given year. To clarify the presentation, we consider a simplified case and assume that two identical plants of size 2 t K are installed in year t . These plants are controlled by two independent players labeled '1' and '2' and we posit that each player faces a binary choice with respect to the immediate installation of CC capabilities. We also assume that early CC adoption has already been decided by all predecessors so that the cumulated CC capacity available at the beginning of the year is The 'unsubsidized' game The objective of each player is to minimize its LCOE. Absent any tax-credits, their strategic interactions can be summarized with the 'unsubsidized' normal form game in Table 1.
As N t c is assumed to be a strictly decreasing function, it also pays to delay CC adoption when the rival does not early adopt the capture technology. 8 Hence, the condition (2) indicates that 'late adoption' is a strictly dominant strategy for a player and therefore the pure strategy where both players decide 'late adoption' is the unique NE. Hence, absent any tax-credits, the two players rationally prefer to delay CC adoption.
Emergence of a coordination game We now examine the case where tax-credits are implemented and consider the levelized subsidy level, t S . For a player that early adopts CC capabilities, the payoff is now given by the subsidized LCOE. Together, these two findings suggest that implementing a levelized subsidy that solely verifies t t S S ≥ could lead to a coordination game with possibly several NEs.
However, the existence of a NE other than the one that provides early CC adoption at level t K in year t is a source of concern. The following finding proves that a lower-than-expected level of CC adoption in year t may undermine the ability of the proposed schedule of levelized subsidies to also achieve the early adoption of CC capabilities in subsequent years. can be too small to make 'early adoption' of CC capabilities the best response of an investor in year 1 t + .

C -A remedy
Because of this possible snowball effect, one may desire that the schedule of levelized subsidies rules out any possibility for the investors in any given year t to pick up a NE that does not lead to generalized early CC adoption. As there can be between-year variations in the number of players and in the sizes of their plants, we believe that it is preferable to opt for a threshold level that is large enough to be independent from these considerations. The following proposition offers a sufficient condition for generalized CC adoption to occur.

Proposition -
In each year t , any tax-credits yielding a levelized subsidy t S that verifies

D -Application
This subsection reports the results obtained using the minimum threshold above. The numerical evaluations have been conducted assuming the robust capacity deployment scenario discussed in Section 1. 9 Compared to the values in the original article, our evaluations indicate that the magnitude of the ITC levels remains similar; however, substantially augmented PTC are needed (cf., Figure 2).

[ INSERT FIGURE 2 ABOUT HERE ]
These new levels generate a substantial increase in the cumulative (undiscounted) foregone tax revenue to the U.S. Treasury: about $14.1 billion. This is a 110% increase over the figure obtained in the original article. Nevertheless, we believe that this cost figure remains tolerable for such an ambitious policy, especially one that would now be rendered robust to both foreign adverse events and domestic gaming issues.

Conclusions
This note discusses the feasibility of the policy proposal in Comello and Reichelstein (2014). Two lines of arguments have been considered. First, we have examined the effects of early CC deployments outside the U.S. Second, we have determined that the initially proposed ACCD schedule can be insufficient to engender the desired generalized early adoption of CC capabilities because of the possible co-existence of multiple Nash equilibria. In both cases, a modified version of the policy has been proposed using the detailed cost structure developed in Comello and Reichelstein (2014). Though higher incentive levels have been obtained, our findings confirm that the cost of the proposed ACCD policy to the U.S. Treasury is not out of reach. This modified policy thus represents an interesting instrument to break the 'vicious circle' that currently hampers the deployment of CC technologies.

Further considerations from a European perspective
Albert BANAL-ESTAÑOL Jeremy ECKHAUSE Olivier MASSOL ********* This document constitutes a technical appendix to the aforementioned paper.
• Appendix A (respectively Appendix C) clarifies the assumptions and methodology used to generate the numerical results commented in Section 1 (respectively Section 2) of the paper.
• Appendix B presents the mathematical proofs of the Finding 1, 2 and 3 and the Proposition stated in Section 2 of the paper.

********* Appendix A -The role of non-U.S. CC adoptions, a sensitivity analysis
This Appendix details the assumptions, methodology and results commented in Section 1.

A.2 Methodology
We proceed as in Comello and Reichelstein (2014) and identify the minimum incentives required to bridge the gap between: (i) the Levelized Cost of Electricity (LCOE) of a facility that is retrofitted in 2027, and (ii) the LCOE of a plant that immediately adopts CC capabilities. For each year, the minimum investment tax credit (respectively production tax credits) is calibrated so that the levelized capacity (respectively variable) cost in case of immediate CC adoption 1 is equal to those incurred in case of a retrofit in 2027. 2

A.3 Results
In Table A.2, we detail the "Accelerated Carbon Capture Deployment" (ACCD) tax credits obtained in the robust scenario. These results have been generated using an adapted version of the original NGCC+CC Calculator. 3

Appendix B -Mathematical proofs
This Appendix presents the formal proofs of the results stated in Section 2. Unless otherwise specified, the notation is based on the one introduced in the paper.
Finding 1 -For any levelized subsidy that verifies t t S S ≥ , the strategy vector stating 'early adoption' for each player is a Nash equilibrium of the subsidized game.
Proof: Suppose both players decide 'early adoption'. Each player incurs the subsidized LCOE: is de facto verified which indicates that 'early adoption' is the best response of a player whenever its rival also picks that strategy. Q.E.D.

Appendix C -A robust schedule of ITC and PTC that is immune to strategic gaming considerations
This Appendix details the assumptions and results commented in Section 2.

C.1 Assumptions and methodology
The simulation is based on the projected capacity deployments retained in Appendix A (Table A.1).
We follow the methodology in Appendix A.2 except that the tax credits are now calibrated so as to provide a levelized subsidy that is at least as large as the threshold level mentioned in the Proposition in Section 2. These tax credits thus prevent the existence of Nash equilibriums where some emitters could rationally prefer to delay CC adoption.

C.2 Results
In Table C.1, we detail the "Accelerated Carbon Capture Deployment" (ACCD) tax credits obtained in the robust scenario when the incentives are derived from the levelized subsidy discussed in the Proposition in Section 2. These results have been generated using an adapted version of the original NGCC+CC Calculator. 4