Coalitional Games

Prepared by:

Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk/

Many "games" that involving reaching decisions by groups of players are given in terms of coalitions that can take action or give weights for players that can be used to determine the coalitions that can take action.

Examples of such games are the way that decisions are reached by various "legislative" bodies of the European Union, County Boards of Supervisors in New York State, the Electoral College, procedures to pass laws in the United States, and the Security Council of the United Nations. In the European Union there are countries of very different sizes (Belgium versus Germany) so it does seem "fair" to just have each country have one vote. Rather it may be reasonable to have each country cast a block of votes, where the size of the block of votes is determined by the population and/or economic importance of the country involved. For the Security Council of the United Nations there are "veto players," players whose approval is required in order for an action to be taken but for action to be taken, a larger group of the "players" on the council must approve, beyond the group that have veto power.

Games of this kind are often described by giving the names of players and listing sets of these players, who by working together can achieve some action (goal).

So we might have a game where the players are A, B, C, D, E and the minimal winning coalitions, those groups of players who can take action are {A, B}, {B, C, D}, {B, C, E}, {C, D, E}. Any subset of these coalitions shown are no longer winning.

A different game might have the players 1, 2, 3, 4, read from left to right, who cast votes, in blocks, with the numbers indicated, where any coalition which has weight greater than the number to the left of the semicolon can take action: [13; 8, 7, 6, 5}. So the minimal winning coalitions are {1, 2}, {1,3}, {1, 4}, {2, 3}. Note that a superset of a winning coalition is a winning coalition. Thus, {1, 3} wins and so also does {1, 2, 3} and {1, 3, 4}.

It is easy to construct examples where the quota for a weighted voting game is set at the ceiling function of half the sum of the weights of the players, where a player D can have positive weight but belongs to no minimal winning coalition. Often in the weighted voting literature player D in this circumstance is referred to as a dummy. For situations where the weighted voting game is designed to provide a fair way to deal with players representing, say, countries with different populations, it would be desirable to assign weights to the countries so that the "power" of the players is proportional, by way of example, to the populations of the countries. (Or one might assign the weights so that the "power" was proportional to the gross domestic product of the different countries.) However, there are different ways to measure power of the players in a weighted voting game, and these different power indices differ in quantitative and qualitative properties. This raises the issue of which power index for a weighted voting game is the best. However, to begin with let us look at an example which allows us to see some of the kinds of things that happen when one constructs a mathematical model for power of players in a weight voting (or more generally, a voting game, specified by using the winning coalitions (or minimal winning coalitions) for the voting game). Although in many weighted voting games the quota to pass a bill is a "simple majority," there are voting situations where more votes are necessary for an action to occur. Thus, when amending the US Constitution a simple majority of the Senate or House is not good enough. Both parts of Congress must approve by 2/3 to have a new amendment to the Constitution pass. The President plays no role in the approval process, and after the Congress approves, the legislatures of 3/4 of the states must approve, so it is not easy to change the US Constitution.

Suppose there are three parties in the 100 seat legislature with 5, 45, and 50 seats, where I will call the parties, with these numbers of seats 1, 2, and 3. This game can be represented at: [51; 5, 45, 50] but notice it is the same game as [51; 50, 45, 5}. Just as in other parts of mathematics one can have voting games that have different descriptions but turn out to be "isomorphic."

Perhaps the simplest way to compute power for the players in this game is to start by listing the minimal winning coalitions. These coalitions are {1,3} and {2,3}. Counting the total number of appearances of players in these minimal winning coalitions we get 4, and of these 1 and 2 appear once and 3 appears twice, so we assign 1 and 2 a power of 1/4 and player 3 a power of 1/2. Sometimes this power "index" is referred to as the Coleman Index, for James Coleman, the distinguished American sociologist.

Here is another approach to voting power. When a vote is taken on a "bill" each of the parties can vote yes or no on the bill, and since there are three parties we can prepare a table of the 8 patterns of the three "players" voting yes or no on the bill:

