Feature Column from the AMS

Voting Games: Part I

3. Basic mathematical ideas

When mathematics is applied to a real-world situation, one needs to abstract and simplify the most important aspects of the situation to get insight. In the case of weighted voting it is convenient to have a name for a group of players who come together to achieve a common goal. We will use the term coalition for such a group.

For simplicity we will assume that the weights cast by players are nonnegative integers. However, there are interesting mathematical issues involved in whether or not it makes any difference to use more general weights. Furthermore, since we have a voting situation in which decisions will be made on the basis of the groups of players who come together to cast votes, we need to know how we can tell when a group of players can "get their way." One way to do this is to just specify a list of all those groups of players who, when they work in concert, can "win." This, however, does not take advantage of the numerical weights assigned to the players, and the list of groups that can win may be very, very long. A more practical way involves a positive integer quota Q. One way to produce Q is to have it set at one-half the sum of the weights, add 1, and if the sum is not an integer, round down to the nearest integer. However, for some situations, where one wants to make it hard to change from the status quo, the quota might be set higher than this "simple majority" level. For example, amending the U.S. Constitution requires more than a simple majority and in many legislative bodies certain kinds of action (e.g. approval of a treaty) require more than a simple majority. However, as we saw with examples such as the United Nations Security Council, it is not clear when voting games can be represented as weighted voting games.

In light of these ideas it is natural to define the idea of a simple game. We are given a collection of people P, the players in the game, and a collection of subsets W of these players. The sets in W are known as winning coalitions. The intuitive idea is to think of W as those sets of players that can accomplish their goal in a voting situation. It is natural to assume a monotonicity axiom, that is, if X is a member of the set of winning coalitions W, then any set Y that contains X is also in W. The motivation is that having more players in a group that can already accomplish its goal can do no harm in terms of "winning." A subset of players which is not winning is called losing. Of special interest are those winning coalitions, denoted MW, which have the property that removing a single player from such a coalition changes it from a winning coalition to a losing coalition. Such coalitions are known as minimal winning coalitions.

The definitions above are very general. The definition we have given for a winning coalition does not preclude that if some coalition C is winning, the coalition of players not in C is not a losing coalition, even though in most but not all real world situations this would usually be the case. An example of a situation where one can have a winning coalition whose complement (i.e. elements not in this coalition) contains a collection of players who can also win is in the procedure that the United States Supreme Court uses to approve certain cases it wants to have brought before the Court. Only 4 justices are needed to approve such a request. Thus, the complement of a winning coalition can also contain a winning coalition.

In light of the fact that there are so many situations that involve voting and decision making, political scientists and the lay public have developed many terms that capture special aspects of either the players in such games or their coalitions. For example, people talk about dictators, veto players, and blocking coalitions. These terms can be given meaning within the framework of voting games. For example, a dictator is a person who can "win" without the assistance of other players. So if a voting game has a minimal winning coalition with a single player, the player in that coalition is a dictator. However, unless there is a rule preventing this, there may be more than one dictator in a game. Several minimal winning coalitions might consist of a single player. If one is interested in a kind of game where this would not be possible, one would have to make an assumption which rules out having more than one minimal winning coalition with a single player.

What is the intuitive meaning of a veto player? This is someone without whose approval one can not win. This idea can be captured by saying that a player is a veto player in a game if that player is a member of every minimal winning coalition. Can a voting game with two dictators (weird thought, right?) have a veto player? If one is not content with the relationship between definitions one has made, one must either change the definition or restrict the kinds of games one wants to deal with.

Another common term in voting is the idea of a blocking coalition. The intuitive idea here is that one has a collection of players who are not winning yet can prevent any other collection of players from being a winning coalition. Based on this intuition one can formalize the definition of a blocking coalition. After defining these words one can try to find interesting examples or prove theorems involving these concepts. The important thing to notice is that mathematics often provides unexpected insights by examining situations that seem artificial. Another reason for sometimes allowing general structures that may not occur in the real world is that it is often easier to prove general assertions, which may allow for things that one may not see in practice, than to prove assertions restricted only to the cases one sees in practice! Although this is not used in common parlance, if a voting game has a player who is not the member of any minimal winning coalition, the player is known as a dummy. A dummy may have influence on other players in terms of their behavior, but there is no voting pattern where the dummy's presence or absence makes any difference.

Notation is often a handmaiden of mathematical progress. For weighted voting games the following notation has become increasingly standard. One denotes the players by 1, 2, ..., n, and the weights they cast by w₁, w₂, ..., w_n. If the players, without loss of generality, have been named so that the weights are in decreasing order we can write:

Given a weighted voting game in this form it is a straightforward process to write out the winning coalitions and minimal winning coalitions for the game.

Example:

Consider the game:

which has three players who cast 4, 2, and 1 vote(s), respectively. If we set the quota Q at the "majority" level, namely, 4, then we have the following collection of minimal winning coalitions: {1}! So the game has a dictator in the sense that there is no minimal winning coalition with more than one player, and that player 1 by him/herself constitutes a minimal winning coalition. Players 2 and 3 are dummies in this game because they are not members of any minimal winning coalition. Even though it is not perhaps of much "political interest," it is of mathematical interest to note that as the value of Q varies from 1 to 7 one gets a different set of minimal winning coalitions each time (and one might even want to consider the "degenerate" game where the quota is zero!).

Q = 1; minimal winning coalitions: {1}, {2}, {3}

Q = 2; minimal winning coalitions: {1}, {2}

Q = 3; minimal winning coalitions: {1}, {2, 3}

Q = 4; minimal winning coalition: {1}

Q = 5; minimal winning coalition: {1,2}, {1, 3}

Q = 6; minimal winning coalition: {1,2}

Q = 7; minimal winning coalition: {1, 2, 3}

Note that because the players' vote totals are different powers of 2 and every number between 1 and 7 has a unique representation in the binary number system, we get a different set of minimal winning coalitions for each number from 1 to 7. One can generalize what happened here to games with four players where the weights are the powers of two. This idea allows one to get a lower bound on a count for the number of "different" weighted voting games with n players.