Assign4: Banzhaf Power Index

"It's not the voting that's democracy; it's the counting." – Tom Stoppard, Jumpers

Block voting systems

It's said that "every vote counts", but does every vote count equally? A block voting system such as the US Electoral College makes for an interesting case study in analyzing the relative voting power of each block in a system where blocks have different weights.

In a block voting system, each block has an assigned number of votes, and the votes for one block are cast in unison. In the US electoral system, California has a block of 55 votes to New Mexico's 5. You might ask: does this mean that California wields 10 times the influence of New Mexico in affecting the election outcome? Let's explore further!

One measure of a block's importance or voting "power" is the count of election outcomes in which that the block's vote is critical. A critical or swing vote is one that changes the election outcome. The count of critical votes is used in computing the Banzhaf Power Index, a measure of voting power in a block voting system.

Banzhaf Power Index

For a given voting block B, we count the situations in which B is a critical voter by identifying those winning coalitions in which B can participate but the coalition would not win if B does not join; that is, B supplied the critical vote that was able to swing the election.

Consider this example system of three voting blocks:

First let's enumerate the possible ways a voting coalition could shape up: Lions+Tigers+Bears, Lions+Tigers, Lions+Bears, Tigers+Bears, Lions, Tigers, Bears.

Assume winning an election requires a strict majority. This system has 100 total votes, so a winning coalition must amass 51 or more votes to have a majority.

Of these seven possible coalitions above, three are winning coalitions: L+T+B, L+T, and L+B.

Now, for each winning coalition, consider which of its blocks are a critical voter:

• Lions is a critical voter in L+T+B, L+T, and L+B
• Tigers is a critical voter in L+T
• Bears is a critical voter in L+B

A block is a critical voter if its support for the coalition changes the outcome. A winning coalition would no longer be winning if a critical voter left the coalition. Note that Lions is a critical voter for the coalition L+T+B, but neither Tigers nor Bears are.

Counting the critical votes for each block gives us the following data:

The Banzhaf Power Index expresses a block's voting power as the percentage of situations in which this block is a critical voter. This system has 5 total critical votes of which Lions have 3, so Lions control 3/5 or 60% of the critical votes.

To convert from the count of critical votes to the Power Index, total all critical votes in the system, and compute the percentage of each block's critical votes. The table below shows the power indexes for the sample system:

The power indexes for all blocks sum to 100%. Comparing relative percentages shows the difference in voting power among the blocks.

Tigers and Bears have equivalent voting power, despite the Tigers' much larger block count. The small uptick in block count for the Lions gives it three times the voting power the Tigers. Apparently the lion's share of the votes really does go the Lions! (sorry… I could not resist)

Your task

You are to write the function

Vector<int> computePowerIndexes(Vector<int>& blocks)

that receives a Vector of size N containing the block counts for a block voting system. The function counts critical votes to determine the voting power per block. The result returned from the function is a Vector of size N with Banzhaf power index for each block. For example, calling computePowerIndexes on the vector of block counts { 50, 49, 1} returns a vector of per-block power indexes { 60, 20, 20 }.

Although the explanation above describes the process in terms of first finding coalitions and then determining which participants are critical, the actual code is easier to structure by instead proceeding to count the critical votes specific to a target block and repeating that process for all blocks.

• Set aside the target block and recursively explore all the subsets(coalitions) that do not include target. As you form a coalition, you do not need to store a collection of the participating blocks, just tally the amassed vote total.
• Once a coalition is summed, consider the impact of the target block's vote— will its choice to join the coalition be necessary and sufficient to give the win? If so, then the block is a critical voter.
• Repeat the exploration for every block in the system to count its critical votes.
• Once you have the counts of critical votes for all blocks, the conversion to percentage is simple looping and arithmetic.

After testing and debugging your function, predict what you expect to be the Big O of the computePowerIndex function. Then use the timing operation to measure the execution time over 4 or more different sizes. (There is information on how to use SimpleTest for timing in the merge task writeup). Choose sizes so that the largest operation completes in under a minute or so. Answer these questions in short_answer.txt:

• Q13. Include the data from your execution timing and explain how is supports your Big O prediction for computePowerIndex.
• Q14. Use the timing and Big O to predict how long it would take to compute the power index for the 51 voting blocks in the US electoral system.

Notes

• Ties. To win the election, a coalition must earn a strict majority of the votes. A tie is not considered a winning coalition.
• Helper/wrapper functions. Our starter code includes prototypes and test cases for some recommended helper functions. You may also use additional/different helper/wrapper functions of your design with whatever parameters you like. The only firm requirement is that the function computePowerIndexes is implemented to exactly match the prototype above.
• The recursive insight is the classic in/out pattern used for subset exploration. Starting with similar code you've seen in lecture/section/warmup will be a good start, but you'll need to modify some of the details to add the housekeeping and counting required for this problem. Adapting an existing recursive solution to solve a slightly different problem is a great way to build your recursive mastery.
• Two or more blocks in a system can have the same block count; the number of critical votes for equal blocks will be the same. You do not have to do something clever to avoid this repetition, you may compute for each block anew. If you are eager to be smarter about it, try the extension below!
• Efficiency. The exhaustive recursion to try all subsets is computationally expensive. Here are a few things to tame its resource-hungry nature:
  • As soon as it is apparent that a forming coalition is going to win regardless of whether the target block participates, there is no need to further explore that path. It is not a critical vote for target.
  • Be thoughtful about use of ADTs and take care to avoid unneeded copy operations (expensive!). A data structure is copied when passed by value (not reference) or returned from a function. A few copies here or there is no problem, but making a copy on every single recursive call of the entire exploration? No bueno!

References

• The Banzhaf Power Index originated in a lawsuit raised by John Banzhaf challenging the fairness of a block-voting system used in Nassau County, New York. He argued that the system with block counts of {9,9,7,3,1,1} disenfranchised the three smallest blocks, as they never cast a critical vote and had zero voting power! Wikipedia: Banzhaf Power Index
• Banzhaf making recent news as applied to analyzing blockchain voting systems.

Extensions

• Exponential problems can be a tough nut to efficiently crack. The approach we are using to solve the problem repeats many calculations, which further bogs it down. Research how you could apply techniques such as memoization, dynamic programming, or generating functions to achieve a more efficient implementation.