Condorcet completion methods that inhibit manipulation through exploiting knowledge of electorate preferences

Potthoff, Richard F. Article Condorcet completion methods that inhibit manipulation through exploiting knowledge of electorate preferences Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Potthoff, Richard F. (2014) : Condorcet completion methods that inhibit manipulation through exploiting knowledge of electorate preferences, Games, ISSN 2073-4336, MDPI, Basel, Vol. 5, Iss. 4, pp. 204-233, https://doi.org/10.3390/g5040204 This Version is available at: https://hdl.handle.net/10419/167930 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. http://creativecommons.org/licenses/by/4.0/ Games 2014, 5, 204-233; doi:10.3390/g5040204 games ISSN 2073-4336 www.mdpi.com/journal/games Article Condorcet Completion Methods that Inhibit Manipulation through Exploiting Knowledge of Electorate Preferences Richard F. Potthoff Department of Political Science and Social Science Research Institute, Duke University, Erwin Mill, Duke Box 90420, Durham, NC 27708, USA; E-Mail: [email protected]; Tel.: +1-919-684-1380 External Editor: Ulrich Berger Received: 4 August 2014; in revised form: 2 October 2014 / Accepted: 6 October 2014 / Published: 30 October 2014 Abstract: This paper attacks a problem like the one addressed in an earlier work (Potthoff, 2013) but is more mathematical. The setting is one where an election is to choose a single winner from m (> 2) candidates, it is postulated that voters have knowledge of the preference profile of the electorate, and preference cycles are limited. Both papers devise voting systems whose two key goals are to select a Condorcet winner (if one exists) and to resist manipulation. These systems entail equilibrium strategies where everyone votes sincerely, no group of voters sharing the same preference ordering can gain by deviating given that no one else deviates, and the Condorcet candidate wins. The present paper uses two unusual ballot types. One asks voters to rank the candidates with respect both to their own preferences and to their discerned order of preference of the entire electorate. The other just asks voters for their own preference ranks plus approval votes. Novel mathematical elements distinguish this paper. Its Condorcet completion methods examine all 󰇡 3󰇢 candidate triples, sometimes analyze loop(s) of some of those triples, and order candidates in a set by first determining the last-place candidate. Its non-manipulability proofs involve mathematical induction on m. Keywords: Condorcet completion methods; strategic voting; manipulable; cyclical majorities; approval voting; mathematical induction OPEN ACCESS Games 2014, 5 205 1. Introduction This paper can be considered a complement to an earlier one (Potthoff [1], hereafter Po0). Both papers address the problem of devising single-stage voting systems to select a single winner from m (> 2) candidates, under the specific premise that a system should have two principal goals: (i) to elect a Condorcet winner (a candidate who could win pairwise against each opponent) if one exists according to the profile of true preferences of the electorate, and (ii) to be resistant to manipulation, with no lure to vote insincerely. Both papers develop voting systems that thwart manipulations by sophisticated voters who strategically misrepresent their preferences so as to defeat a Condorcet winner. Thus, they both involve game-theory concepts. Our aim is to find voting systems where truthful revelation of preferences is an equilibrium strategy, leading to the election of the Condorcet winner, but in settings necessarily limited to electorate domains that exclude some cyclicities in true preferences. To achieve (i) and (ii) together, both papers use unorthodox ballots (more so in the case of the present paper), and both of them assume and exploit voters’ knowledge of electorate preferences (again more so in the present paper). Both papers utilize both candidate rankings and approval voting in certain ways. For our purposes a voting system (or election system, or just system) is characterized by: (1) its ballot; (2) its procedure for aggregating the ballots to determine the winner; and (3) a set S of sincere voting strategies that specifies how all voters are to mark their ballots, given their true preferences (i.e., as a function of those preferences). The present paper covers voting systems with two types of ballots and three associated aggregation procedures for each. One ballot asks voters to rank the candidates with respect both to their own preferences and to their discerned preferences of the whole electorate. The second ballot is simpler and asks for voters’ own preferences plus approval votes. Po0 likewise covered six systems based on two ballot types each with three aggregation procedures. Compared with the systems of the present paper, those of Po0 are simpler (both practically and mathematically) and are more fit for large public elections, but have non-manipulability properties that are less strong. Thus, the voting systems of the two papers illustrate a tradeoff between non-manipulability and simplicity. Beyond its use of ballots that are out of the mainstream and its exploitation of voters’ knowledge of electorate preferences, the present paper is also distinctive because of several interesting mathematical features. Briefly, they include the following. The non-manipulability proofs use mathematical induction on m; such proofs do not usually do so. The ballot aggregation assigns a key role to the set of 󰇡 3󰇢 candidate triples. In addition, special loops of some of those triples undergo auxiliary analyses in some cases. For the Condorcet completion method that has to be available (under any Condorcet system) to determine the winning candidate when the ballots show no Condorcet winner, a unique procedure applies. When m > 3, that procedure successively, for j = 4, ..., m, orders the candidates in each of the 󰇡 󰇢 j-tuples by first determining the last-place (j-th place) candidate and then placing the remaining candidates in the same order as in the (j − 1)-tuple that contains them all. Examples 1 and 2 in Section 4 Games 2014, 5 206 demonstrate basic details, for m = 5 and 4 (respectively), and, like other, later examples, will aid in understanding the systems. We use the letter G to refer to a group composed of all voters sharing the same true-preference ranking of the m candidates. We call G a preference group. (If there are m = 3 candidates X, Y, and Z, then (e.g.) G(ZXY) denotes the group of all voters who prefer Z to X to Y.) For a given domain of admissible true-preference profiles over the candidates, a voting system will be called non-manipulable if no group G can change the winner of the election to a candidate it prefers (not necessarily its top-preference candidate) by part or all of G deviating from the strategy set S for the system, given that no one else deviates from S. Otherwise, the system is manipulable. The notion here is basically a game-theory concept, where each group G that shares a preference ranking corresponds to a player in a game, and where non-manipulability is equivalent to a Nash equilibrium. In most game-theory problems, however, the rules of the game are given, and the goal is to find the best strategy for each player. But in the choice of a voting system the scene is reversed: Our aim is to select the system (i.e., the rules of the game and the set S) so that the strategy of each “player” (each G) is in accord with (i) and (ii) above, that is, leads to the election of the Condorcet winner and offers no advantage to unilateral deviation from S (where S is consistent with sincere voting). Note that “unilateral deviation” refers here to deviation by a group of voters all having the same ranking of true preferences, rather than deviation just by an individual voter. Our assumed settings, covered in Section 5, are ones where cyclicities in true preferences are fully or partially ruled out: Our non-manipulability results are for domains of true-preference profiles that exclude those with any preference cycles at all (in some settings) or exclude only those that lack a Condorcet winner (in other settings). No such constraints apply, though, for any reported preferences (which may differ from true preferences if there is strategic voting). The non-manipulability of the systems of this paper comes about because of the ballot property that asks voters to provide extra markings beyond the usual rankings on a ranked ballot. These added markings relate in one way or another to what we are calling discerned electorate preferences, or just electorate preferences, which refer to the profile of true preferences of the electorate as a whole. We postulate that the needed information about these electorate preferences is available to all voters (on a pragmatic level, see Remark 10.10 below in regard to possible sources of this information). The additional ballot markings enable exploitation of the discerned electorate preferences and thereby enable use of Condorcet completion methods that render the strategic contrivance of vote cycles unrewarding. With only the usual voter rankings and without the added markings, manipulability is unavoidable, as Remark 10.18 and its example point out. The function of the extra markings is to deter manipulation (see Remark 10.11). One might wonder, though, whether they could actually offer added opportunity for manipulation. But that type of manipulation (as well as all others) is already taken into account in our non-manipulability proofs. Other Condorcet-consistent systems, such as those of Nanson, Kemeny, and Dodgson, are simpler for the voter than those of the present paper, so why are they not superior? They are more manipulable. In fact, for specific preference profiles each of these three is as easy to manipulate as the highly manipulable Borda system, as is illustrated at the end of Section 4.1 below. In what follows, Section 2 deals with minor assumptions and with terminology. Ballots, aggregation procedures, and strategy sets are defined in Section 3. Section 4 provides the two examples mentioned Games 2014, 5 207 earlier. Section 5 deals with non-manipulability and manipulability but relegates two mathematically complex non-manipulability proofs to Appendixes A and B. A manipulability comparison of some systems in this paper and Po0 is examined through an example in Section 6. Section 7 provides an aggregation shortcut, with mathematical proof in Appendix C. Circumvention of minor restrictions is the topic of Section 8. All parts of the paper just mentioned are strictly mathematical, in the sense that, given our assumptions, the conclusions are direct mathematical consequences. The assumptions themselves, however, may separately raise some questions, in both practical and philosophical terms. Concerns about the assumptions have no effect on the correctness of our mathematical results, but nonetheless need to be recognized. An example in Section 9 deals with a quandary that arises from uncertain discernment of electorate preferences. Then, in regard to the assumptions as well as the framework of the paper, Section 10 consists of various remarks that provide analytical discussion, supplementary comments, and numerous references. Section 11 concludes. 2. Secondary Assumptions, and Terminology Some simplifying assumptions are needed in order to avoid excessive complexity, though Section 8 will show how they can be skirted. In any preference profile, it is assumed that no voter is indifferent between any two of the m candidates (and that individual preferences are transitive). There are thus m! preference groups G. (We must deal with all m! of them, not just with the m (coarser) groups whose members share the same top preference but otherwise differ.) Regarding the ballots, we assume that each voter ranks all m candidates using ranks from 1 to m (with no ties) for the voter’s own (reported) preferences on both types of ballot, as well as for the discerned electorate preferences on the first type of ballot. It is assumed that each voter provides the approval votes that are asked for on the second type of ballot. In any preference tallies or vote tallies, it is assumed that no ties between candidates occur and that no total involving preferences or votes is exactly half the total number of voters. As needed, the random tie-breaking device described in Section 8 will ensure that this assumption holds if it does not already hold initially. For clarity, we will henceforth refrain from using the term Condorcet winner, and will avoid as well the two-word terms Condorcet runner-up, Condorcet loser, Condorcet cycle, and cyclical majorities. In their place will be three-word terms obtained by inserting either preference or vote in the middle of a two-word term. A Condorcet preference winner is thus a candidate whom the electorate prefers to each opponent in a two-way match-up with each, and Condorcet vote winner is defined likewise but based on actual votes from a ranked ballot (i.e., reported preferences rather than true preferences). The no-ties assumptions simplify the meaning of a Condorcet preference winner or vote winner. Condorcet preference runner-up will refer to a candidate whom the electorate prefers to each other candidate except a Condorcet preference winner, and Condorcet vote runner-up is defined analogously. A candidate X is a Condorcet preference loser if the electorate prefers every opponent to X. Meanings of other three-word terms should be obvious. Sometimes a Condorcet preference cycle (where, e.g., majorities of the electorate prefer X to Y, Y to Z, and Z to X) will simply be called a preference cycle, and similarly for a Condorcet vote cycle. Games 2014, 5 208 The term basic ranking applies to both ballot types and will refer to the voter’s reported preference ranking, whether sincere or not. It is the same as the voter’s true preference ranking if the voter is non-strategic and votes sincerely. For any preference group G, the set S for a given voting system specifies the (sincere) voting strategy for G. It will be called the base strategy for G under that system. Our systems all make use of approval voting (Brams and Fishburn [2]) in one fashion or another. We use the term approval voting in a way that differs a bit in a nonmathematical sense, though not in a mathematical one, from its usual usage. Specifically, the term will simply connote (for any voter’s ballot) a binary separation of candidates in a given set into those who receive a vote in that set and those who do not, without necessarily signifying either approval of the former or disapproval of the latter. We could have used a different term such as binary voting, but we keep the more familiar term. 3. The Voting Systems The six systems considered in this paper are denoted by RR1, RR2, RR3, RA1, RA2, and RA3. The first three use the first ballot type; the other three, the second ballot type. The first three have three somewhat differing aggregation procedures, whereas the last three have a common aggregation procedure. On the other hand, there is a common set S of base strategies for the first three but three different sets for the last three. Sections 3.1–3.3 cover, respectively, the ballots, the aggregation procedures, and the sets of base strategies. The six systems can efficiently be described and dealt with together, but with attention to the special characteristics of each one. 3.1. The Ballots The two types of ballots are called RR and RA ballots and are used, respectively, in the RR1, RR2, RR3 and RA1, RA2, RA3 election systems. The RR ballot asks the voter to provide two different rankings of the m candidates. The first is the basic ranking (reported preference ranking). The second is the discerned electorate-preference ranking, or simply electorate ranking, for which a voter is asked to rank the candidates based on knowledge of the preference ordering of the entire electorate. Section 3.3 explains this second ranking further. Instead of two rankings, the RA ballot asks for just one: the basic ranking. But it also asks for approval votes. They are subject to the restriction (corresponding to what Brams and Fishburn [2] call sincere approval voting) that one cannot cast an approval vote for any candidate X unless one also casts an approval vote for every candidate who appears higher than X on one’s basic ranking. Ranked voting and approval voting are thus combined on the same ballot. The RA ballot (unlike that for RR) is not really new; it is much the same as the one that Nurmi [3] (p. 176) described. (It also is the same as the ballot for the RA* systems covered in Po0.) 3.2. The Aggregation Procedures Under any of the six election systems, if there is a Condorcet vote winner (as determined from the basic rankings on the ballots), then the system simply chooses that person as the winning candidate and concludes. If not, the aggregation procedure invokes a Condorcet completion method. Because these Games 2014, 5 209 methods (covered next) are complicated, the reader may find it helpful to look at the two examples in Section 4 in conjunction with studying the rest of Section 3. 3.2.1. To Start: Ascribe Approval Votes within Each Candidate Triple There are 󰇡 3󰇢 possible candidate triples that can be chosen from the m candidates. For each voter’s ballot for each triple, each election system ascribes an approval vote to either one or two of the three candidates in the triple. The aggregation procedures for the six systems differ only with respect to the rules by which the Condorcet completion methods ascribe these approval votes, which are captured at the outset. Along with the candidate triples themselves, the ascribed approval votes play a complex but key role that enables the aggregation procedures to bring about non-manipulability properties for the systems, as will be established through later proofs. For a given individual ballot for a given triple, let B1, B2, and B3 denote (respectively) the candidates who (within the triple) are ranked highest (most favorable), second, and lowest on the basic ranking, and (for RR) let E1, E2, and E3 denote the candidates who are first, second, and third on the electorate ranking. The rules are as follows for the four aggregation procedures. In the procedure for the RR1 system: For each ballot for each of the 󰇡 3󰇢 triples, find whether B1 and E1 are the same candidate. If so, then (for this ballot for this triple) ascribe an approval vote to B1 only. If not, both B1 and B2 receive an approval vote. RR2: If B1 and E3 are the same candidate, ascribe an approval vote to both B1 and B2. If not, only B1 gets an approval vote. RR3: If B1 and E1 are not the same candidate and also B3 and E3 are not the same, then approval votes go to both B1 and B2. Otherwise, only B1 receives an approval vote. RA1, RA2, and RA3: They all use the same rule for ascribing approval votes. For a given ballot for a given triple, ascribe an approval vote only to B1 if the ballot shows approval votes for none or one of the candidates, or to both B1 and B2 if it has approval votes for two or all three. Illustration for RR. With four candidates, suppose that a ballot shows BDAC for the basic ranking and ABCD for the electorate ranking. Then, for that ballot, approval votes are ascribed for the ABC triple to both B and A under RR1, but only to B under RR2 and RR3; for the ABD triple to both B and D under RR1 and RR3, but only to B under RR2; for the ACD triple to both D and A under all three rules; and for the BCD triple to B alone under all three rules. Illustration for RA. Suppose that a ballot shows a basic ranking of WXYZ for four candidates, with an approval vote for W only. Then an approval vote is ascribed to X (alone) in the XYZ triple. Ascribed approval votes go only to W in the other three triples. 3.2.2. Steps in the Remainder of the Aggregation Procedure In the rest of the aggregation procedure, the Condorcet completion method is the same for all six systems. The steps are as follows. Games 2014, 5 210 Step 1: A triple will be called cyclical if the basic rankings (upon tabulation across all ballots) reveal that its three candidates exhibit a Condorcet vote cycle. Otherwise, it is noncyclical. Find which of the 󰇡 3󰇢 triples are cyclical and which are noncyclical. Step 2: For each of the 󰇡 3󰇢 triples, tally the total number of ascribed approval votes (see Section 3.2.1) across all ballots for each candidate in the triple. Step 3: In each of the 󰇡 3󰇢 triples, rank the candidates 1, 2, 3. If a triple is cyclical, rank the candidates based on their numbers of approval votes within the triple. If a triple is noncyclical, ranks 1, 2, and 3 go (respectively) to the Condorcet vote winner, runner-up, and loser. (Note: Step 2 obtains approval-vote totals for both cyclical and noncyclical triples. The totals for the latter are not used at this stage but will sometimes be required later.) Steps 4{4} (groups of j = 4 candidates), 4{5} (j = 5), ..., 4{m} (j = m): These step(s) (applicable only when m > 3) consist of ranking the candidates first in all 󰇡 4󰇢 4-tuples (quadruples) of candidates, then in all 󰇡 5󰇢 5-tuples, and so forth. To rank any of the 󰇡 󰇢 j-tuples (j = 4, 5, ..., m), one first determines which candidate is to rank j-th (last), using the method given in Section 3.2.3 just below. Then the ranks of the remaining (j − 1) candidates are made the same as in the (j − 1)-tuple that contains them all. Step 5: The candidate ranked first in the m-tuple of all candidates (Step 4{m} if m > 3) is declared the winner of the election. 3.2.3. Determining the Lowest-Ranked Candidate Let L denote the candidate to be ranked last in a j-tuple. The method to find L may require as many as three (multi-step) operations, which are as follows: (i) Consider the j (j − 1)-tuples that are subsets of the j-tuple. L is taken as the candidate with the most (j − 1)-th places in the j (j − 1)-tuples. If there is a tie, L is the one (among the tied candidates) with the most (j − 2)-th places in the j (j − 1)-tuples. If there is still a tie, continue to try to break it by examining numbers of (j − 3)-th, (j − 4)-th, ..., 2nd places among those candidates who at each point are still in the running to be chosen as L. If now a tie still persists, break it by using Method M1 if the tie is not among all j candidates. (For more about M1 as well as two other methods to be mentioned shortly, M2 and M3, see Section 3.2.4 below.) If the tie is among all j candidates, thus implying that in the j (j − 1)-tuples each candidate appears exactly once in each of the (j − 1) places, then go on to (ii). In Example 1 in Section 4, the aggregation procedure is able to terminate after applying operation (i) first in Step 4{4} (five times, with j = 4) and then in Step 4{5} (once, with j = 5 = m). (ii) If any candidate X has the same candidate (Y, say) ranked immediately below X in all (j − 2) of the (j − 1)-tuples in which both appear, then call X a capping candidate. It will be said that X caps Y. Determine if all candidates are capping candidates. If not, use Method M2 to choose L from those candidates who are not capping candidates. If so, go on to (iii). (iii) Because all j candidates are capping candidates, a single loop comprising all of them is automatically defined. In this loop, candidate i1 caps i2, i2 caps i3, ..., ij−1 caps ij, and ij caps i1, where the candidates are numbered with j of the integers from 1 through m and (i1, i2, ..., ij) is some permutation of those j integers. (For j = 6, e.g., the set of six ordered quintuples in (i) and (ii) would have to be of the form ABCDE, BCDEF, CDEFA, DEFAB, EFABC, FABCD to reach operation (iii), so the loop would be A, B, C, D, E, F, and back to A.) Now consider the j triples that consist of three consecutive Games 2014, 5 211 candidates in the loop, and call them contiguous triples. If (X, Y, Z) is a contiguous triple, with X capping Y and Y capping Z, call Y the central member of the triple. For each contiguous triple, find the number of approval votes won by its central member. (Capture this number regardless of whether the triple is noncyclical or cyclical.) A candidate Y will be called a lesser candidate if, in the contiguous triple of which Y is the central member, Y’s number of approval votes is less than half the total number of voters. Use Method M3 to choose L from among all lesser candidates, or from among all j candidates if there is no lesser candidate. Example 2 in Section 4 can stop only after operation (iii) (in Step 4{4}, with j = 4 = m). 3.2.4. Methods M1, M2, and M3 Methods M1, M2, and M3 are not relevant to the non-manipulability proofs given later, so from that standpoint it is immaterial how they are specified. Thus, they could suitably be defined in numerous ways since they do not affect the proofs. For simplicity, all three can be made the same. One reasonable way for M1, M2, or M3 to choose L from k of the j candidates (where k is the number who qualify to be chosen) is as follows. If 2 < k < j, let L be the candidate who ranks last in the k-tuple that consists of those k candidates. If k = 2, let L be whichever candidate is rated lower by more than half the voters in the basic rankings. If L has to be chosen from all j candidates under consideration (not applicable for M1), let L be the candidate with the smallest number of approval votes totaled across the 󰇡 3󰇢 subset triples. 3.2.5. A Full Ordering Sometimes Although Section 3.2 aims to produce only a winner of the election, in some cases it also yields, as a by-product, a full ordering of the m candidates. That occurs if either there are no Condorcet vote cycles or there is no Condorcet vote winner. It does not occur in the intermediate case where there is a Condorcet vote winner but Condorcet vote cycle(s) exist otherwise. 3.3. The Sets of Base Strategies As noted earlier, the three RR systems have a common set S of base strategies, but the RA systems have three different sets S. Under each of the six systems, the set S specifies simply that voters are to mark their basic rankings sincerely, identically to their true preferences. For marking the electorate ranking for the RR systems and the approval votes for the RA systems, though, the base strategies are more involved. For RR1, RR2, and RR3, S directs voters to mark their electorate rankings in accord with their discernment of the preference profile of the entire electorate. Thus, if there are no Condorcet preference cycles, then every voter’s electorate ranking assigns top rank to the (discerned) Condorcet preference winner, second rank to the Condorcet preference runner-up, and so on, with bottom rank going to the Condorcet preference loser. If there is a Condorcet preference winner (call it A) but preference cycle(s) otherwise, then the voter is to rank A at the top of the electorate ranking. For the rest of this ranking, though, S can allow full leeway: Having A at the top suffices for the non-manipulability proof for RR1; RR2 and RR3 have no such proof for this case anyway. (The start of Section 5 below indicates the preference domain for each non-manipulability result.) Nonetheless, for definiteness one could define S further, such as by Games 2014, 5 218 Example 4. Group G(ABCD) G(DCBA) G(DABC) G(DBAC) G(CABD) Number of voters 43 40 4 4 9 RA2 or RA3 vote A|BCD DCB|A DA|BC DB|AC C|DAB ABCD is the preference order of the electorate. The votes shown for each group except G(CABD) follow base strategy, under either RA2 or RA3. G(CABD) prevents a Condorcet vote winner from emerging. The RA aggregation procedure produces the following results for the four triples: Noncyclical triples: ABC, DAB Cyclical triples: C 49, D 48, A 47; C 49, D 48, B 47 Because B has the most third places (two) in the triples, B is last in the quadruple, thereby causing the ordering of the quadruple to be CDAB. Thus, the manipulation by G(CABD) succeeds in dethroning A in favor of C, its first preference. Observe that, with RA1, the base strategy changes for one of the groups: G(DBAC) votes DBA|C rather than DB|AC. That change causes A to receive 51 approval votes instead of 47 in the first cyclical triple, thus averting the defeat of A by C. Any kind of manipulation attempt by G(CABD) under any of the RR systems will likewise fail (per Proposition 2 in Appendix A). 6. RA* (from Po0) versus RA The RA* ballot of Po0 is the same as the RA ballot of this paper. The systems RA*1, RA*2, and RA*3 of Po0 use, respectively, the same base strategies as RA1, RA2, and RA3. The RA* aggregation procedure, though, is different: If there is no Condorcet vote winner, all RA* systems just choose the election winner via a straight tally of approval votes. But possible greater manipulability of those systems may counteract their greater simplicity. In the following example, which further develops Example 2 of Po0, RA*2 and RA*3 are manipulable whereas RA2 and RA3 are not: Example 5. Group G(ABCD) G(BACD) G(DABC) G(CABD) Number of voters 7 27 29 37 RA2, RA3, RA*2, or RA*3 vote A|BCD B|ACD DA|BC C|DBA There are no preference cycles, and ABCD is the preference order of the electorate. For each preference group above, all four systems happen to prescribe the same base strategy. Each group except G(CABD) follows its base strategy. But thanks to the manipulation by G(CABD), no Condorcet vote winner emerges. With RA*, the ensuing count of approval votes yields 36 for A, 27 for B, 37 for C, and 29 for D. Thus, C wins and the manipulation succeeds. But under RA, the manipulation fails. The ordering of the two noncyclical triples, and the ordering and approval votes for the two cyclical triples, are as follows: Noncyclical triples: BAC, DBA Cyclical triples: A 63, C 37, D 29; C 37, B 34, D 29 Games 2014, 5 219 Note that, despite the locations of the vertical lines, A’s approval votes include 27 from G(BACD) for the ACD triple, and B gets seven votes from G(ABCD) for the CBD triple. D is last in the quadruple because D has the most last places (two) in the four triples. Thus, the order of the quadruple is BACD, B wins, and B’s victory is not favorable to G(CABD). Conceivably one could discover an example where manipulation succeeds with RA2 (or RA3) but fails with RA*2 (or RA*3). Such a case has not been found, however. For RA and RA* to produce a difference, m must be ≥ 4. The RA and RA* systems are effectively the same when m = 3. 7. Simplification of the Aggregation Procedures All the Condorcet completion methods in this paper (see Section 3.2) have been defined in terms of applying them to all m candidates when there is no Condorcet vote winner. A shorter procedure is possible. An obvious—and simpler—approach would be to apply the Condorcet completion method (if it has to be invoked) to just the candidates in the top vote cycle. The top vote cycle is defined to be the smallest set of candidates such that, in the basic rankings, each candidate in the set is ranked above each candidate outside the set by a majority of voters. For all six of our election systems (with their four aggregation procedures), the winner of the election will be the same if the Condorcet completion method is applied just to the candidates in the top vote cycle rather than to all m candidates. This is shown by Proposition 4, proved in Appendix C. 8. Circumventing the Minor Assumptions The minor simplifying assumptions that are stated in Section 2 involve both preferences and votes, thus entailing theoretical and operational concerns, respectively. All of these assumptions, however, can be circumvented if they are not satisfied. A ballot that is incompletely marked violates the assumptions. It can be resolved by treating it as v separate ballots, each with weight 1/v, where v is the number of possible ways of completing the ballot and one of the v ballots corresponds to each of these v ways. Thus (e.g.), if an RR ballot with candidates X, Y, and Z has Z ranked first on the basic ranking, X first on the electorate ranking, and no other rankings marked, it can be treated as 1/4 of a ballot for each of ZXY/XYZ, ZXY/XZY, ZYX/XYZ, and ZYX/XZY. If (e.g.) an RA ballot with four candidates shows Y|W but leaves X and Z unranked below Y and W, it can be treated as 1/2 of a ballot for each of Y|WXZ and Y|WZX, but it can be treated as 1/6 of a ballot for each of Y|WXZ, Y|WZX, YW|XZ, YW|ZX, YWX|Z, and YWZ|X if it shows just YW with no approval-vote marking. Indifference in the preference rankings (another assumption violation) can be handled in essentially the same way as an incompletely-marked ballot. Thus (e.g.), with four candidates a voter who prefers W most and X least but is indifferent between Y and Z can be treated as 1/2 of a voter for each of the WYZX and WZYX preference rankings. Finally, the assumptions precluding ties and the like can be readily circumvented. Let n be the total number of voters in the electorate. Let ug (g = 1, ..., n) be independent random variables each drawn from the uniform (rectangular) distribution with range from 0 to 1. Now suppose that each voter g receives a weight of (1 + ug/n) instead of 1. Such slightly differing weights for the voters automatically produce a Games 2014, 5 220 random tie-breaking mechanism. It ensures that vote tallies and preference tallies will both satisfy the assumptions of no ties between candidates and no totals exactly equal to n/2. Moreover, as one can easily show, the differential weighting will give the same results as the equal weighting when there is no assumption failure under equal weighting. Breaking ties randomly is, in general, a standard approach (cf. Pritchard and Wilson [8] (p. 489)). Ties are less likely the more voters there are, of course. 9. Are RR1 and RA1 Still Best if the Information Postulate Is Relaxed? Thus far, this paper has been purely mathematical. We now turn to broader issues. Treating voters more as real-world people and less as mathematical entities, we first illustrate the effect of uncertainty about electorate preferences. Because RR1 and RA1 are non-manipulable in F1 whereas the other four systems are non-manipulable only in F0 (and just for m = 3 for RA2 and RA3), it would appear that RR1 and RA1 are the only systems that merit consideration. That is the case if the postulate stipulating the needed knowledge of electorate preferences strictly holds. But if not, the other four systems are, in some cases, better at avoiding pitfalls stemming from incorrect discernment of those preferences. The following example, which bears some similarity to Example 5 of Po0, shows how even slight uncertainty as to electorate preferences can cause RR2, RR3, RA2, and RA3 to have an advantage over RR1 and RA1 if there is a close contest between the two front-running candidates: Example 6. Group G(ABC) G(BAC) G(CAB) G(CBA) Number of voters Actual 40 45 9 6 Believed to be 40 45 11 4 RR1, RR2, or RR3 vote ACB/ACB BAC/ABC CAB/ABC CBA/ABC RA1 vote A|CB BA|C CA|B CB|A RA2 or RA3 vote A|CB B|AC CA|B CB|A The preference order of the electorate is BAC with the actual profile but ABC with the presumed profile. For all six systems, all groups except G(ABC) follow their base strategies according to the presumed (not the actual) preference order, by using ABC for the electorate ranking on the RR ballots, or, on the RA ballots, by surmising A to be the Condorcet preference winner (and B the runner-up) when using Rule 1, 2, or 3 to mark approval votes. Without the strategic voting by G(ABC), the actual Condorcet preference winner, B, would straightforwardly win the race under any of the six systems. But the Condorcet vote cycle stemming from the manipulation by G(ABC) has to be resolved by tallying approval votes. The results are 94 for A and 51 for B (and 15 for C) under either RR1 or RA1, but are 51 for B and 49 for A under the other four systems. Thus, B still wins under those four but not under RR1 or RA1. Of course, the G(BAC) voters could block the manipulation by voting BAC/BAC instead of BAC/ABC under RR1 or B|AC instead of BA|C under RA1. They would have to violate base strategy to do so, though, whereas under the other four systems they face no similar dilemma. Games 2014, 5 221 With the close race between A and B, it does not seem sensible anyway for G(BAC) voters to award approval votes to A as well as B, as under either RR1 or RA1. Incorrect or uncertain discernment of electorate preferences contributes to this conundrum. The plight of voters is actually greater under RR1: In the case of m = 3, they control the approval votes (if they have to be tallied) directly and fully under RA1, but only indirectly under RR1. 10. General Remarks This section is a collection of remarks that go beyond mathematical matters and deal with our framework and assumptions, practical and philosophical angles, and associated references. Remark 10.1. Although goals (i) and (ii) stated at the start of the paper are not the only ones that one might want to examine, there is probably broad but not universal agreement that (i) and (ii) are both highly desirable. The selection of the Condorcet preference winner (i), including even the selection of the majority winner in the simple special case of a two-way race, may not maximize utility (in some form) in situations where preference intensities are distributed asymmetrically. Such situations, though, may be uncommon or at least not be easy to identify or remedy; and utility maximization is not the goal here anyway. As for property (ii), it does not seem to receive high priority from (e.g.) advocates of the easily manipulable Borda procedure, or of plurality voting with its incentives to vote insincerely in some cases. But if a system does not reward misrepresentation and voters can vote their true preferences without fretting whether that is strategically unwise, they will face simpler tasks and will have greater confidence in the election process as well. Generally, the less manipulability, the better. Although one might prefer non-manipulability properties stronger than the Nash equilibria that are central to this paper, the nature of the problem limits what can be done. For further discussion related to (i) and (ii), see (e.g.) Merrill [9] (especially Sections 1.2, 1.3, 3.1, and 5.1). For other viewpoints, see (e.g.) Saari [10] and Moulin [11] (Part IV). In addition, see Taylor [12] for an extensive treatment of manipulation in voting. Remark 10.2. Instead of candidate, a broader term such as option could have been used throughout the paper. Options could refer not only to candidates in an election but also (e.g.) to rival legislative proposals. All of our results for candidates would hold also for other options. Remark 10.3. In a system with an ordered agenda, voters vote on successive pairs of options. Other multi-stage systems also exist. We confine our attention, though, to voting systems that select a winner in a single stage. With a single-stage system along with m pre-specified options (or candidates), as in this paper, there is no room for undesirable agenda manipulation nor for strategic voting that could be used to counteract it, as covered in McKelvey [13]. Thus, although sophisticated voting may be beneficial in the agenda-manipulation framework by leading to improved outcomes, no such benefit would apply to our work here. Remark 10.4. Although the Nash equilibria in our systems are relatively natural, understandable, and straightforward, there is, of course, no claim that any of them are unique. Other Nash equilibria would not generally have the same desirable properties as ours. Remark 10.5. Computation for our systems may become prohibitive, when there is no Condorcet vote winner, if m (the number of candidates) is too large. (But a big value of n (number of voters) should Games 2014, 5 222 cause little trouble.) Typical (e.g., single-digit) values of m should be manageable. Moreover, computational burden can be greatly reduced when the shortcut described in Section 7 is applicable. Although the main calculations then involve just m* candidates (where 3 ≤ m* ≤ m), the value of m* cannot be known before the election. In the worst case, m* = m, one first applies Steps 1–3 (Section 3.2) to each of the 󰇡 3󰇢 candidate triples. One then applies Steps 4{4}, 4{5}, ..., 4{m} successively to find the last-place candidate, L, in each of the 󰇡 4󰇢 4-tuples, 󰇡 5󰇢 5-tuples, and so on, where finding L may involve a candidate loop for some of these groups but will be simpler for others. The total number of groups (of varying size) is 󰇡 3󰇢 + 󰇣󰇡 4󰇢+󰇡 5󰇢+…+󰇡 󰇢󰇤,or 2m − 1 − m − 󰇡 2󰇢 < 2m, a number that would seem to be small enough to preclude prohibitive computational time so long as m is below 10 or even slightly greater. Larger values of m would probably be rare in practice anyway. The task of writing an applicable computer program is a largely separate issue from avoidance of prohibitive computation. For small enough elections, hand calculations can be feasible, as one may gather from the examples in Section 4. Remark 10.6. The concept of unilateral deviation or strategic voting by a homogeneous bloc, rather than a single voter, is not unique to this paper. Other works, such as Niou [14] and Brams and Sanver [6], as well as Po0, have also used it. Remark 10.7. Note that we do not require true (or reported) preferences to be single-peaked. One would hardly expect voter preferences for m > 2 candidates in most usual elections to be strictly single-peaked. (On the other hand, if voters are choosing not from m candidates, but rather from (e.g.) numerical values along a continuum that represent money to be spent or taxed, then single-peaked preferences may be reasonable to assume. For such a case, methods far simpler than ours (e.g., asking voters to report just their first-preference value and then declaring the median to be the winner, as suggested long ago by Francis Galton) could be applied. See (e.g.) Black [15] (Chapter IV and p. 188) and Balinski and Laraki [16] (Section 5.2).) Remark 10.8. The value of our systems is greater the lower the frequency of Condorcet preference cycles. Empirically, such cycles seem to be uncommon (see, e.g., Section 10 of Po0). Remark 10.9. Positing knowledge of other voters’ preferences, as this paper does, is not a novel concept and has a long tradition. The idea played a basic role (e.g.) in Farquharson’s [17] (p. 38) classic development of “sophisticated voting”; in related schemes of McKelvey and Niemi [18]; and in the articles of Niemi and Frank [19], Eckel and Holt [20], and Felsenthal, Maoz, and Rapoport [21]. Both in those works and in the voting systems proposed here, each voter’s knowledge of the preference profile of the electorate is the key to bringing about improvements in the voting process. More recent articles that assume voters’ knowledge of other voters’ preferences include Niou [14], Brams and Sanver [6], and Peress [7], as well as Po0. Any posited knowledge of electorate preferences is used only for determining voter strategies and, obviously, could not properly be used in any aggregation procedure. One might be tempted to ask why an election is even needed at all if electorate preferences can already be discerned. Of course, not holding an election could hardly be legitimate. Remark 10.10. How might voters obtain the needed information about the preference profile of the electorate? For various ideas and possibilities, see (e.g.) Section 9 of Po0. The information sources mentioned there include past election results, discussions in the media, and interactions with other voters. Especially, though, they include results from a certain type of public-opinion poll (Condorcet Games 2014, 5 223 polling, covered in Potthoff [22]), which could apply in somewhat the same fashion as described in the work of McKelvey and Ordeshook [23] on rational-expectations equilibrium. More speculatively, they also include political stock markets. Remark 10.11. To the extent that our systems work as intended, the discerned electorate preferences do not often play a role in the eventual aggregation, thus somewhat limiting their import. Paradoxically, their purpose is, in essence, to prevent them from being needed, or at least from needing to be used. Their function is to deter manipulation. If that deterrence succeeds, then manipulated vote cycles are not created, and only the voters’ own reported preference rankings will generally play a role in the aggregation. Remark 10.12. The voting systems of this paper (and of Po0) can be seen as falling under the wide umbrella of mechanism design (e.g., Moore [24]; Maskin [25]; Jackson [26]; Maskin and Sjöström [27]), sometimes referred to also as design of game forms or as reverse game theory. Mechanism design does cover voting systems but deals especially with economic problems. Typically, it does not involve preference groups of differing sizes, as in our work, nor use anything like our unusual ballots. Its results are often highly theoretical and abstract, and limited in their practicality (e.g., Moore [24] (pp. 209 ff.))—unlike the systems of the present paper, which, though not as suited as those of Po0 to real-world elections, are nonetheless workable. Remark 10.13. Ranking of m candidates for either preferences or votes (Section 2) is more involved the larger m is, although any ranked voting system becomes more burdensome for voters as m increases. The points in Section 8 mitigate the complexities, though. Although one could even question the assumption of transitivity of individual preferences (along the lines of Tversky [28], e.g.,), this issue would seem to be minor. For instance, the ABC exit poll among Anderson, Carter, and Reagan in the 1980 U.S. presidential election found individual intransitivity in only 52 respondents among 8146 (Blydenburgh [29] (p. 105)). Remark 10.14. The RA ballot can be simply designed so as to require only a single mark beyond what an ordinary ranked ballot requests (cf. Po0, and the displays in the examples above). Remark 10.15. Section 3.3 did not define the set S for any case where no Condorcet preference winner is discerned (although for definiteness it could have done so). For some other cases, Section 3.3 could allow leeway for base strategies without affecting non-manipulability proofs but, for definiteness, it still defined S. But any indefiniteness concerning S does not prevent the use of any RR or RA system in an actual election, since the aggregation procedure is independent of S and is thus always well defined (though non-manipulability may fail in some cases). Remark 10.16. Although Examples 3 and 4 in Section 5.2 prove that manipulation is indeed mathematically possible, the situations may be so complex that, practically speaking, voters may be unable to discover and carry out the successful manipulation strategies. Difficulty in understanding the role of the candidate triples and of the ascription of approval votes, along with uncertain discernment of electorate profiles, may deter manipulation efforts. In general, the seriousness of whatever manipulability exists may largely depend not only on how easy or hard it is for voters to manipulate the system, but also on how often there are voter preference profiles where manipulation is even possible. These points may not be easy to judge. Remark 10.17. Although we have pointed out some contrasts among the six systems of this paper, we have attempted no assessments to compare RR2 versus RR3 or RA2 versus RA3. Games 2014, 5 224 Remark 10.18. Unfortunately, any voting system whose ballot asks for voters’ candidate rankings and nothing more is doomed to be manipulable even in the rather extreme simple case where the domain of true-preference profiles is restricted to those that are single-peaked. This is shown by the following example, which resembles that of Blin and Satterthwaite [30] but is more general (it applies to any Condorcet completion method, not just Borda as in the earlier article) and is also like that of Penn, Patty, and Gailmard [31] (pp. 447–448) though the perspective differs: Example 7. Suppose that 100 voters each report rankings of three candidates X, Y, and Z with the result that there are 36 ballots marked XYZ (X first, Y second, Z third), 33 marked YZX, and 31 with ZXY. Thus, there is no Condorcet vote winner. Consider the following three voter preference profiles (each of which is consistent with single-peaked preferences): Profile Number of Voters Whose True Preference Order Is Condorcet Preference Winner XYZ XZY YXZ YZX ZXY ZYX 1 36 0 33 0 31 0 X 2 36 0 0 33 0 31 Y 3 0 36 0 33 31 0 Z The observed ballot results could have arisen from Profile 1 if the 33 YXZ voters had voted YZX (and all others had voted their true preferences), from Profile 2 if ZYX voters had voted ZXY, or from Profile 3 if XZY voters had voted XYZ. From the ballots, there is no way to distinguish the three profiles with their three different Condorcet preference winners, even given that no more than one group sharing the same preference order deviated from voting its true preferences. Thus, no Condorcet completion method—including the many that have been proposed (e.g., Brams and Fishburn [4] (pp. 210–212); also Felsenthal and Machover [32])—would render the system non-manipulable, because the method could always select the “wrong” winner. That is, if it selected Y (Z, X) and Profile 1 (2, 3) were the true profile, then the unilateral manipulation of YXZ (ZYX, XZY) voters in voting YZX (ZXY, XYZ) would be rewarded by the dethronement of X (Y, Z) in favor of Y (Z, X). All is not lost, however. Manipulations like those in Example 7, and others that are far more involved, can be thwarted. Our work shows that non-manipulable systems do exist when the true preferences of the electorate show no cyclical majorities, or even when they show a Condorcet preference winner but may otherwise show cycle(s), if the ballots ask for certain markings in addition to the usual rankings. Remark 10.19. The Impossibility Theorem of Arrow [33] and different results on ease of manipulation (e.g., Gibbard [34]; Satterthwaite [35]; Gärdenfors [36]) are not encouraging to those who try to find good voting systems. Nonetheless, as our work is intended to convey, the outlook is not as bleak as one might suppose, at least for situations where cycles in voter preferences are absent or of limited impact. Remark 10.20. It may not be widely recognized that the Arrow results and manipulation results just mentioned do not apply if information is available that is not derivable from the true-preference profile. That is because the results follow from premises that assume availability of nothing other than the profile. They thus do not apply to approval voting nor, in fact, to any of the voting schemes covered here or in Po0. Of course, the unfavorable conclusions of those earlier works may well still hold under much broader premises (it would be highly optimistic to think otherwise), but different proofs would be Games 2014, 5 225 required. Still, the lack of full applicability of the results may suggest that exploration of unusual voting systems can lead to unexpected benefits. 11. Conclusions This paper, like an earlier one, Po0, develops single-winner voting systems that aim to elect a Condorcet preference winner while minimizing incentives for manipulation and insincere voting. A major objective is for voters to be able to vote sincerely with little need to consider whether doing so may hurt them or whether strategic voting might help them. Both papers rely on discernment of electorate preferences, though less so in Po0. Po0 is less mathematical, but the systems of the present paper have stronger non-manipulability properties. The Po0 systems are the simpler ones (and are even simpler than some currently used in certain public elections). Yet the systems of the present paper could be usable at least (e.g.) in a limited or sophisticated electorate, in a committee (whose members may know each other’s views), in groups with some interest in voting theory, or in laboratory experiments, if not in a larger arena. But leading contributions of the present paper, outside of its use of unusual ballots, lie in its distinctive mathematical aspects. These include its successive determination of last-place candidates in j-tuples, its use of candidate triples and of loops formed therefrom, and its non-manipulability proofs that use mathematical induction on m. Acknowledgments The author has benefited from helpful comments from Steven J. Brams, Samuel Merrill, Hannu Nurmi, and Mandar P. Oak, as well as from two referees. An earlier version of some of the material in this paper was presented at the annual meetings of the Public Choice Society in Nashville, Tennessee in March 2003. A related paper (“Super IRV: A cure for the myriad ills of instant-runoff voting?”) was presented at the March 2011 Society meetings in San Antonio, Texas. Appendixes A. Non-Manipulability of RR1, RR2, and RR3 When There Are No Preference Cycles This first appendix proves Proposition 2, which establishes that RR1, RR2, and RR3 are all non-manipulable for any number of candidates (m) among whom there are no Condorcet preference cycles. The first step is to state and prove Theorem T1, whose proof uses Lemma L1 (proved earlier, in Section 5.1). Then Proposition 2 is proved, using Proposition 1 (also proved in Section 5.1) along with Theorem T1. Theorem T1(m). Let Um be a set of m (> 2) candidates among whom the profile shows no Condorcet preference cycles. Let Am and Bm then denote the candidates in Um who are the Condorcet preference winner and runner-up, respectively. Let G be any preference group. For any of the election systems RR1, RR2, or RR3, let S1 denote the set of base strategies, under which all voters simply mark their basic rankings according to their own true preferences, and mark their electorate rankings according to the Condorcet preference ranking for the electorate as a whole (i.e., Am first, Bm second, and so on). If all Games 2014, 5 226 preference groups other than G follow S1 but G can deviate from S1, then all of the following hold for each of RR1, RR2, and RR3: T1.1(m): For any G that does not have Am as its first preference, the members of G can adopt no ballot strategy that will cause Am to place last in Um. T1.2(m): For any G with Bm and Am as its first and second preferences, respectively, its members can adopt no ballot strategy that will prevent Am from placing above Bm in Um. T1.3(m): For any G that has Am as its second preference and does not have Bm as its first preference, the members of G can adopt no ballot strategy that will cause Bm to place last in Um. Proof. The proof of Theorem T1(m) is by mathematical induction on m, and thus has two main steps. The first one is to prove T1(3). The m = 3 candidates will be denoted by A (=A3), B (=B3), and C (Condorcet preference loser). There are, of course, 3! = 6 preference groups G. Proof of T1.1(3). T1.1(3) applies to four of these six preference groups. Because G(BCA) and G(CBA) are already marking their basic rankings with A last, neither one can switch to a ballot strategy that will stop A from placing first. Because G(CAB) voters are already marking C first, they can do nothing to pull C ahead of either A or B in the two-way comparisons with each, so C must remain last. By L1.2 (see Section 5.1), G(BAC) voters cannot stop A from placing above B, regardless of whether the election system is RR1, RR2, or RR3. Proof of T1.2(3). G(BAC) is the only applicable preference group. Again, the result follows from L1.2. Proof of T1.3(3). The only applicable preference group is G(CAB). This group is unable to stop C from placing last, and so B cannot place last. The other main step in the induction proof is to show that T1(m + 1) is true given that T1(m) is true. For purposes of this step, T1.1(m + 1) will be broken into three parts, as follows: T1.1.1(m + 1), Case 1: G has Am+1 as third preference or lower. T1.1.2(m + 1), Case 2: G has Am+1 as second preference, and Bm+1 is not first preference. T1.1.3(m + 1), Case 3: G has Am+1 as second preference and Bm+1 as first preference. T1.1.1(m + 1), T1.1.2(m + 1), T1.1.3(m + 1), T1.2(m + 1), and T1.3(m + 1), all given T1(m), will now each be proved in turn. The most intricate proof is the one for T1.1.3(m + 1). Proof of T1.1.1(m + 1) given T1(m). G cannot have Am+1 higher than second preference in any of the m Um sets that result from removing a candidate other than Am+1 from Um+1. Thus, by T1.1(m) with Am+1 identified therein as Am, it follows that Am+1 cannot place last in any of these m Um sets, regardless of G’s ballot strategy. It is therefore not possible for Am+1 to place last in Um+1, because to do so Am+1 would have to place last in at least one of the m Um sets to which the candidate belongs. Proof of T1.1.2(m + 1) given T1(m). In the Um set obtained by removing Am+1 from Um+1, no ballot strategy adopted by G can cause Bm+1 to place last, by virtue of T1.1(m) with Bm+1 identified therein as Am. Similarly, in the Um set with Bm+1 removed from Um+1, G cannot cause Am+1 to place last, by virtue of T1.1(m) with Am+1 identified therein as Am. In any Um set obtained by removing any candidate other than Am+1, Bm+1, or G’s first preference from Um+1, Am+1 cannot place last, thanks to T1.1(m) with Am+1 identified therein as Am, and neither can Bm+1 place last, owing to T1.3(m) with Am+1 and Bm+1 identified therein as Am and Bm, respectively. Thus, neither Am+1 nor Bm+1 can place last in any of the (m + 1) possible Um sets except perhaps the one from which G’s first-preference candidate is removed. This Games 2014, 5 227 means that some candidate other than Am+1 or Bm+1 has to place last in at least two of the Um sets, which precludes any possibility for either Am+1 or Bm+1 to place last in Um+1. Note that the preceding argument not only proves T1.1.2(m + 1) given T1(m) but also proves T1.3(m + 1) given T1(m). Proof of T1.1.3(m + 1) given T1(m). In any of the (m − 1) sets Um obtained by removing a candidate other than Am+1 or Bm+1 from Um+1, Am+1 must place above Bm+1, no matter what ballot strategy G uses. This follows from T1.2(m) with Am+1 and Bm+1 identified therein as Am and Bm, respectively. Thus, among the (m + 1) sets Um obtainable by dropping one candidate from Um+1, Am+1 can place last only in the Um set that results when Bm+1 is the candidate removed. In fact, Am+1 must place last in that Um set if there is to be any possibility that Am+1 will place last in Um+1. Moreover, if Am+1 is to place last in Um+1, the number of the Um sets in which Bm+1 places last cannot exceed 1 (since then Bm+1 would have more last places than Am+1) and cannot be 0 (since then some other candidate would have more last places than Am+1). Thus, Bm+1 must place last in exactly one of the (m + 1) sets Um to keep alive the possibility of Am+1 placing last in Um+1. Next, because Am+1 must place above Bm+1 in all sets Um that include both of these candidates, Am+1 can place second from last in only one of these sets—the one in which Bm+1 places last. Arguing as before, one finds that Am+1 must place next to last in this set, and also that Bm+1 must place second from last in exactly one set Um (if Am+1 is to have any chance of placing last in Um+1). Continued application of this argument leads to the conclusion that the (m + 1) sets Um have to consist of one set with Bm+1 first and Am+1 omitted, one with Am+1 first and Bm+1 second, one with Am+1 second and Bm+1 third, ..., one with Am+1 third from last and Bm+1 second from last, one with Am+1 second from last and Bm+1 last, and one with Am+1 last and Bm+1 omitted. Thus, Am+1 is a capping candidate, and Am+1 caps Bm+1. Because Am+1 is a capping candidate, Am+1 cannot place last in Um+1 unless all (m + 1) candidates are capping candidates. To complete the proof that Am+1 cannot place last in Um+1, it remains to deal with the case where every candidate is a capping candidate. If all candidates are capping candidates, one examines the loop that they define, and the associated set of (m + 1) contiguous triples. The contiguous triple of which Bm+1 is the central member will also contain Am+1. By L1.1, the number of approval votes for Bm+1 in this triple will be less than half the electorate (regardless of whether the election system is RR1, RR2, or RR3). Thus, Bm+1 is a lesser candidate. The contiguous triple of which Am+1 is the central member will also contain Bm+1. By L1.1, the number of approval votes for Am+1 in this triple will be more than half the electorate. Thus, Am+1 is not a lesser candidate. (Remember that approval votes are tallied for the central member of each contiguous triple even if the triple is noncyclical.) Finally, because there is at least one lesser candidate (Bm+1), and because Am+1 is not a lesser candidate, the last-place candidate in Um+1 will be chosen from candidates who do not include Am+1. This eliminates the only remaining avenue by which Am+1 could place last in Um+1. Proof of T1.2(m + 1) given T1(m). By T1.1(m + 1) (which was just proved), Am+1 cannot place last in Um+1, regardless of what ballot strategy G uses. If Bm+1 places last in Um+1, the conclusion of T1.2(m + 1) is immediate. Thus, one needs to consider only the case where some candidate other than Am+1 or Bm+1 places last in Um+1. The proof of T1.2(m + 1) is completed by applying T1.2(m), with Am+1