Prepared by:
Joseph Malkevitch
Mathematics Department
York College (CUNY)
Jamaica, NY 11451
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk/
1. When one describes a voting game just with a verbal description, or even with the minimal winning coalitions for the voting game, it may be difficult for the players who are participating the in game to see the "power relationships" of the players. Here I am not talking about the power that comes with your name (e.g. people who are named Kennedy in the American Congress may get more attention than they deserve) but as a consequence of the structure of the voting game. If one can represent the voting game using weights, the weights may provide the players clues to the power relationships. Of course, one could give the players the value of their power in the game (assuming that the computation of that number can be carried out). However, there are many power indices and which of the different power indices should the players believe are the "true" ones? If the game is a weighted voting games, of the many weights that one might be able to use for the same game one could use weights where the weights were proportional to the power of the players with respect to a particular power index. To the best of my knowledge it is an open question, for example, to determine for which kinds of weighted voting games the weights of the game can be chosen so that the weights are proportional to, say, the Banzhaf Power of the players.
2. How can one tell if a voting game has a weighted voting representation? Thus, even though the Security Council Game is not usually described in terms of a weighted voting game, it can be. It can be represented [ 39; 7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]. Alan Taylor and William Zwicker have a beautiful theorem that answers this question completely, at least from an "existence" point of view. The major insight they had was that if one has two winning coalitions a voting game, and the coalitions exchange some players to create new coalitions, that if both of these new coalitions are losing, the game can not be a weighted voting game.
Here is some information related to what they accomplished.
One begins with this definition.
Definition: A voting game is called k-trade robust if one is unable to convert a sequence of k winning coalitions (which need not be distinct) into a sequence of some other k (not necessarily distinct) losing coalitions using a series of trades of players (where the groups of players exchanged can have different sizes) between pairs of coalitions. A game is called trade robust if it is k-trade robust for all values of k.
Taylor and Zwicker prove the following truly remarkable theorem:
Theorem: If G is a voting game with n players the the following 3 conditions are equivalent to each other:
1. G can be represented as a weighted voting game.
2. G is trade robust
3. G is
- trade robust.Taylor and Zwicker also consider what can be accomplished when players are switched in pairs.
As an application of the theorem above one can show:
a. The voting rules to amend the Canadian Constitution can not be represented as a weighted voting game
b. The procedure to pass legislation in the United States (which sometimes involves the approval of Congress and the President but can still be carried out without the approval of the President) can not be represented by a weighted voting game.
Is there a way of telling that one voting game is more "complex" than another? The concept of the "dimension" of a voting has been developed to do this.
Although we have barely touched the surface of the mathematical and applied questions involving voting games we will turn to another class of fairness questions which have both mathematical and applications ramifications.
3. The basic model is that we have a collection of claimants ci, where the "strength" of the claim of ci is measured by a number pi. The claims are being made against an integer quantity h, often referred to as the "house size." If one denotes by ai also an integer, the amount given to ci, then the sum of the ai's must be h. The natural approach to this problem if integers were not involved might seem straight forward: give each claimant the percentage of h that is "deserved" based on pi. However, this can not be done due to the presence of fractions. (However, we will see with other fairness models to discussed in the future, many people would dispute the "naturalness" of the proportionality solution in other settings.)
Here are two different situations where apportionment problems arise. One situation involves the claims that each state in the United States has for seats in the US House of Representatives. Now, the number of such seats h is set by law as 435. (Just recently it has been proposed to raise this number so that residents of the District of Columbia, who now have no voting representative(s) in Congress would be given representation in the House of Representatives.) The number of seats a state gets is distributed based on the populations of the states determined by the census. One requirement of the problem is that each state be given at least one seat. How many seats should be given to each state?
Another setting arises in many European democracies. Here, often voters vote for parties rather than individual candidates in "districts." If the size of Parliament is h, how many seats should each party get based on the claims of the portion of the vote each party gets?
4. Problems of this kind are called apportionment problems. Let us illustrate some approaches to this question in the case of apportioning the seats in the United States House of Representatives. Suppose we use P to represent the sum of the populations pi of the individual states. One natural calculation is to compute P/h. This number, which may not be an integer, can be thought of as the "ideal" district size for each congressional district in the country. Every P/h people "deserve" one representative. To find out the number of these representatives for a particular state we can compute pi/(P/h). Again this number is often not an integer. However, it represents an "idealized" number of seats for each state. This number is often called state i's ideal quota. If this number is not an integer, it seems reasonable that state i should get either this number rounded up to the next integer or rounded down to the integer below. However, whichever case is chosen, the state will either be underrepresented or over represented compared with what is "ideal."
A somewhat different approach is to compute the integer part of the "ideal" quota for each state, and give the state this number of seats. Now, one has to decide how to distribute the left over seats.
Let us consider the example we treated in class:
The legislature (Parliament) of a small (fictional) country has 200 seats.
After the recent election the parties received the following shares of votes:
Social Democrats: 18,800
Democratic Socialists: 180,600
Independent Democrats: 200,600
What is a fair way to distribute the 200 seats to the different parties?
Here we have three claimants, whose "claims" are measured by the percentages:
SD: 4.7%
DS: 45.15%
ID: 50.15%
Note that because ID received more than half of the vote it does not seem unreasonable for it to get at least half the total number of the seats that are available. Democracy usually requires protection of minority rights but not that a majority be hampered in doing what it seeks to accomplish.
Reasonable people disagree considerably about what method should be used to solve apportionment problems, in many ways paralleling the divergence of opinion about what is the best method is to translate ordinal ballots into a single societal winner or a societal ranking.
In the above example:
The ideal district size is 400000/200 = 2000
and, hence,
SD should get .047(200) = 9.4 seats
DS should get .4514(200) = 90.3 seats
ID should get .5015(200) = 100.3
The numbers above add, as they should to 200, though sometimes one does not get the house size h because of round off error.
Reference:
Balinski, M. and H. Young, Fair Representation, Yale University Press, 1982, Second Edition, Brookings Institution, 2001.
Taylor, A. and W. Zwicker, A characterization of weighted voting, Proc. Amer. Math. Soc., 115 (1992) 1089-1094.
Taylor, A. and W. Zwicker, Simple Games, Princeton U. Press, Princeton, 1999.