From mvcorks [AT] alumni [dot] uwaterloo [dot] ca Mon Nov 24 18:35:33 EST 1997 Path: undergrad.math.uwaterloo.ca!not-for-mail From: mvcorks@calum.csclub.uwaterloo.ca (Matt Corks) Subject: Game Theory and Democracy Summary: Examples of paradoxes in various contemporary voting systems. Sender: news@undergrad.math.uwaterloo.ca (news spool owner) Message-ID: Date: Mon, 24 Nov 1997 07:47:34 GMT Reply-To: Matt Corks Nntp-Posting-Host: calum.csclub.uwaterloo.ca Organization: None to speak of. X-Newsreader: trn 4.0-test60 (5 October 1997) Keywords: democracy, game theory Status: RO Content-Length: 6544 Lines: 122 I've been promising for a while now to post a game-theoretic analysis of democracy. What follows are examples of the problems arising from many democratic voting systems, and a description of a voting system which is free >from them. This is all summarized from the chapter "Is Democracy Mathematically Unsound?" of the book _Archimedes' Revenge_ by Paul Hoffman. In 1951, American economist Kenneth Arrow gave a game-theoretic demonstration that most democratic voting methods can lead to undemocratic paradoxes where misrepresenting oneself on a ballot can act in one's favour. As an example of such a paradox, consider three friends voting on which restaurant to eat at. Their preferences are as follows: | Ronald | Clara | Herb ---+-------------+-------------+------------ 1 | McDonald's | Wendy's | Burger King 2 | Burger King | McDonald's | Wendy's 3 | Wendy's | Burger King | McDonald's They decide to vote first between McDonald's and Wendy's, and then between the winner of that vote and Burger King. If they each vote honestly, they'll end up at Burger King. However, if Clara claims to prefer McDonald's over Wendy's in the first ballot, the three will go to her second choice restaurant-- McDonald's-- and not her third. Changing the order of the vote will not remove this paradox, it will just cause a different person to be able to benefit. William Riker (a professor at the University of Rochester) shows in _Mathematical Applications of Political Science_ that this situation is essentially the same as that in the U.S. House of Representatives when an amendment is introduced. There are two votes, the first on whether to amend the bill, and the next to decide whether to pass the winner of that vote or defeat it. His example is a 1956 vote on a bill to provide federal aid for school reconstruction. It was proposed to amend the bill so that only states whose schools were racially integrated would receive money. The interest groups, which were of roughly equal size, were as follows: | Republicans | Northern Democrats | Southern Democrats ---+--------------+--------------------+------------------- 1 | No Bill | Amended Bill | Bill 2 | Amended Bill | Bill | No Bill 3 | Bill | No Bill | Amended Bill As would be expected, the amendment passed the first vote, but the bill was defeated in the second. However, if there had been no amendment, the bill clearly would have passed. To understand this paradox, consider the three friends again. The sequence of preferences of any one of them can be charted, like so: Ronald: McDonald's <-- Burger King <-- Wendy's These preferences are transitive. If we know that, in his opinion, McDonald's > Burger King and Burger King > Wendy's, we can conclude that he prefers McDonald's to Wendy's. Now, consider the preferences of the group as a whole: Group: ,-<- McDonald's <-- Burger King <-- Wendy's <--. `----->----------------->------------->--------' The problems given above arise from the fact that these preferences are intransitive. Voting systems have been studied intensively by Steve Brams, also a professor at Rochester. He shows that this paradox of "societal intransitivity" will only arise between three voters faced with three alternatives when each choice is ranked first by exactly one party, second by exactly one other, and third by the last. If all possible preferences are equally likely, there is a 5.6% chance of intransitivity. However, as the number of voters and the number of alternatives increase, intransitivity becomes more likely. The following table is excerpted from Bram's _Paradoxes in Politics_: | Number of voters | 3 5 7 11 oo ----+-------------------------------------- Number of 3 | 5.6% 6.9% 7.5% 8.0% 8.0% alternatives 4 | 11.1% 13.9% 15.0% 29.4% 17.6% 5 | 16.0% 20.0% 21.5% 34.3% 25.1% 7 | 23.9% 29.9% 30.5% 34.2% 34.3% oo | 100.0% 100.0% 100.0% 100.0% 100.0% Chance of Societal Intransitivity Brams has also pointed out paradoxes in other voting systems, such as the Hare system , in which the voter is asked to list multiple candidates in order of preference, until the voter is indifferent to those who remain. (The rules for tabulating the votes are rather complicated.) This system is currently in use governmental elections in several countries, as well as in various professional organizations, including the American Mathematical Society. Under the Hare system, an AMS ballot once included the statement "there is no tactical advantage to be gained by marking fewer candidates", but Brams was able to show a counterexample to this claim. There are also cases where ranking a candidate second as opposed to first can cause them to win. As well, in "The Hare Voting System is Inconsistent", Gideon Doron (again, of Rochester) constructs a paradox in the Hare system where a candidate who wins in two separate districts will lose in a combined tally of the two districts. In _Approval Voting_, Brams and Peter Fishburn give examples of these paradoxes affecting two-stage elections (such as a run-off election between the top two candidates in the first election). Brams also suggests that a public announcement of how candidates fared in a pre-election poll may cause the same situation to happen in an ordinary one-stage election. This, of course, is precisely the method currently used to elect our governments. Brams is an advocate of a method of voting called approval voting, a system in which no paradoxes have been discovered to date. In this method, each voter may vote for multiple candidates, but may cast no more than one vote per candidate. There is no disadvantage in voting for a relatively unpopular candidate who would be unlikely to win in a traditional election, since it is possible to vote for a more popular candidate as well. However, this system is currently only used in a few professional societies, and in the United Nations Security Council for elections of candidates for the position of Secretary General. -- Matt Corks, congenital pessimist; 2B Co-Op Math, Comp. Sci., U. Waterloo PGP key: , Laziness: check. Impatience: check. Hubris: check.