Selected topics in finite mathematics/Voting coalitions

A coalition of voters is a set of voters that all agree to vote in the same way.

Objectives

Some objectives include: 1. finding winning coalitions 2. finding minimal winning coalitions 3. finding a critical voter(s) 4. deciding if a motion can be passed or not

Details

A coalition of voters is a group of voters that all agree to vote the same way. A winning coalition is a group of voters that is guaranteed to win the election no matter how anyone else votes A minimal coalition occurs when each of the voter's vote is necessary for the group to win the election. If one voter were to back out, then the motion would fail to pass.

Examples

1. Suppose the US Senate has 49 Republicans, 49 Democrats, and 2 independents. Assume the Republicans form a coalition and the Democrats form a coalition. Then the minimal winning coalitions are {R, D}, {R, I1, I2}, {D, I1, I2}. Curiously, in this situation those two independent votes seem to be very influential.
2. In publicly held companies, the shareholders often have votes in proportion to the amount of stock they hold. However, many shareholders own few enough shares that they are dummy voters. Suppose a company is held by 12 people: A, B, C, D, E, F, G, H, I, J, K, and L. If E through L are dummies, then no minimal winning coalitions contain them. One possible set of minimal winning coalitions would be: {A, B, D}, {A, B, C}. In this case both A and B have veto power because they are in every minimal winning coalition. However, together A and B require the support of either C or D to pass a motion.

Homework

Consider the voting system give by [q:A,B,C,D]=[13:7,5,4,3]. Identify all coalitions. Which are winning coalitions?

Solution [ABD, ABC, ACD, and ABCD (there are no minimal winning coalitions) ]

Consider the voting system give by [q:A,B,C,D,E,F,G]=[13:6,6,4,2,1,1,1]. Identify all minimal winning coalitions.

Solution [{A,B,E}, {A,B,G}, {A,B,F}, {A,C,D,E}, {A,B,D,E}, {G,F,E,A,D}, {E,F,G,B,D}]