THoughtful Thursday, Voting Systems

Assume there are several candidates or alternative health reform plans on the table. Assume candidate A would win a one-on-one election with any other candidate. Candidate A is the Condorcet winner. If we have a binary tournament, candidate A will win. It does not matter what order they are paired up. Unfortunately, there may be no Condorcet winner, a cycle. Example with three voters, assume the preferences below:

G	B	N
B	N	G
N	G	B

In this case, the order matters. In the tree below where G runs against B and the winner of that race runs against N, N would win. If we had a different pair up for the first challenge, some other candidate would ultimately win. This is in game theory terms (Page 219, Osborne, A Course in Game Theory) Condorcet cycles are considered the first mathematical social choice theory. The Game Theory book goes on to identify top cycles, candidates that can beat every alternative directly or indirectly (A beats B beats C) one of these will win in any binary voting tree but we don't know which of these "top candidates" will win the election--it depends upon the binary decision tree.

Preference Systems

In conventional voting, the voters vote for one choice. That is people cast a vote either for B, G or N. I am sure everyone here recognizes the problem. The third person prefers N but whose second choice is G would be better off voting for G so as to ensure that the hated B does not wins, especially if the second column represented 34% of the vote. This is known in the social choice literature as "strategic voting."

Many voting systems ask us not to just give our "first choice" but simply to list our preferences. We need a voting system which decides who wins. The well-known Arrow Impossibility Theorem says that one can't find an ideal one. Any algorithm that takes as input everyone's preference order will have one or more of a list of certain undesirable properties. I will save that for another Thoughtful Thursday.

Referenda

The Swiss system allows the legislature to respond to a initiative by the people, by proposing an alternative. Thus, when voting occurs on the initiative, the ballot has three choices:

1. Whatever the people sending the initiative proposed
2. the counteroffer from the legislature
3. the status quo. The most voters vote for neither of the two proposed laws and the people are left with whatever was there before, e. g., if the subject was health and we did a plurality voting between possible health systems, the votes of everyone who wanted health reform would be split among the different health reform proposals. Thus, the votes of everyone who liked the health system just fine would be the highest plurality.

Unfortunately, in Switzerland, the legislature sometimes deliberately puts out an alternative. This is to split the vote for change. The people with nothing but status quo, which is what the legislature wanted in the first place.

(I read this online and I definitely recall printing it; but I cannot find it; and my attempts to search for the article again have failed.)

In the insurance wars of California, the Californians were very tired of high auto-insurance rates. Several proposals got the signature need to qualify to be on the ballot for a referendum. California handled it by approval voting, everyone got to vote for as many proposals as they liked or of which they "approved." The one with the most votes won. The one that got the most votes was a simple proposal to limit the percentage of money the insurance companies could charge over and above the cost of claims. That is, the insurance companies had to pay out a certain fraction of every dollar of premium.

I introduce the idea of parametric referenda. Each referendum might have one or more numbers. A tax law would have the tax rate. We know from Duncan Black's work that if there are a series of binary votes, we would end up with the median voter response. And we saw that with candidates and the "Left-Right" continuum in Hotelling's work. In the United States, on the "left-right" continuum, the country is at the median position of its voters.

One possibility is that there is a big vote for the structure, followed by a vote for the parameter. I wrote about this in one of the first articles on the health care system reform; there would be a big plebiscite with options such as the status quo, single-payer and perhaps the structure that was since enacted into law. Then once one of these won the approval voting, there would be an oportunity to choose the parameters by median. Assume the current structure was passed into law with a penalty for choosing not to be insured. In a second election, each voter would enter the amount that they felt the penalty should be and the median of those numbers would be the penalty amount enacted into law.

Each voter would decide which health structure to choose and would have an opportunity to engage in strategic voting. If they could accurately judge, say by polls, what the median would be for that system, each voter would decide which one they wanted. Another possible mechanism: The voters would enter preference orders conditional on parameters. That is a voter would say they prefer the current structure as long as the penalty is under $1000.00. And they would prefer single-payer as long as the taxes were less than $1000.00. How could the combinations of a vote plus an interval for a parameter be combined to choose a system and a parameter?

