Minimal Winning Coalition

In a simple game, a minimal winning coalition (MWC) is a winning coalition that would become losing if any member left. Although the idea of MWC surely goes back a long way, the formal concept was introduced into game theory in 1944 in the fundamental book by John von Neumann and Oskar Morgenstern. In 1962, William Harrison Riker introduced the idea of MWC in his study of the formation of political coalitions as an alternative to the view of vote maximization expressed by Anthony Downs in 1957. The MWC concept is essential to the Public Goods Index introduced by Manfred J. Holler and also essential to the Deegan-Packel Index.

A simple game may be described by the list of coalitions (subsets of players) that are winning, where this list satisfies these conditions:

• 1.
  the empty coalition (of no players) is losing;
• 2.
  the coalition of all players is winning; and
• 3.
  if coalition S is winning, any more inclusive coalition (i.e., any superset of S) is also winning.

A coalition S is a minimal winning coalition if (i) S is winning, but (ii) the loss of any member converts S into a losing coalition. Given the [Page 423]superset property above, a simple game can be more concisely described by the list of its minimal winning coalitions. Therefore an MWC is a winning coalition that does not include any other winning coalition. A player who belongs to every MWC is called a veto player (or blocker). A player who by himself constitutes the sole MWC is a dictator. A player who does not belong to any MWC is a dummy. A dummy player is a player who does not play an essential role in the game.

MWCs take on notable importance in weighted majority games in which every player can be assigned some numerical weight and a numerical quota can be fixed such that a coalition is winning if and only if the total weight of its members equals or exceeds the quota.

Suppose that a parliament has 100 seats distributed thus: 50 for party A, 30 for party B, 15 for party C, and 5 for party D. If the quota is 51 (i.e., simple majority rule), no party can decide alone. Party A, however, has a clear advantage in that it belongs to every winning coalition (A is therefore a veto player). Each of the others needs to form a coalition with A, as a coalition between B, C, and D would still be losing. On the other hand, A can obtain nothing alone, as it does not have a majority on its own. The winning coalitions are therefore: {A, B}, {A, C}, {A, D}, {A, B, C}, {A, B, D}, {A, C, D}, and {A, B, C, D}. But not all of these are MWCs: for example {A, B, C, D} would still be winning even if D left. The MWCs of this game are: {A, B}, {A, C } and {A, D}.

To understand the role of MWCs in determining certain power indices, consider the Public Goods Index for this game. This index is based on the number Mi of MWCs each player belongs to, and the power of each player i is given by Mi divided by the sum of the Mi values over all players. In this example, party A belongs to all minimal winning coalitions, so MA = 3, while parties B, C, and D belong to only one minimal winning coalition each, so MB= MC= MD= 1. Thus the power assigned to parties A, B, C, and D are 3/6, 1/6, 1/6, and 1/6, respectively. Note that equal power is assigned to the three smaller parties, even though they have very different numbers of seats.

...