YYY
YNY
YYN
YNN
NYY
NYN
NNY
NNN

where, for example, YNN means that party 1 supported the bill but the other two parties did not.

Which lines of the table result in the bill passing? We need to have lines where the Yes votes sum to at least 51.

So this happens for:

YYY
YNY
NYY

YYN cannot pass the bill because 5 votes from 1 and 45 votes from 2 only give a total of 50 points, not enough to equal or exceed the quota of 51.

These three "strings" represent situations where there was a coalition of players that passed a bill.

Now, consider for example YYY. Suppose player 1 had vote N instead of Y. The bill would still have passed, so player 1 was not critical for this coalition. However, if player 3 had changed from Y to N, the bill would not have passed. So player 3 is "critical" for this pattern of voting. I will indicate which voters are critical for a given line by using an * to the right of the vote they gave. Thus:

YYY*

shows the pattern of critical players for this line, namely, voters 2 and 3 were critical. For the other two ways the bill could pass here is here is the coding of the critical players:

Y*NY*
NY*Y*

so summarizing for the original three ways a bill could pass>

YYY*
Y*NY*
NY*Y*

What is called the Banzhaf power for the players can now be constructed for this example. We count the total number of critical players, which is coded by the 5 asterisks above, and count for each player how many of the asterisks that player contributed. Some rows can have more than one asterisk.

so we get b1 = 1, b2= 1 and b3 =3. So players 1 and 2 are tied with 20 percent of the power each while player 3 has 60 percent of the power. Though players 1 and 2 have different weights they have the same power, and this seems reasonable because they appear in the minimal winning coalitions in a symmetrical way.

You might ask why, in the analysis above, we did not look at the lines where the bill failed, and see if a player by changing an N vote to a Y vote, could get the bill to pass. It turns out that all that happens here is that we "double" the results of what happens for the analysis we did, so the approach used does the job of providing a "power index" for the voting game.

Another approach to voting power is due to Lloyd Shapley and Martin Shubik. The idea here is to look at the different orders of the players voting. Since there are three players there are six such orders:

123
132
213
231
312
321

We will assign for each row one of the players reading from left to right when the sum of the weights of those players first reaches the point where that group of players can make the bill pass.

For example, in the row 123, 1 by itself can't pass the bill, nor can 1 and 2 (only 50 points), so 3 gets a "pivot" point. I will indicate the pivot point for each row with an asterisk after the player who is pivotal for that order. Note that unlike what may happen for the Banzhaf Power Index, each row has exactly one asterisk.

123*
13*2
213*
23"1
31*2
32*1

So the powers are s1 = 1/6, s2 = 1/6 and s3 =2/3.

There is another power index (and you can practice it after the next example on the example above) where the fact that some minimal winning coalitions have different sizes comes into play.

Example 2:

Suppose parties 1, 2, 3, 4, 5 have 35, 20, 15, 15, and 15 seats respectively in the 100 seat legislature. The minimal winning coalitions are listed "lexicographically" below:

12
134
135
145
2345

For each player and coalition we weight the presence of a player in that coalition and take into account the number of players in the coalition.

For example the power of player 1 is 1/5(1/2 +1/3+1/3+1/3) = 18/60.
Player 1 is not a member of the last coalition so no contribution to player 1's power results from that coalition.


The 1/5 reflects the fact that there are 5 minimal winning coalitions, and we would like in the end the total power of all the players to add to 1. You can write the power of the players in these indices as either fractions or percentages.

The power for player 2 is: 1/5 (1/2 + 1/4) = 9/60

Note that player 2 is only a member of two winning coalitions and the sizes of these two coalitions are 2 and 4.

Proceeding in this way we see that the players 3, 4 and 5 have power:

1/5(1/3+1/3+1/4) = 11/60.

