Homogeneous Weighted Majority Games

Voting power in political and other decision-making bodies can often be represented by a simple game. For instance, in a parliamentary democracy, the players in the game are the political parties, which can form coalitions: a coalition is winning if it has a majority of seats, and losing otherwise. Also shareholders in a firm can form coalitions, where a coalition is winning if it has a qualified majority of shares, and losing otherwise.

In general, given a set of players N = {1, 2, …, n}, a simple game is defined by identifying which coalitions—that is, subsets of N—are winning. All other coalitions are losing.

A weighted majority game (WMG) for the set of players N is a simple game that can be represented by an array [q; w1, …, wn], where the weights w1, …, wn are nonnegative integer numbers and the quota q is a positive integer number greater than (w1+ … +wn)/2, such that a coalition of players is winning if the sum of the weights of its members is at least q, and losing otherwise. Such an array [q; w1, …, wn] is a representation of the WMG, but this representation is not unique. For instance, the three-player games [9;8,7,2] and [2;1,1,1] represent the same WMG because the sets of winning coalitions are identical. The latter representation seems much more attractive and adequate because (a) it uses minimal weights—thus, numbers of seats, or votes—to describe the same situation in terms of voting power, that is, the same simple game and (b) each minimal winning coalition (i.e., each winning coalition from which no player can be dropped without making it losing) has the same total weight, which is, moreover, equal to the level q.

More generally, a representation [q; w1, …, wn] of a WMG is homogeneous if the total weight of each minimal winning coalition is equal to q. A WMG is homogeneous if it has a homogeneous representation. A representation [q; w1, …, wn] of a WMG is minimal if the total weight sum w1+ … + wn is minimal among all representations of the WMG under consideration. Axel Ostmann has shown that each homogeneous WMG has a unique minimal representation. This representation is itself homogeneous and assigns equal weights to symmetric players. (Players i and j are symmetric if adding player i to any coalition not containing i and j has the same effect as adding player j.). Moreover, dummy players—that is, players that never make any difference—get weight zero, and the least powerful non-dummy players get weight 1. Ostmann provides a simple algorithm to compute this minimal representation.

In the special case of a strong WMG—that is, one in which a coalition is winning if and only if its complement is losing—we have the (intuitively obvious) result that q = (w1+ … +wn+1)/2 in a minimal representation. If such a game has no dummy players, then every representation is a multiple of the minimal representation, which is generated by the nucleolus of the game.