Puzzles for Programmers and Pros

1.6. Pork Politics

A grant of a whopping 100 million dollars is available to the five districts making up a state. The districts have representation proportional to their population in the state assembly. District A has 35 representatives, district B has 25, district C has 16, district D has 14, and district E has 10.

If a coalition consisting of at least 51 members forms, then they can force the funds to come to their districts, where the money will be divided proportionally to the representation. For example, if the districts having 35 and 25 get together, they can force all 100 million to go to their two districts and that money will be divided such that (35/60) × 100 million goes to the district A and (25/60) × 100 million goes to B. Each district has only its own self-interest in mind.

1.6.1. Warm-Up

What would B most prefer?

1.6.2. Solution to Warm-Up

B prefers the coalition {B, C, E} to any other winning coalition, because B would get the fraction 25/55 of the money, whereas if B allied itself with A, it would get only 25/60 of the money.

1. Which coalitions might form?

The representatives of B have an ancient privilege. They can control the rules of when an allocation can take place. That is, they may require that an allocation require only a simple majority as we've assumed until now, but they can also demand that it require a 67% majority, or a 75% majority.

1. How strong ...