Voting and social choice

We view an election-tallying procedure as an algorithm, so that it is natural to inquire about the computational resources required by that algorithm.

Among the results that pleases me most is that an election scheme seriously proposed by Charles Dodgson (Lewis Carroll) has the property that it is NP-hard to tell whether any particular candidate has won the election. This suggests the delicious paradox that a candidate’s term may have expired before his can be determined to have won the election!

Another type of result we have established is that some voting schemes are computationally resistant to manipulation: That is, it is NP-hard for an individual to figure out how to tailor his vote to achieve a strategic outcome. This is true for the voting scheme known as Single Transferable Vote but is not true for many other voting schemes, such as plurality vote or Borda count.

Some of these are available only as paper reprints, which I will be happy to mail to interested parties.

• Voting schemes for which it can be difficult to tell who won the election, with C. A. Tovey and M. A. Trick; Social Choice and Welfare 6:157-165 (1989).
• The computational difficulty of manipulating an election, with C. A. Tovey and M. A. Trick (1989); Social Choice and Welfare 6:227-241 (1989).
• Recognizing majority-rule equilibrium in spatial voting models, with L. S. Narasimhan and C. A. Tovey. A slightly revised version of this appeared in Social Choice and Welfare 8:183-197 (1990).
• Single transferable vote resists strategic voting, with J. A. Orlin (1991). This appeared in Social Choice and Welfare 8:341-354 (1991). See also: errata.
• How hard is it to control an election?, with C. A. Tovey and M. A. Trick. A slightly revised version of this appeared in Mathl. Comput. Modelling (Special Issue on Formal Theories of Politics) 16(8/9):27-40 (1992).

Another matter regarding voting: Here is a copy of the voting test that was used in the state of Georgia to disenfranchise blacks, until the federal Voting Rights Act of 1965 put an end to it. I am told one had to achieve a perfect score to be registered to vote. Two things are striking about this test:

• It is very hard. In fact, I do not know anyone who could pass it other than, perhaps, a political science teacher. (Here are the answers.)
• Parts of the test make the authors seem illiterate (“If a person is indicted for a crime, name two rights which he has.”).