Embedded Files
John Banzhaf
John Banzhaf
Lloyd Shapely
Lloyd Shapely
Martin Shubik
Martin Shubik
Common Core Standards and Mathematical Practices
Common Core Standards and Mathematical Practices
7th Grade: Number Systems
7NS.A1 Apply and extend previous understandings of addition and subtraction to add and subtract integers and other rational numbers; represent addition and subtraction on a horizontal or vertical number line diagram.
Mathematical Practices
MP.2 Reason abstractly and quantitatively.
MP.3 Construct viable arguments and critique the reasoning of others.
MP.4 Modeling with Mathematics
Learning Objectives
Learning Objectives
Students will be able to…
Students will be able to…
Define power indices and coalitions
Explain the mechanics behind weighted voting
Compute Banzhaf and Shapley-Shubik power indices from sample elections
Describe how different types of voters influence the way we compute power indices
Make a connection between power indices and the Electoral College
Introduction:
Introduction:
Power indices are the ways of quantifying power in a weighted voting system. But, in order to be able to compute both the Banzhaf and Shapley-Shubik power indices, it is important to understand several topics: examples of different types of voters, how weighted voting works, and what the function of a coalition is.
Power indices are the ways of quantifying power in a weighted voting system. But, in order to be able to compute both the Banzhaf and Shapley-Shubik power indices, it is important to understand several topics: examples of different types of voters, how weighted voting works, and what the function of a coalition is.
Critical voters: when a voter has influence in determining whether it is a winning coalition
a voter who, if they changed their vote from yes to no, would cause a change in the winner
Dictator voters: when a voter's weight is equal to or greater than the quota.
TYPES OF VOTERS:
TYPES OF VOTERS:
Pivotal voters: when a voter is responsible for making a coalition reach the quota
pivotal voter causes the coalition to "pivot" from losing to winning
Dummy voters: when a voter has no influence in the outcome of the election.
QUESTIONS TO KEEP IN MIND WHEN COMPUTING POWER INDICES:
QUESTIONS TO KEEP IN MIND WHEN COMPUTING POWER INDICES:
Banzhaf = how often is the voter critical to a coalition?
Shapley-Shubik = how often is the voter pivotal to a coalition?
Weighted Voting
Weighted Voting
one voter = x amount of votes
In terms of two candidate elections:
w = weight
The number of votes each player controls - denoted w1... wn
v = voters
(denoted v1... vn)
w1…, wn are the weights of voters v1…., vn
q = quota
This represents the minimum number of votes needed to win
Standard notation: (q; w1, w2….., wn)
quota is given first, followed by the respective weights of the individual voters
Total number of votes is t= w1 + w2 + wn
1/2t < q < t = quota (the number of votes required to win the election)
"All animals are equal...but some animals are more equal than others." - George Orwell
Weighted Voting Example
Weighted Voting Example
[25; 8, 6, 5, 3, 3, 3, 2, 2, 1, 1, 1, 1]
This is a weighted voting system with 12 voters
(v1..., v12)
The quota is 25
v1 has 8 votes, v2 has 6 votes...., v12 has 1 vote
Weighted Voting Example with a dictator
Weighted Voting Example with a dictator
[10:11, 3, 2]
In this example, voter 1 (v1) can reach the quota without requiring the support of any other player.
Voter 1 is therefore the dictator, because their weight is equal or greater than the quota.
In this case, the q = 10 and the weight of v1 is 11.
Weighted Voting Example with a dummy
Weighted Voting Example with a dummy
[10; 7, 6, 2]
In this example, voter 3 (v3) is considered a dummy voter, because they have no affect on the outcome.
The only way the quota can be met is if voter 1 and voter 2 support the outcome.
In this case, q=10 and the weight of v1 + v2 = 13 --- which is greater than 10.
COALITIONS:
COALITIONS:
All voters within a coalition are assumed to be politically like minded, or that they will vote in the same way
Winning coalition = all the voters inside the coalition voted for the winning candidate
The number of votes in the coalition surpasses the quota
Losing coalition = all the voters inside the coalition voted for the losing candidate
Two person elections or yes/no vote cannot result in two disjoint winning coalitions
Winning Coalition Example
Winning Coalition Example
Given a coalition of [A, B, C, D] = [9, 8, 7, 2] with a quota of 19
9 + 8 + 7 + 2 = 27 > 19
Therefore, this is a winning coalition
Determining a Coalition's Critical Voter Example
Determining a Coalition's Critical Voter Example
Any subset Y of the 5 voters
Take V(q; w1, w2….., w5)
Suppose a coalition is the subset Y = [v1, v3, v4]
This is a winning coalition: w1 + w3 + w4 >= q
[v2, v5] cannot also be a winning coalition since we cannot have both
W1 + w3 + w4 >= q and w2 + w5 >= q
This is because q>1/2t, so we would then have
W1 + w3 + w4 + w2 + w5 >= 2q > t, which is impossible
Suppose a voter k is in a winning coalition Y
That voter k is said to be critical if Y minus voter k is not a losing coalition
Therefore, if voter k is removed from the coalition, then this coalition will no longer win
In the previous example, Y = [v1,v3,v4] was winning
Ie: w1 + w3 + w4 >= q
But if, for example, w3 + w4 < q, then the coalition Y\ {v1} = {v3, v4} is losing
This means v1 is critical for this coalition
Critical Coalition Voter Example
Critical Coalition Voter Example
Given a quota (q) of 22, for a coalition of [A, B, C, D] = [10, 9, 8, 3]
When A is removed, total votes are 9 + 8 + 3 = 20 < q, therefore A is a critical voter
When B is removed, total votes are 10 + 8 + 3 = 21 < q, therefore B is a critical voter
When C is removed, total votes are 10 + 9 + 3 = 22 = q, therefore C is not a critical voter
When D is removed, total votes are 10 + 9 + 8 = 27 > q, therefore D is not a critical voter
Sequential Coalitions
Sequential Coalitions
A sequential coalition is a coalition of players where the order in which a player joins matters
Total number of sequential coalitions = n! = n * (n-1) * (n-2) * (n-3) … 2 * 1
n = number of voters
If you have n voters, there are 2^n coalitions and n! sequential coalitions
Why? Think of forming a sequential coalition as having slots into which we want to place the voters. ( _ , _ , _ , _ )
Sequential Coalitions Example #1
Sequential Coalitions Example #1
We have four voters with like-minded views who are thinking of forming a coalition. (n = 4)
First slot = n voters
⟨ _ , _ , _ , _ ⟩ → Any voter can start this coalition and take the first slot
Second slot = n - 1 voters
⟨ v1 , _ , _ , _ ⟩ → The first voter joined! This means for the second slot, there are 3 voters who can join
Third slot = n - 2 voters
⟨ v1 , v2 , _ , _ ⟩ → The second voter joined! Now, there are only two slots left
Last slot = 1 voter
⟨ v1 , v2 , v3 , _ ⟩ → For the last slot, there is only one voter left to join the coalition
So, this coalition looks like this: ⟨ v1 , v2 , v3 , v4 ⟩
But there are 23 other ways this coalition can end up forming! Depending on the order in which the four voters joined, it could have looked like this:
⟨v4 , v3 , v2 , v1 ⟩
or this:
⟨v2 , v4 , v1 , v3 ⟩
etc.
Sequential Coalitions Example #2
Sequential Coalitions Example #2
If there are 3 voters, there are 3! (6) possible sequential coalitions:
⟨ v1 v2 v3 ⟩ , ⟨ v1 v3 v2 ⟩ , ⟨ v2 v1 v3 ⟩ , ⟨ v2 v3 v1 ⟩ , ⟨ v3 v2 v1 ⟩ , ⟨ v3 v1 v2 ⟩
Note that angular brackets ⟨ ⟩ are used to represent sequential coalitions
Banzhaf Power Index
Banzhaf Power Index
Introduction to Banzhaf Method:
Introduction to Banzhaf Method:
The Banzhaf power index, named after John F. Banzhaf III (originally invented by Lionel Penrose in 1946 and sometimes called Penrose–Banzhaf index; also known as the Banzhaf–Coleman index after James Samuel Coleman), is a power index defined by the probability of changing an outcome of a vote where voting rights are not necessarily equally divided among the voters or shareholders.
To calculate the power of a voter using the Banzhaf index, list all the winning coalitions, then count the critical voters. A critical voter is a voter who, if he changed his vote from yes to no, would cause the measure to fail. A voter's power is measured as the fraction of all swing votes that he could cast. There are some algorithms for calculating the power index, e.g., dynamic programming techniques, enumeration methods and Monte Carlo methods (Wikipedia). More Links:
Computing the Banzhaf Power Indices
Computing the Banzhaf Power Indices
Steps:
Listing winning coalitions
Identifying all voters who are critical in each coalition,
Couning how many times each voter is critical for all winning coalitions
Calculate Banzhaf power indices in fractions or decimals by dividing counts in step 3 by the total times any voter is critical
Another example:
It turns out the Banzhaf index is also susceptible to paradoxes. (a) Suppose we have a weighted voting system V (8; 5, 3, 1, 1, 1). Compute the Banzhaf indices for all five voters. (b) Now suppose the first voter gives up one of her votes to the second voter. So the new system is V (8; 4, 4, 1, 1, 1). Compute the Banzhaf indices again. What do you notice?
We notice that although the weight of voter A is decreased, its Banzhaf power increased. This suggests that the Banzhaf power is an indicator of power of a voter in relation to other voters in the weighted voting system.
Here are two more examples of computing Banzhaf Index featured on Youtube:
Banzhaf Method Example in Electoral College
Banzhaf Method Example in Electoral College
Consider the United States Electotal College...
There are a total of 538 electoral votes. A majority vote is considered 270 votes. The Banzhaf power index would be a mathematical representation of how likely a single state would be able to swing the vote.
There are a total of 538 electoral votes. A majority vote is considered 270 votes. The Banzhaf power index would be a mathematical representation of how likely a single state would be able to swing the vote. A state such as California, which is allocated 55 electoral votes, would be more likely to swing the vote than a state such as Montana, which has 3 electoral votes.
Let's do a simple example first. Suppose in the United States is having a presidential election between a Republican (R) and a Democrat (D). For simplicity, suppose that only three states are participating: California (55 electoral votes), Texas (38 electoral votes), and New York (29 electoral votes).
The possible outcomes of the election are as shown in the table 1.
The Banzhaf power index of a state is the proportion of the possible outcomes in which that state could swing the election. In this example, all three states have the same index: 4/12 or 1/3.
However, if New York is replaced by Georgia, with only 16 electoral votes, the situation changes dramatically as shown in table 2. In this example, the Banzhaf index gives California 1 and the other states 0, since California alone has more than half the votes (Wikipedia).
Table 1
Table 2
Banzhaf Method Example in European Economics Community
Banzhaf Method Example in European Economics Community
The European Economic Community (EEC) was a regional organisation that aimed to bring about economic integration among its member states. It was created by the Treaty of Rome of 1957.[note 1] Upon the formation of the European Union (EU) in 1993, the EEC was incorporated and renamed the European Community (EC). In 2009, the EC's institutions were absorbed into the EU's wider framework and the community ceased to exist (Wikipedia).
Look at the image carousel on the lower right corner of this section for example of Banzhaf Index calculation in the European Economic Community.
For further information regarding EU voting rules, power distribution in EU parliament, by political groups and council of ministers, check here and the two charts attached the bottom of this section.
Shapley-Shubik Power Index
Shapley-Shubik Power Index
Introduction
Introduction
The Shapley-Shubik power index finds how many times a voter is pivotal.
Recall that a pivotal voter is one that changes a losing coalition into a winning one after joining.
This differs from the Banzhaf power index because what matters is the order in which voters join a coalition. Under the Banzhaf index, {v1 v2 v3} is the same as {v3 v2 v1}. Under Shapley-Shubik, these are different coalitions.
The index can be written as:
The index can be written as:
Number of times voter vk is pivotal / total number of sequential coalitions
Remember that total number of sequential coalitions = n!
So, the SS index can be rewritten as:
So, the SS index can be rewritten as:
Number of times voter vk is pivotal / n!
Calculating the Shapley-Shubik Index
Calculating the Shapley-Shubik Index
Example
Example
Weighted voting system: V(16; 12, 8, 7, 3)
This means that there are 4 voters, v1, v2, v3, and v4, and there are voting weights are 12, 8, 7, and 3, respectively
The 16 means that the q = 16 ; 16 votes are needed for one candidate to be elected
Steps:
Steps:
Find the total number of sequential coalitions.
With four voters, the total number is 4! = 4 * 3 * 2 * 1 = 24
Find the sum of votes in each coalition in the order that the voters joined the coalition
Find the pivotal voters in each coalition (which voter cleared the quota of 16)
Calculate the power index of each voter using the formula, Number of times voter vk is pivotal / n!
The votes in blue represent the votes necessary to meet the quota. So, the last blue vote is the pivotal voter.
Another Example
Another Example
Weighted voting system: V(15; 9, 6, 3, 3, 3)
Remember that the first number, 15, represents the quota. Each number after represents the weighted vote of each voter in order. So v1 has 9 votes, v2 has 6, v3 has 3, v4 has 3, and v5 has 3.
Now, there are 120 sequential coalitions (5! = 120). Because the number is much higher, it would not be practical to list all 120 coalitions and find the pivotal voter in each one. Instead, we need to think about how powerful each voter is based on the quota.
1. Let’s start with v5, who has 3 votes. v5 can never be pivotal if it is the first or second to join a coalition.
In the first position, there will be only three votes.
In the second position, there will at most be 12 votes, if v1 is the first.
So, when is v5 a pivotal voter in the third position?
Only if v1 joins before v5 and v2 joins after. Why? Since v1 has 9 votes and v2 has 6, if both joined before v5, the quota of 15 would already be reached.
Therefore, v5 is pivotal in the third position in the following coalitions:
⟨v1, v3, v5, v2, v4⟩ , ⟨v1, v4, v5, v2, v3⟩ , ⟨v3, v1, v5, v2, v4⟩ , ⟨v4, v1, v5, v2, v3⟩ , ⟨v1, v3, v5, v4, v2⟩ , ⟨v1, v4, v5, v3, v2⟩ , ⟨v3, v1, v5, v4, v2⟩ , ⟨v4, v1, v5, v3, v2⟩
When is v5 a pivotal voter in the fourth position?
Only if v1 joins the coalition after v5. Why? V1 + any two voters will meet or exceed the quota of 15.
So, the coalition must look like ⟨v_, v_, v_, v5, v1⟩
Therefore, v5 is pivotal in the fourth position in the following coalitions:
⟨v2, v3, v4, v5, v1⟩ , ⟨v2, v4, v3, v5, v1⟩ , ⟨v3, v2, v4, v5, v1⟩ , ⟨v3, v4, v2, v5, v1⟩ , ⟨v4, v3, v2, v5, v1⟩ , ⟨v4, v2, v3, v5, v1⟩
When is v5 a pivotal voter in the fifth position?
Never. By the time v5 joins a coalition last, the quota will always already be exceeded.
So, v5 is a pivotal voter a total of 14 times.
2. V3 and v4 have the same number of votes as v5. So, all three have the same voting power. This means if v5 is pivotal 14 times, so are v2 and v3.
3. Next is v2. Again, v2 cannot be pivotal in the first position.
When is v2 a pivotal voter in the second position?
Only when v1 joins first.
There are 6 such coalitions:
⟨v1, v2, v3, v4, v5⟩ , ⟨v1, v2, v3, v5, v4⟩ , ⟨v1, v2, v4, v3, v5⟩ , ⟨v1, v2, v4, v5, v3⟩ , ⟨v1, v2, v5, v4, v3⟩ , ⟨v1, v2, v5, v3, v4⟩
When is v2 a pivotal player in the third position?
When v1 joins first or second. There are 12 of these coalitions.
When is v2 a pivotal player in the fourth position?
When v1 is the fifth voter to join. There are 6 of these coalitions.
When is v2 a pivotal player in the fifth position?
Never. By the time v2 joins a coalition last, the quota will always already be exceeded.
So, v2 is pivotal 24 times.
4. Lastly, we have v1. v1 is only pivotal when the other four voters are not. Instead of going through the steps like we did with v5 and v2, we can simply subtract what we have found so far from the total number of coalitions.
14 + 14 + 14 + 24 = 66
120 - 66 = 54
So, v1 is pivotal 54 times.
Power index:
V1 = 54/120 = 45%
V2 = 24/120 = 20%
V3 = 14/20 = 11.67%
V4 = 14/120 = 11.67%
V5 = 14/120 = 11.67%
Application - UN Security Council
Application - UN Security Council
You can use both the Banzhaf and Shapley-Shubik indices to look at the power of each member of the UN Security Council.
On the council, there are:
5 permanent members (U.S., China, England, France, Russia).
10 other countries that rotate
A measure passes if 9 members vote for it, but all 5 permanent members have veto power.
The voting system can be represented this way:
V(39; 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
To calculate the power indices for the UN Security Council, go here.
Conclusion - Major Take-Aways
Conclusion - Major Take-Aways
Learning about coalitions is important because in the rest of the world, in government and politics, coalitions play an integral role in countries’ legislatures.
The main difference between Banzhaf and Shapley-Shubik indices is that Banzhaf is determining how often a voter is critical in a coalition, whereas Shapley-Shubik is computing how often a voter is pivotal.
Suppose there are n voters in total, Banzhaf index looks at coalitions with 0 to n number of voters, Shapeley-Shubik index only looks at "sequential coalitions" with n voters. The number of total coalitions is 2^n in Banzhaf index, and n! in Shapley-Shubik index.
Computing power indices shows us the impact every voter has under a weighted voting system. In the United States, our Electoral College can be viewed as our weighted voting system. Each state is a voter, and their electoral votes are their weighted votes. We can use the Banzhaf index to find the power of each state in the presidential election. Check out the further resources section for more on this!
Page updated
Report abuse