MILES H. SONSTEGAARD

A SHORTCUT METHOD OF CALCULATING THE DISTRIBUTION OF ELECTION OUTCOME TYPES UNDER APPROVAL VOTING

ABSTRACT. The paper applies to approval voting, under which the voter casts a ballot by casting one vote for each of k candidates, where k = 1; 2; . . . ; m 1 and there are m candidates. I assume (following Brams and Fishburn) that each of the voter’s 2m 2 strategies is equally likely to be chosen. Election-outcome types include: the m-way tie; (m 1)-way ties with the runner-up trailing by 1; 2; . . . ; n votes; (m 2)-way ties, and so on. The frequency distribution of outcome types varies only with m and n and is necessary to the calculation of the expected utilities of successive ballots cast, in the same election, by a voter under a variant of approval voting. This variant allows the voter to cast several complete ballots provided that he pays the respective prices, which could reasonably be based on the expected utilities. The paper describes a shortcut method of calculating the distribution of outcome types when m = 4 and n rises to levels that make straightforward calculation computationally infeasible. The shortcut involves the combining of an outcome type, instead of each member of that type, with each of the 14 strategies available to the incremental voter. In going from n 1 to n, for n > 3, the number of outcome types increases by a factor of (n + 3)=n; whereas, the number of combinations of strategies increases by a factor of 14. KEY WORDS: Elections, Approval voting, Voting, Shortcut method, Election outcome types

Under approval voting the voter casts a ballot by casting one vote for each of k candidates, where k = 1; 2; . . . ; m 1 and m is the number of candidates on the slate. The candidate receiving the most votes wins; any tie is broken by a fair random process. As proposed by Brams and Fishburn (1978), approval voting allows each voter to cast one ballot and involves no voting fee. A possible variant of this method would permit the voter to cast one or more ballots (in the same election) and require him to pay a price for each ballot cast. This would allow him to express the intensity of his preference, but it would raise the question: how should the successive ballots cast by a voter be priced in relation to one another? One likely answer would be: in proportion to ex ante Theory and Decision 44: 211–220, 1998.

c 1998 Kluwer Academic Publishers. Printed in the Netherlands.

*115424* v.5; p.1

PIPS No.: 115424 HUMSKAP theo351.tex; 1/07/1998; 12:23;

212

MILES H. SONSTEGAARD

expected utility. On the basis of the Brams–Fishburn assumption that each of the voter’s possible voting strategies is equally likely to be chosen, it can be shown that expected utility varies from one successive ballot to the next and the variation depends on the distribution of election-outcome types. (Examples of these types are: an m-way tie, an (m 1)-way tie with the runner-up trailing by x votes (x = 1; 2; . . .), (m 2)-way ties, and so on.) This distribution varies with the number of voters, n. Thus there is at least one possible reason for pursuing the objective of the present study. This objective is to find a feasible way to calculate the distribution of election-outcome types as a function of n, for sizable values of n. Now, it is straightforward to find this distribution by calculating the election-outcome type for each logically possible combination of voting strategies for n voters, but for even moderate values of m and n the number of combinations is large. For example, let m = 4, with candidates A; B; C and D. Then the voter has 14 permissible strategies. He can vote for: A; B ; C ; D; A and B ; A and C ; A and D; B and C ; B and D; C and D; A; B and C ; A; B and D; A; C and D ; or B; C and D. And of course the number of logically possible combinations is 14n , so that the computational task can easily become prohibitive. The foregoing method will therefore be referred to as the hammer-andtongs method. Instead of actually calculating the election-outcome type for each of 14n elections, one might seek a shortcut. One shortcut method of calculating the distribution of election-outcome types will now be illustrated for m = 4. This method is based, in part, on the principle that information obtained in calculating the distribution for n voters can be used to simplify the calculation for n + 1 voters. But mainly it is based on the combination of an outcome type, instead of each of the members of that type, with each member of the set of strategies available to the incremental voter. We begin by observing that, for n = 1, the voter can produce one of three possible types of outcomes: (a) one candidate gets a vote; (b) two candidates get one vote each; and (c) three candidates get one vote each. In Figure 1 these types are represented by histograms. The rectangles making up any such histogram are ordered so that they decrease in height monotonically from left to right, and they are always shown in reduced form such

theo351.tex; 1/07/1998; 12:23; v.5; p.2

SHORTCUT METHOD

213

Figure 1. Possible types of outcomes for one voter.