This index is known as the Deegan-Packel Index. Note that party 2 while holding 20 seats has less power under this index than the three parties with 15 seats. This reflects the fact that the players with smaller weights can enter into groups which win in more ways, perhaps giving them more "power."

Note that something similar happens here for the Coleman Index where the powers are (4/15,/2/15,/3/15, 3/15, 3/15).

Notice that computing the Banzhaf Index and Shapley-Shubik Index requires a lot of computation here since there are 32 patterns of yes and no and 120 permutations of the numbers 1 to 5. The results (percentage power) are 44, 20, 12, 12, 12 for the Banzhaf Index, and 45, 20, 11..67, 11.67, 11.67 for the Shapley/Shubik Index.

While the analysis so far has indicated a variety of different ways to compute power for players in a weighted voting game or voting game, there is also the question of trying to understand the dynamics of what coalitions might actually emerge and why. One can ask which coalitions are likely to form in an environment such as that of the game above.

In the dynamics of coalition formation for parties in Europe the results often reflect some sense of the right wing versus left wing nature of the parties. Suppose that it is possible to order the parties in a way from left to right in terms of the way they are perceived by the public and members of the parliament itself.

Suppose we have 5 parties that have sizes 22, 15, 18, 25, and 20 seats which adds up to 100, and to pass a bill requires 51 votes.

We will assume the names of the parties are A, B, C, D, and E and their "rank" in terms of being left/right is that A is the leftmost party, with rank 1 and E is the least leftist, or rightmost party with rank 5. We can now assign a "distance" function between two parties, known as Leiserson distance, as follows. First we compute the number of parties between two parties. So the number of parties between CD or DE is 0, while for BD there is one party between BD. Now, we count the number of steps that have to be moved to get from one party to another. For BC this number is one, but for AE the number of steps is 4. Now to get the distance between two parties we sum these two numbers. Thus, d(A,C) is 3, since there is one party between A and C and to get from A to C requires 2 steps. The value of d(A, E) = 7. We can also compute the distance associated with a coalition. Thus, d(ACD) = d(A,C) + d(C,D) = 4.

What are the winning coalitions for this game?

Here are these coalitions listed in order of number of players, and in increasing size of the number points that the coalition controls:

ABCDE (100)

ABCD (80), ABCE (75), ACDE (85), BCDE (88)

BCE (53), ABC (55), ABE (57), BCD (58), ACE (60), BDE (60), CDE (63), ACD (65), ABD (66), ADE (67)

Not all of these are minimal winning coalitions. Here is the list of minimal winning coalitions.

BCE (53), ABC (55), ABE (57), BCD (58), ACE (60), BDE (60), CDE (63), ACD (65), ABD (66), ADE (67)

You may want to think about the question of whether a minimal coalition with a larger or small number of votes is likely to form when the two minimal coalitions have the same number of parties.

Some might argue that a coalition is more likely to form when it has a small number of total seats that are good enough to pass a bill. In the example above this would suggest that BCE is a "good bet" to come into existence.

The above discussions did not take into account the left right distribution of the parties. So one might using this idea think that the coalitions might form which have small distance in the "left-right" sense. Thus, ABC (55), BCD (58) and CDE (63) have distance 2, While BCE has fewer members it has a larger distance, namely 4.

In situations where one can see what happens to a real system on an historical basis one can try to use this data to see which of the different principles seems to be what occurred in practice.

When a person is participating in a voting game it is sometimes hard to tell how much influence the person has, so if the game has a representation as a weighted voting game that is helpful to the players involved.


References

Cortona, P. and C. Manzi, A. Pennisi, F. Ricca, B. Simeone, Evaluation and Optimization of Electoral Systems, SIAM, Philadelphia, 1999.

Taylor A, and W. Zwicker, A characterization of weighted voting. Proceedings of the American mathematical society., 115 (1992)1089-94.

Taylor, A. and W. Zwicker, Simple games: desirability relations, trading, pseudoweightings. Princeton University Press, 1999.