Voting Schemes for Which It Can be Difficult to Tell Who Won the Election, J. Bartholdi III, C. A. Tovey and M. A. Trick, Social Choice and Welfare (1989) Volume 6, pages 157 to 165.

If there are several alternatives for the referendum, then there is a very good chance that there is no Condorcet winner. That means if referendum opportunity one is paired against referendum opportunity two, the second might win. Then, if that were paired against referendum opportunity three, then three might win. Had referendum one been pitted against referendum opportunity three and then the winner of that wrestled with referendum opportunity two, there would be a different outcome. Dodgson proposed taking the preference orders, and seeing how one could change them so that there would be a Condorcet winner. Depending upon how one rearranged the orders of each voter, one would get a different winner. If we arranged the table with N, B and G by flipping the middle column , we would get a Condorcet winner of N

G	N	N
B	B	G
N	G	B

For the millions of votes and preference orders, how could we achieve a Condorcet winner with the fewest swaps?

Kemeny suggested that we find a consensus order closest to voters preference orders as possible.

Unfortunately, both of these are NP-complete! This means there is no algorithm that will find the solution in less than polynomial time, or in general, it is intractable. (This is a bastardized and oversimplified view of this concept. I will talk about NP-complete in a future Thoughtful Thursday.) In other words, everybody could submit their preference sheets. And the computers would be grinding "forever," apparently in an infinite loop, not to end until well past the entire Universe has decayed into a soup of positrons. I briefly mentioned work on good approximations for Kemeny method?

Elections Can be Manipulated Often, by Ehud Friedgut, Gil Kalia and Noam Nissan

Looking back at voters voting for three candidates,such as the infamous B-N-G election, the three doctors found that the sum of the probabilities that a voter could manipulate the election is greater than C e ². Manipulation sounds evil, but it simply means that voter might give a preference that isn't true. For example, saying G is their first choice when they really like N. This does not mean that every voter can do manipulation. Only that some can! So out of the United States 200 million voters, maybe only a few thousand might have the opportunity to manipulates.

Oh, and what is e. That is the percentage of times the social choice function differs from a dictatorship. If the rule is that the king makes the decision, then noone can manipulate the election as either their choice does not matter or for the king, whatever they want will be the result.

The good doctors were only able to extend the first two steps of the proof to the case where there were more than three candidates. They speculated that the bound would "decrease polynomially in " the number of alternatives.

It is also important to remember that the probability of manipulation is one that might land on only a few voter's laps, who might not be sophisticated or too high-minded enough to manipulate.

Marcus Isaksson, Guy Kindler and Elchanan Mossel, "The Geometry of Manipuation -- A Quantitative Proof of the Gibbard Satterthwaite Theorem"

The three researchers show that a social choice function has a probability of being maniulable of at least
0.0000001 e ² / (n ³ q ³²)
They define a manipulatin point that a particular voter x can report a preference set that isnot their true preference set but get a result they prefer. They show the probability that any given voter could manipulate the election is
e ²/ ( 2 n ³ q ⁶ (q factorial) ²)
Now as a practical sense this is a negligable probability. Even the main result that someone can manipulate the election decreases as the thirty-second power of the number of alternatives. It increases as the cube of the number of voters. 100,000,000³ steps is way beyond the time frame of moedern computers.

One should be concerned with coalitions of voters, voters all willing to follow a "guru" whether religious or political who presumably can also spend for the computer time to search millions of possibilities to find the best strategy.

Also, these results are for "neutral functions" where each voter has the same power. In other words, voter A voting a preference order v , voter B voting a preference order w or voter C voting a preference order z shold give the exact same result as voter A voting a preference order z, voter B voting preference order w and voter C voting prefernce order v. However, imagine a country of three ethnic groups forming a constitution. They might specify a mechanism to give equal power to the ethnic groups so a voter in one ethnic group effectively might have more power than a voter in another. Similarly, a system comparable to the United States Senate that counted voters by state , The alternative passed by a majority in the ost states wins, even though the states have different populations. This would not be a neutral election system!

