Voting schemes for which it can be difficult to tell who won the election

We show that a voting scheme suggested by Lewis Carroll can be impractical in that it can be computationally prohibitive (specifically, NP-hard) to determine whether any particular candidate has won an election. We also suggest a class of impracticality theorems which say that any fair voting scheme must, in the worst-case, require excessive computation to determine a winner.Presented at Purdue University, March 1987; at the University of Arizona, April 1987; at Massachusetts Institute of Technology, April 1987; at Yale University, November 1987; at Centre International de Rencontres Mathematiques, Marseille-Luminy, April 1988. This research was supported in part by Presidential Young Investigator Awards from the National Science Foundation to the first two authors (ECS-8351313 and ECS-8451032), and by grant N00014-86-K-0173 from the Office of Naval Research.The authors thank the editor and three anonymous referees for many helpful suggestions.