that there are never more than m 1 actual rectangles, any other rectangle being degenerate in the sense of having zero height. The numerical code appearing below each histogram comprises m 1 base-ten numbers, the kth number specifying the absolute difference in height between the k th rectangle and the (k + 1)th rectangle. Election-outcome type 100 shows one of the candidates (A; B; C or D) winning over each of the other three by exactly one vote. (There is no implication in this code that the winning candidate received exactly one vote–in the general case, it might have received any finite, positive, integral number of votes, with each of the other candidates receiving one less.) In Figure 1 the number lying above each histogram shows how many ways the type can occur with n = 1 and therefore, given the Brams–Fishburn assumption, the expected relative frequency of its occurrence. Hereinafter, it will be convenient to refer to the candidates A; B; C and D as 0, 1, 2, and 3, respectively. Type 100 then indicates that either 0, 1, 2 or 3 won the election, over each of the others, by exactly one vote. When we let n = 2, each of these four election outcomes could be combined with each of the 14 strategies available to the second voter, but this would be proceeding by the hammer-and-tongs method, that is, by actually calculating the outcome of every election. Under the shortcut method proposed here we combine, with each of the 14 strategies of the second voter, type 100 only, rather than each of the four election outcomes. The election results (six types) are shown in Figure 2. On each line is shown the type of election-outcome found by combining type 100 with one of the second voter’s available strategies. The strategy 0 was chosen arbitrarily to represent the first voter’s type 100; 1, 2, or 3 could have been chosen instead. (It is trivial to show that each of the four strategies–0, 1, 2, 3–yields the same set of types, albeit in a different order, when combined successively with the second voter’s 14 strategies ordered as shown.) A weight w of 4 is assigned to the outcome specified on any line in Figure 2 because type 100

theo351.tex; 1/07/1998; 12:23; v.5; p.3

214

MILES H. SONSTEGAARD

Figure 2. Possible types of outcomes for type 100 and a second voter.

encompasses four strategies. The 14 strategies of the second voter are combined with type 010 in Figure 3 and with type 001 in Figure 4. By summing the weights for a given type across Figures 2–4, one gets the number of outcomes, as shown in Table 1. In adding a third voter, one can start with the ten election-outcome types of Table 1, combining each type with each of the 14 strategies of the third voter and tallying the respective weights for each of the resulting types. For example, type 000 results when: type 010 is combined with the third voter’s 23-strategy (w = 24, see Table 1); type 001 is combined with his 3-strategy (w = 24); and type 100 is combined with his 123-strategy (w = 24). The resulting weight of 72 is shown for type 000 in Table 2, which shows weights, by type, for n = 3.

theo351.tex; 1/07/1998; 12:23; v.5; p.4

SHORTCUT METHOD

215

Figure 3. Possible types of outcomes for type 010 and a second voter.

The number of types of election outcomes is

t=1+n+

Xi XXi n

=1

i

n

+

j

j

=1 i=1

for n > 2. The Appendix may illuminate the origin of the equation. Table 3 shows t as a function of n for n = 1; 2; . . . ; 10. Under the hammer-and -tongs method one combines the 14 strategies of the first voter with the 14 strategies of the second and gets 196 combinations of strategies but only 10 election-outcome types. One then combines each of the 196 combinations of strategies with the 14 strategies of the third voter and gets 2744 combinations of

theo351.tex; 1/07/1998; 12:23; v.5; p.5

216

MILES H. SONSTEGAARD

Figure 4. Possible types of outcomes for type 001 and a second voter.

strategies, but only 20 election-outcome types. And so on, as shown in Table 3. Bringing the kth voter’s 14 strategies to bear on results based on the assumed behavior of the first k 1 voters appears to be unavoidable, but less calculation is involved with a series of numbers of types–3, 10, 20, 35, and so on–than with the corresponding series for combinations–14, 196, 2744, 38416, and so on. Note that in going from n 1 to n, for n > 3, the number of outcome types increases by a factor of (n + 3)=n; whereas, the number of combinations of strategies increases by a factor of 14.

theo351.tex; 1/07/1998; 12:23; v.5; p.6

217

SHORTCUT METHOD

Table 1. Election-outcome types for two voters Code type

Number of outcomes

Code type

Number of outcomes

000 001 002 010 011

14 24 4 24 24

020 100 101 110 200

6 24 48 24 4 196

Table 2. Election-outcomes types for three voters Code type

Number of outcomes

000 001 002 003 010 011 012 020 030 100

Code type

Number of outcomes

101 102 110 111 120 200 201 210 300

360 108 288 216 36 96 108 36 4 2 744

72 252 96 4 378 288 36 72 6 252 Table 3 Number of voters, n

Number of election-outcome types, t

1 2 3 4 5 6 7 8 9 10

3 10 20 35 56 84 120 165 220 286

Number of combinations of strategies

7 105 1 475 20 661 289 254

2 38 537 529 413 789 046 654

14 196 744 416 824 536 504 056 784 976

theo351.tex; 1/07/1998; 12:23; v.5; p.7

218

MILES H. SONSTEGAARD

Table 4. t as a function of n for n > 2

n

t

2

10

3

