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.

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: