Setting up this definition will take a bit, bear with me.
The problem: Shapley-Shubik Voting Power. This is problem MS8 in the appendix.
The description: Suppose we have a set of n voters, each voter i has a “weight” wi, corresponding to their number of votes. If we are doing a simple majority vote, a coalition of voters then needs votes of (strictly) more than half the sum of the weights to win. For a specific voter i, we can look at all permutations of voters, and say that all voters before voter i in the permutation voted “yes”, and all voters after voter i in the permutation voted “no”. We are interested in the number of these permutations where voter i’s vote “matters”- where adding voter i to the “yes” votes makes “yes” the majority, but adding them to the “no” votes makes “no” the majority. We call voter i a pivot player if this is the case.
Is voter 1 (in the G&J definition, it’s voter N in the paper) ever a pivot?
Some clarifications: The number of times a voter is a pivot is the “Shapley-Shubik voting power”, and the proportion of permutations the voter is a pivot (by dividing the count by N!) is the “Shapley-Shubik power index”, but all we care about here is whether the power is non-zero.
Also, the definition of the voting game (in G&J, and also in the paper) allows for a more general definition of winning, besides a simple majority- you can supply a “quota” q, and any amount of votes ≥ q is a winning coalition. For us, q is set in the reduction to be 1/2 the sum of the weights, +1, rounded up.
Example: Suppose we had 4 voters, with weights: 5.4,3,1. There is 13 total weight, and 7 weight is enough to win. Voter 4 has 0 coalitions in which they are the pivot (we would need 6 votes without them), so has “zero Shapley-Shubik voting power”.
If, however, we split up the same number of votes among 5 voters: 4,3,3,2,1, then the 1-vote voter can be a pivot with (among others) the 4 and the 2. The coalition loses without our pivot voter but wins with them.
Reduction: G&J have this as an “unpublished results” problem, but luckily I found a paper by Matsui and Matsui who solved it. So we start with Partition. We’re given a set A of n integers. We will create a set of weights with one weight equal to each element of A, and add one extra voter with weight 1 at the end. This is the voter that may or may not be a pivot.
If this last voter is a pivot, then there is a coalition that needs an additional weight of 1 to become a majority. This means the coalition had exactly half of the votes without this voter (and so the sum of the elements is a partition of A)
In the other direction, if the set has a partition, then the partition set’s votes is equal to exactly half of the votes, one short of a majority. Adding our 1-weight voter will make it a majority, and thus that voter is a pivot.
Difficulty: 4. This problem looks scary because the definitions of Shapley-Shubik voting power include a lot more than what you actually need to do this reduction. Once you get past all of that, it’s actually a pretty nice problem that students can handle.