The Computational Difficulty of Manipulating an Election, J. J. Bartholdi III, C.A. Tovey and M. A. Trick, Social choice and Welfare (1989) Volume Six 227 to 241

We know from Gibbard and Satterthwaite that every social choice system is manipulable. The above two articles discussed before suggest that sometimes it makes sense to simply search linearly through all the possible strategies for a manipulation strategy.

We know from Computer Science two things. Sometimes when one is trying to optimize, there are ways to accomplish this without searching all possibilities. For example, if one has a table of all the highways and one wants a computer program to find tte he best way to get from the proverbial A to B. There would be an exponential number of possible paths that one can take. But one does not have to search all the pathways. One can apply Dijkstra's algorithm. The computer would take steps proportional to the square of the number of highway segments. And there are proven techniques to simplify even that; one of these is A Star.

We also know that many problems are NP complete. For example, if one wants the best path that visits every city, a Hamiltonian path, there is no polynomial algorithm to find the shortest one. (There are caveats--for another thoughtful Thursday or a quick clink on the Wikipedia Article). There are also approximations.

The same is true for the strategic voter wanting to know what they should enter at the voting machine, or internet voting computer. There is a polynomial time greedy algorithm for any voting system that is monotone. That simply means that the voting system is more likely to report candidate j is the winner of the election than candidate i if a particular voter indicates J higher in preference. And the conventional plurality voting system such as in our famous N, B G election. That means that assume a person prefers N to G to B, and also knows every other voters' preferences, they can consult their computer program to find out whether to vote for N ior G. It is also true for some other schemes:

1. Positional or Borda count. Each voter sends a list in rank order, and these ranks are added. The one with the highest is voted.
2. the winner is the candidate who is preferred in the most pairwise elections
3. the winner is the candidate who would have the most victories - the most defeats in pairwise elections-- Copeland's method.

I will prepare a table of all the proposed voting systems and their properties for a future Thoughtful Thursday.

But a minor variation of Copeland method, which by the way the United States and International Chess Federation works, is NP-complete. It deals with ties by looking at the candidate who defeated the highest scoring candidates. That IS NP-complete. And as seen from the "Future Thoughtful Thursday List" there are many others.

Conclusion

The participatory methods I proposed earlier take advantage that large numbers of alternatives are our friend. If the alternatives are every conceivable combination of factors and penalties for a gun code. If the alternative for a tax code are every combination of rate tables and factors such as number of children and amount of one's mortgage, then we can overwhelm the above results in an exponential or even infinite number of alternatives.

That means we don't have a few proposals from the legislature or for which somebody bothered or paid to get 100,000 signatures. the voter can select their preferences from every logical combination! This lowers or eliminates the probability that someone can find a way to vote strategically!

For Future Thoughtful Thursdays

1. Arrow's Impossibility Theorem
2. The California Insurance Wars.
3. Mark Allen Satterthwaite, "Strategy-proofness and Arrow's Condition: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions Journal of Economic Theory Pages 187 to 217, 1975
4. G. Kalia, "A Fourier-Theoretic Perspective for the Condorcet Paradox and Arrow's Theorem" Advances in Applied Math 29 42 to 426, 20002
5. Allan Gibbard, "Manipulation of Voting Schems: A General Result" Econometric 41 587 to 601 1973
6. V. Conitzer and T. Sandholm,"Universal Voting Protocol Tweaks to Make Manipualtion Hard" in IJCAI 781788 2003, 781 to 788.
7. V. Conitzer and T. Sandholm , "nonexistence of Voting rules that Are Usual Hard to Manipulate" AAAI 2006.
8. V. Conitzer and T. Sandholm, Journal of the ACM, August 2007.
9. Ariel D. Procaccia and Jeffrey S. Rosenchien. Junta Distributions and the Average-Case Complexity of Manipulating Elections In Hideyuki Nakashima, Micahel P. Wellman, Gerhard Weiss and Peter Stone. Fifth International Joint Conference on Autonomnus Agents and MultiAgent Systems (AAMAS 2006)
10. J. S. Kelly, "Almost all social choice rules are highly manipulable, but a few aren't. Social Choice and Welfare 10, 1993.