Tag Archives: Difficulty 4

Shapley-Shubik Voting Power

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.

Protected: Permutation Generation

This content is password protected. To view it please enter your password below:

Protected: Register Sufficiency For Loops

This content is password protected. To view it please enter your password below:

Protected: Context-Sensitive Language Membership

This content is password protected. To view it please enter your password below:

Protected: Linear Space Acceptance

This content is password protected. To view it please enter your password below:

Protected: Integer Expression Membership

This content is password protected. To view it please enter your password below:

Protected: Unification for Finitely Presented Algebras

This content is password protected. To view it please enter your password below:

Protected: Unification With Commutative Operators

This content is password protected. To view it please enter your password below:

Protected: Comparative Vector Inequalites

This content is password protected. To view it please enter your password below:

Protected: Staff Scheduling

This content is password protected. To view it please enter your password below: