Voting Power

Attribution: This assignment was designed by Julie Zelenski

🖐🏿🖐🏼 Be counted!🖐🏻🖐🏽

Stanford Votes

"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 U.S. 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 U.S. electoral system, California has a block of 55 votes while New Mexico has 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!

Consider all possible ways in which n voting blocks could vote in a given election. One measure of a block's importance or voting "power" is the number of election outcomes (out of 2^n total possible outcomes) in which that block's vote is critical. A critical or swing vote is one that changes the election result. The count of outcomes in which a block has a critical vote is used to compute the Banzhaf Power Index, a measure of voting power that a given block has within a voting system.

Banzhaf Power Index

Define a coalition to be a group of blocks that all votes the same way in a specific election. For a given voting block B, we count the situations (outcomes) in which B is a critical voter by identifying winning coalitions in which B can participate but in which the coalition will not win if B does not join. That is, B supplies the critical vote that is 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 result. 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 is.

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 critical votes that the block has out of all total 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. For example, this system has 5 total critical votes of which Lions have 3, so Lions control 3/5 or 60% of the critical votes. The table below shows all of 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 more voting power than the Tigers. Apparently, the lion's share of the votes really does go the Lions! (sorry… we could not resist)

Your task

You are to write the function

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

which 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 output returned by the function is a Vector of size N with the Banzhaf power indexes 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 the target. As you form a coalition, you do not need to store a collection of the participating blocks, just tally the amassed vote total for each coalition.
• Once a coalition is formed and its votes are summed, consider the impact of the target block's vote. Without the target block does the coalition lose, and with the target block, does the coalition win? If the answer to both of these questions is yes, then the block is a critical voter for that coalition.
• Repeat the exploration for every block in the system to count each block's 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 5 or more different sizes. Choose sizes so that the largest operation completes in under a minute or so.

Answer these questions in short_answer.txt:

Notes

• Ties. To win the election, a coalition must earn a strict majority of the votes. A tie is not considered a winning coalition.
• Rounding. We calculate the power index as an integer which is a rounded value (well, to be more correct about what happens, the decimal portion is truncated). The sum over all blocks may be less than the total 100% because of this truncation.
• The recursive insight is the classic include/exclude 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.
• 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 coalition is going to win regardless of whether or not the target block participates, there is no need to further explore that path. The target block cannot be a critical vote in this coalition.
  • 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!
  • Furthermore, do not attempt to first construct the full power set of all coalitions (subsets) and then process the coalitions. Given a voting system with even a modest number of blocks, this would consume a prohibitive amount of memory. Instead you must explore the coalitions one at a time: assemble a coalition, test it, and then un-choose and backtrack to consider other choices in forming another coalition. At any one time, there is only one coalition being formed/stored.
• Duplicates/re-calculating. Two or more blocks in a system can have the same number of votes; the number of critical votes for blocks with equal numbers of votes will be the same. You do not have to do something clever to avoid this repetition; you may compute the number of critical votes for each block anew. If you are eager to be clever about it, consider tackling the extension.
• Helper/wrapper functions. There is a firm requirement that the function computePowerIndexes is implemented to exactly match the prototype above. You are free to add additional helper/wrapper functions of your design with whatever parameters you like.

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.

Extension

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.