11.3 11.2 The Shapley–Shubik Model
A mathematical model for a social structure is usually based on some simplifying assumptions. The Shapley–Shubik model for voting systems assumes that on any issue to be voted upon there is a spectrum of opinion. This concept is on display in the political arena as politicians are characterized as ultra-conservative, conservative, moderate, liberal, and ultra-liberal—or, in terms of colors, red, purple, and blue. There are variations; for example, a politician might be a fiscal conservative and a social liberal (or the other way around). This illustrates that various issues under consideration have different spectra of opinion.
The Shapley–Shubik model is based on voting permutations.
Algebra Review Appendix
Permutations
Voting Permutation DEFINITION
A voting permutation is an ordered list of all the voters in a voting system.
For example, the gasoline tax might be voted upon. Imagine the voters in a line, ordered by how much they think the gasoline tax should be—from a taxi driver who favors $0.00 to a bicycle commuter who favors $100.00 per gallon. The order in which the voters appear in that line would be the voting permutation associated with the gasoline tax issue.
Power Indices Spotlight 11.2
The first widely accepted numerical index for assessing power in voting systems was the Shapley–Shubik power index, developed in 1954 by a mathematician, Lloyd S. Shapley, and an economist, Martin Shubik. A particular voter’s power as measured by this index is proportional to the number of different permutations (or orderings) of the voters in which he or she has the potential to cast the pivotal vote—the vote in the permutation that first turns the permutation from losing to winning.
The Banzhaf power index was introduced in 1965 by John F. Banzhaf III, a law professor who is also well known as the founder of the anti-smoking organization Action on Smoking and Health (ASH). The Banzhaf index is the one most often cited in court rulings, perhaps because Banzhaf brought several cases to court and established precedent. A voter’s Banzhaf index is the number of different possible votes in which he or she casts a critical vote—a vote in favor of a motion that is necessary for it to pass.
467
The Shapley–Shubik model is based on two assumptions:
- Every issue to be voted upon is associated with a voting permutation.
- Every voting permutation has the same chance of being associated with an issue that may be considered.
These assumptions are not intended to be realistic. If “political reality” is considered, we can find issues where the spectrum of opinion is not one-dimensional, in defiance of the first assumption. Voter might be a protégé of voter , and appear next to in all permutations that are associated with issues to be considered—permutations where and are far apart would not occur. By ignoring these political realities, the Shapley–Shubik model can focus on the way a voting system distributes voting power.
If a bill is being drafted to set a gasoline tax rate, it must be drawn so as to attract sufficient votes to meet the quota. Putting the voters in line according to the gasoline tax permutation, one could walk down that line, adding voting weights until the total becomes equal to or more than the quota. The voter who puts the total over the quota is the pivotal voter.
Pivotal Voter DEFINITION
The first voter in a voting permutation who, when joined by those coming before him or her, would have enough voting weight to win, is the pivotal voter in the permutation. Each voting permutation has exactly one pivotal voter.
Self Check 5
In the Film Selection Committee (see Example 4 on page 465), find a voting permutation in which Cao is the pivotal voter.
- In the voting permutation Allen, Cao, Betty, the first member, Allen, has 5 votes, less than the quota. Cao and Allen together have 6 votes, which is equal to the quota, so these two voters can pass a measure. Hence Cao is the pivot.
The gasoline tax story is repeated every time a bill is drafted for consideration by a legislature. To pass, the bill must be approved by the pivotal voter in the voting permutation on the issue it addresses. In a political campaign, there are multiple issues, and the candidates try to address their campaign messages to appeal to the pivotal voter on each issue. This may be complicated, because the pivotal voters for different issues may not agree.
Spotlight 11.1 (page 465) explains how the Electoral College is effectively a 56-voter weighted voting system. Table 11.1 displays the permutation resulting from the 2012 election for president of the United States, in which the winning Democratic ticket was Barack Obama for president and Joseph Biden for vice president, and the Republican ticket was Mitt Romney for president and Paul Ryan for vice president. The table is presented as a voting permutation of the electors in the Electoral College.
468
Each of the voters in the Electoral College is selected by and represents an electorate. Some, such as the Utah popular vote and that of the Nebraska third congressional district, were heavily in favor of the Republican ticket; the Florida popular vote was almost equally split between the two tickets; and still others, such as the District of Columbia popular vote, favored the Democratic ticket by a wide margin. Table 11.1 lists all voters in the Electoral College, in decreasing order by their margin in favor of the Democratic ticket. (The margin is the number of popular votes cast for the Democratic ticket divided by the number of votes cast for the Republican ticket. Other parties were ignored in this calculation.) A running total of electoral votes gives the total weight of each voter and all who came before it in the table. In listing the states and other voters in this order, we have recorded a permutation of the Electoral College participants. The pivotal voter in this particular permutation was Pennsylvania, which brought the running total from 252 to 272, thus exceeding the quota of 270. This is noted in the table by circling the code for Pennsylvania and underlining its running total.
| State | Democrat’s Margin |
Electors | Running Total |
State | Democrat’s Margin |
Electors | Running Total |
|---|---|---|---|---|---|---|---|
| DC | 12.49104 | 3 | 3 | FL | 1.0178 | 29 | 332 |
| HI | 2.5340 | 4 | 7 | NC | 0.9595 | 15 | 347 |
| VT | 2.1493 | 3 | 10 | NE.2 | 0.8646 | 1 | 348 |
| NY | 1.7992 | 29 | 39 | GA | 0.8533 | 16 | 364 |
| RI | 1.7791 | 4 | 43 | AZ | 0.8311 | 11 | 375 |
| MD | 1.7264 | 10 | 53 | MO | 0.8255 | 10 | 385 |
| CA | 1.6228 | 55 | 108 | IN | 0.8116 | 11 | 396 |
| MA | 1.6168 | 11 | 119 | SC | 0.8080 | 9 | 405 |
| ME.1 | 1.5604 | 1 | 120 | MS | 0.7921 | 6 | 411 |
| DE | 1.4659 | 3 | 123 | MT | 0.7533 | 3 | 414 |
| NJ | 1.4362 | 14 | 137 | AK | 0.7447 | 3 | 417 |
| CT | 1.4256 | 7 | 144 | TX | 0.7239 | 38 | 455 |
| IL | 1.4141 | 20 | 164 | NE.1 | 0.7110 | 1 | 456 |
| ME | 1.3730 | 2 | 166 | LA | 0.7022 | 8 | 464 |
| WA | 1.3601 | 12 | 178 | SD | 0.6887 | 3 | 467 |
| OR | 1.2868 | 7 | 185 | ND | 0.6636 | 3 | 470 |
| NM | 1.2369 | 5 | 190 | TN | 0.6570 | 11 | 481 |
| MI | 1.2124 | 16 | 206 | KS | 0.6363 | 6 | 487 |
| ME.2 | 1.1929 | 1 | 207 | NE | 0.6359 | 2 | 489 |
| MN | 1.1711 | 10 | 217 | AL | 0.6336 | 9 | 498 |
| WI | 1.1488 | 10 | 227 | KY | 0.6249 | 8 | 506 |
| NV | 1.1463 | 6 | 233 | AR | 0.6089 | 6 | 512 |
| IA | 1.1258 | 6 | 239 | WV | 0.5705 | 5 | 517 |
| NH | 1.1202 | 4 | 243 | ID | 0.5055 | 4 | 521 |
| CO | 1.1163 | 9 | 252 | OK | 0.4976 | 7 | 528 |
| PA | 1.1156 | 20 | 272 | WY | 0.4053 | 3 | 531 |
| VA | 1.0819 | 13 | 285 | NE.3 | 0.3961 | 1 | 532 |
| OH | 1.0625 | 18 | 303 | UT | 0.3400 | 6 | 538 |
469
EXAMPLE 5 Pivotal Voters in the Film Selection Committee
Allen, Betty, and Cao vote to approve film selections by using the voting system . We observed in Example 4 that the weight-5 voter (Allen) has veto power. Betty and Cao have voting weights 3 and 1, respectively. Let’s consider their voting permutations, shown in Table 11.2. (Voters are identified by initials.) Next to each voting permutation, the total weights of the first voter, the first two voters, and all three voters are shown in sequence. The first number in the sequence that equals or exceeds the quota (6) is underlined, and the corresponding pivotal voter’s symbol is circled. We see that Allen is pivotal in four permutations, while Betty and Cao are each pivotal in one. Hence Allen’s share of the voting permutations is , while Betty and Cao each have a share—even though their voting weights differ.
| Permutations | Weights | Pivotal Voters | ||||||
|---|---|---|---|---|---|---|---|---|
| 5 | 8 | 9 | Betty | |||||
| 5 | 6 | 9 | Cao | |||||
| 3 | 8 | 9 | Allen | |||||
| 3 | 4 | 9 | Allen | |||||
| 1 | 6 | 9 | Allen | |||||
| 1 | 4 | 9 | Allen | |||||
In Example 5, we found that Allen is the pivot in four permutations, while Betty and Cao are each pivot in one permutation. In effect, we determined the Shapley- Shubik power index for this voting system.
Shapley–Shubik Power Index DEFINITION
The Shapley–Shubik power index of each voter is computed by counting the number of voting permutations in which that voter is pivotal, and dividing that number by the number of all voting permutations.
Let’s see how many permutations there are. If there is one voter, there is only one permutation. Two voters would have two permutations, because one could be first, the other second. With three voters, there are three that could be first. Once the first voter is identified, there are two permutations of the remaining two—thus there are permutations in all. The six permutations listed in Table 11.2.
Self Check 6
If there are just two voters, and neither is a dictator, what is the Shapley–Shubik power index of each?
- The quota must be more than either voter’s weight, because there is no dictator. Therefore, both voters are needed to pass a motion; so in both permutations of the voters, the second voter is pivotal. Thus, each voter is pivotal in one permutation, and each has a Shapley- Shubik index equal to .
470
With four voters, there are four who could be first, and for each choice of a first voter, there are six permutations of the remaining three voters. In all there are permutations. This reasoning can be continued ad infinitum. With five voters, the number of permutations is .
Self Check 7
If there are seven voters, how many permutations are there?
- We have seen that with five voters there are 120 permutations. With six voters, there are permutations. Finally, with seven voters, there are permutations.
Factorial DEFINITION
The number of permutations of a set of voters is called the factorial of and is denoted .
It is necessary to consider the number , the number of ways to order the empty set. By convention, , meaning there is one way to do this. The factorial of a positive whole number is the product all the whole numbers from 1 up to :
We saw one of the permutations of the voters in the Electoral College in Table 11.1. Factorials grow rapidly in size, an instance of the combinatorial explosion. For example, is more than 3.6 million, is more than 1.3 trillion. Enter in the Google search box—you will find it is a 75-digit number. Here’s a puzzle: How many zeros are at the end of ?
EXAMPLE 6 The Corporation with Four Shareholders
A corporation has four shareholders, , , , and , with 49, 48, 2, and 1 shares, respectively. it uses the weighted voting system .
The permutations of the shareholders are shown in Table 11.3. (The arrangement is the same as in Table 11.2, which lists permutations and finds their pivotal voters in a three-voter system.) in 10 of the permutations, is the pivotal voter; and are each pivotal voters in 6; and is the pivotal voter in 2 permutations. Therefore, the Shapley–Shubik power index for this weighted voting system is
Self Check 8
If the voting system in Example 6 were changed by giving voter one more vote (everything else the same), in which permutations listed in Table 11.3 would the pivot be different? Find the Shapley–Shubik power index of the altered system.
- Four permutations would acquire new pivots: would be the new pivot in and (the pivots had been and , respectively); and would be the new pivot in and (again, the pivots had been and , respectively). Thus, and each lost two permutations, and and each gained two. Now is pivot in 12 permutations, while ,, and are each pivot in four. The Shapley–Shubik index of is now , while ,, and have Shapley–Shubik indices equal to .
How to Compute the Shapley–Shubik Power Index
471
It is practical to calculate the Shapley–Shubik power index of a system with up to four voters by making a list of all the voting permutations and identifying the pivotal voter in each, as we have done in the previous two examples. This is the brute force way of determining the Shapley–Shubik power index. With a computer, brute force can be used to determine the Shapley–Shubik power index of somewhat larger systems, but eventually the combinatorial explosion renders the brute force method impossible to implement. The Shapley–Shubik power index of the Electoral College is shown in Spotlight 11.5 (page 484). The calculations were performed with an online calculator (see the web citation at the end of this chapter). Brute force would not work here because, as we have noted, the number of voting permutations is more than astronomical. It would be impossible to examine each permutation and identify its pivotal voter.
| Permutations | Weights | Pivot | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| A | B | C | D | 49 | 97 | 99 | 100 | B | |||
| A | B | D | C | 49 | 97 | 98 | 100 | B | |||
| A | C | B | D | 49 | 51 | 99 | 100 | C | |||
| A | C | D | B | 49 | 51 | 52 | 100 | C | |||
| A | D | B | C | 49 | 50 | 98 | 100 | B | |||
| A | D | C | B | 49 | 50 | 52 | 100 | C | |||
| B | A | C | D | 48 | 97 | 99 | 100 | A | |||
| B | A | D | C | 48 | 97 | 98 | 100 | A | |||
| B | C | A | D | 48 | 50 | 99 | 100 | A | |||
| B | C | D | A | 48 | 50 | 51 | 100 | D | |||
| B | D | A | C | 48 | 49 | 98 | 100 | A | |||
| B | D | C | A | 48 | 49 | 51 | 100 | C | |||
| C | A | B | D | 2 | 51 | 99 | 100 | A | |||
| C | A | D | B | 2 | 51 | 52 | 100 | A | |||
| C | B | A | D | 2 | 50 | 99 | 100 | A | |||
| C | B | D | A | 2 | 50 | 51 | 100 | D | |||
| C | D | A | B | 2 | 3 | 52 | 100 | A | |||
| C | D | B | A | 2 | 3 | 51 | 100 | B | |||
| D | A | B | C | 1 | 50 | 98 | 100 | B | |||
| D | A | C | B | 1 | 50 | 52 | 100 | C | |||
| D | B | A | C | 1 | 49 | 98 | 100 | A | |||
| D | B | C | A | 1 | 49 | 51 | 100 | C | |||
| D | C | A | B | 1 | 3 | 52 | 100 | A | |||
| D | C | B | A | 1 | 3 | 51 | 100 | B | |||
| Number of Pivots | 10 | 6 | 6 | 2 | |||||||
In special cases where almost all of the voters have the same weight, the Shapley–Shubik power index can be calculated by relying on the following two principles:
- Voters with the same voting weight have the same Shapley–Shubik power index.
- The sum of the Shapley–Shubik power indices of all the voters is 1.
472
EXAMPLE 7 A Nine-Person Committee
Alice is chairperson of a committee. She has 3 votes, and there are eight other members, each with 1 vote. The quota for passing a measure is a simple majority, 6 of the 11 votes. in our notation, this voting system is .
Each weight-1 member has the same power index. Our strategy is to compute Alice’s Shapley–Shubik power index first. By subtracting her index from 1, we will get the share of power for the remaining members of the committee. Because there are eight of them, and they are equally powerful, we can find the index of each weight-1 member by dividing by 8. Thus, we’ll avoid having to examine all voting permutations.
Alice will be the pivotal voter in any voting permutation where she is in the fourth position, when her vote would bring the total voting weight in favor from 3 to 6; the fifth position, when she would increase the total weight in favor from 4 to 7; or the sixth position, when the total would increase from 5 to 8 with her vote. if she is in any other position in a permutation, another member of the committee will be the pivot.
Because Alice is pivotal in three of the nine positions of a permutation, her Shapley–Shubik index is . The remaining of the voting power is shared equally by the eight other voters. Therefore, each has of the power.
According to the Shapley–Shubik model, Alice is 4 times as powerful as a weight-1 member, although her voting weight is only 3. (Divide her Shapley–Shubik power index by that of a weight-1 voter: .)
The method used to compute the Shapley–Shubik index of each voter in Alice’s committee is applicable to any weighted voting system where all but one of the voters have the same voting weight. Call the voter with the different voting weight the singular voter. For another example, suppose that the singular voter has 1 vote, and 10 other voters have 3 votes. If the quota is 16, the singular voter will be pivotal if preceded by 5 of the other voters. There are 11 voters, so the singular voter can appear in 11 places in a permutation—but is pivotal in only one place. Therefore, the Shapley–Shubik power index of the singular voter is . The other 10 voters share the remaining of the voting power, so each has Shapley–Shubik power index , too. In other words, according to the Shapley–Shubik model, the voters are equally powerful.
Self Check 9
Alice has been promoted. She now has 30 votes, and her new committee has 89 one-vote members. The quota is 60. Use the fact that Alice is the singular voter in this system to find the Shapley–Shubik index of each member of this new committee. (Spotlight 11.6 on page 487 has more to say about this voting system.)
- Alice will be the pivot in any permutation with between 30 and 59 weight-1 voters coming before her— in other words, if she is in position 31 up to 60. If we separate the permutations into 90 groups, according to Alice’s position, she is the pivot in every permutation in 30 of the groups and not the pivot in the remaining 60. Her Shapley–Shubik power index is therefore . The other 89 members of the committee have equal shares of the remaining of the power. Each weight-1 voter’s Shapley–Shubik power index is .
Some of the weight-1 members of Alice’s nine-person committee have been scheming to counteract Alice’s power. Bill, a weight-1 member, has convinced three of the other weight-1 members to give him their votes. Effectively, the system now has six voters: Alice has three votes, Bill has four votes, and there are four 1-vote members. The weighted voting system is . Zoë, a weight-1 voter who did not cede her vote to Bill, wonders if this pact will affect her power negatively.
473
EXAMPLE 8 Zoë’s Power After the Revolt
Zoë will be the pivotal voter of a permutation if and only if the voters coming before her in the permutation have a combined weight of exactly 5. There are two kinds of voting permutations that meet this condition ( is Zoë):
- , where one of is Alice, one of or is Bill, and the remaining three Ys are weight-1 voters
- , where or is Bill, and one of is Alice
Counting these permutations will involve the fundamental principle of counting. Let’s count the voting permutations of the first type. There are three places that Alice could occupy before Zoë, and two places that Bill could occupy after Zoë. By the fundamental principle of counting, there are ways we could position Alice and Bill in a voting permutation with Alice before Zoë and Bill after Zoë. We can count the number of permutations in each of the six groups, where Alice, Zoë, and Bill have already been positioned. The three other committee members can be ordered in ways, and put accordingly into the three open spaces. Using the fundamental principle of counting (again), we see that the number of voting permutations of the first type is . The number of permutations of the second type, where Bill comes before Zoë and Alice after, is the same. Therefore, there are voting permutations in which Zoë is pivotal. The Shapley–Shubik index of Zoë is therefore . Before the revolt, Zoë had of the power according to the Shapley–Shubik model, so her power has increased a bit.
Alice has also been wondering about the situation. Bill has only one more vote than she does—will her power be much less than his?
EXAMPLE 9 Alice’s Power After the Revolt
Alice will be pivot in any permutation where the following occurs:
- She is second, with Bill first. There are permutations of this type, since the 1-vote members, who come after Alice, can be in any order.
- She is third, with Bill and a 1-vote member first. There are of these permutations, because Bill could be in one to two positions, and the 1-vote members can be in any order.
- She is fourth, with Bill and a 1-vote member following. Again, there are 48 permutations in this category.
- She is fifth, with Bill last. There are of these permutations, because there are ways to order the four weight-1 voters who came before Alice.
All told, Alice is pivot in 144 permutations, and her Shapley–Shubik power index is . The revolt has reduced her power considerably. The four remaining 1-vote members of the committee control of the power, so the remaining of the power—twice Alice’s—is Bill’s.
Self Check 10
Zoë has decided to cede her vote to Bill, giving him 5 votes. The system is now . Determine the Shapley–Shubik power indices for Alice, Bill, and the remaining weight-1 voters.
- Bill is one vote short of being a dictator. He will be pivot in any permutation when he is in position 2, 3, or 4. He will not be pivot in position 1, for then the pivot will be whoever is in position 2, and he will not be pivot in position 5, for then the pivot will be the occupant of position 4. Therefore, he is pivot in of the permutations. Alice’s power is the same as a weight-1 voter’s, so she and the three weight-1 voters share the remaining of the power. Each has a Shapley–Shubik index equal to .
474