20

4

35

5

56

6

84

1st difference

2nd difference

3rd difference

10 5 15

1 6

21

1 7

28

The present author has calculated distributions of election-outcome types only up to n = 78, for which the number of types is 85 320 and the number of combinations of strategies is a 90-digit integer starting out 250 026 926. . .. For printout the 85 320 types were consolidated into 35 categories, 20 of which are well defined types, the other 15 being open-ended categories such as a three-way tie with the runner-up trailing by four or more votes. The 20 are just sufficient to support the calculation of expected utilities for the first three ballots cast by any one voter. How can we test the constructive simulation for possible errors? For m = 4, the necessary conditions for correctness include the following: 1. The numbers of election outcomes tallied for all the electionoutcome types should sum to 14n . 2. The number of election outcomes tallied for any election-outcome type should be even. 3. The number t of election-outcome types should be 10 for n = 2, 20 for n = 3, and 35 for n = 4, and as n is incremented successively by 1, the third difference in t, with respect to n, should be +1 (see Table 4 for illustration, Appendix A for proof). 4. For each of the first few values of n, the distribution of electionoutcome types should be confirmed by the (much simpler to program) hammer-and-tongs method, and as n is increased, no change in the constructive simulation program should be made unless the safety of the change is verified by overlapping on n.

theo351.tex; 1/07/1998; 12:23; v.5; p.8

219

SHORTCUT METHOD

Table 5. Number of nontie types as a function of n for n > 2

n

Number of types

2 1+2+1+3+2+1 3 1+2+1+3+2+1

+4 + 3 + 2 + 1

4 1+2+1+3+2+1+4+3+2+1

+5 + 4 + 3 + 2 + 1

5 1+2+1+3+2+1+4+3+2+1+5+4+3+2+1

+6 + 5 + 4 + 3 + 2 + 1

APPENDIX THIRD DIFFERENCE IN NUMBER OF OUTCOME TYPES WITH RESPECT TO NUMBER OF VOTERS

For n = 1, consider four categories of election outcomes: (a) the four-way tie; (b) three-way ties; (c) two-way ties and (d) nonties. As n increases from unity, the number of kinds of four-way ties remains at one–thus the first difference is zero. With n = 1, the three-way tie will have the runner-up trailing by one vote. With n = 2, the runner up can trail by either one or two votes, and so on. Thus the number of kinds of three-way ties will be equal to n, so that the first difference will always be a plus one. Given a two-way tie, there are two losers, say, L1 and L2. With n = 1, each loser trails by one vote. Increase n to 2 and 2 kinds of two-way ties are added: L2 trails by 2 and L1 by 1 or 2. Increase n to 3 and 3 kinds are added: L2 trails by 3 and L1 by 1, 2 or 3. Thus in going from n 1 to n voters, the increase in the number of kinds is equal to n, which is to say that the first difference equals n. Therefore the second difference equals one and the third, zero. Finally, given a nontie, there are three losers, L1; L2 and L3 with L3 rightmost on the outcome histogram. In the new types of nonties that are added when n increases by one, L3 always trails the winner by n votes. When n = 1, all three lose by one vote. When n = 2 and L1 trails by 1 vote, then L2 can trail by 1 or 2, but when L1 trails by 2 votes, then so must L2. Thus when n increases from 1 to 2, the number of kinds of nontie types goes up by 2 + 1. When n = 3 and L1 trails by 1, L2 can trail by 1, 2 or 3; but when L1 trails by 2, L2 can trail only by 1 or 2; and when L1

theo351.tex; 1/07/1998; 12:23; v.5; p.9

220

MILES H. SONSTEGAARD

trails by 3, L2 must trail by 3. Thus when n goes from 2 to 3, the number of types increases by 3 + 2 + 1. It is easy to show that when n goes from 3 to 4 the number of types increases by 4 + 3 + 2 + 1, and so on. Table 5 shows, for n = 2; 3; 4 and 5, respectively, a series of addends arranged as suggested by the foregoing explanation and summing to the number of nontie types for the corresponding value of n. Clearly, the sum of each encircled group of addends is the first difference between the number of nontie types for n 1 and that for n, and the encircled addend is a second difference. Because the second difference equals n + a constant, the third must equal plus one. And because, for each of the other three categories of outcome types the third difference is zero, the third difference, with respect to n, in number of types t for all categories combined, must also be a plus one. REFERENCE Brams, S.J. and Fishburn, P.C. (1978), Approval Voting, American Political Science Review 72(3): 831–847.

Address for correspondence: Miles H. Sonstegaard, Department of Economics, University of Arkansas, College of Business Administration, Fayetteville, AR 72701, U.S.A. Phone: (501) 575-4151; Fax: (501) 575-7687

theo351.tex; 1/07/1998; 12:23; v.5; p.10