The computational complexity of choice sets

ABSTRACT

Social choice rules are often evaluated and compared by inquiring whether they fulfill certain desirable criteria such as the Condorcet criterion, which states that an alternative should always be chosen when more than half of the voters prefer it over any other alternative. Many of these criteria can be formulated in terms of choice sets that single out reasonable alternatives based on the preferences of the voters. In this paper, we consider choice sets whose definition merely relies on the pairwise majority relation. These sets include the Copeland set, the Smith set, the Schwartz set, von Neumann-Morgenstern stable sets (a concept originally introduced in the context of cooperative game theory), the Banks set, and the Slater set. We investigate the relationships between these sets and completely characterize their computational complexity which allows us to obtain hardness results for entire classes of social choice rules. In contrast to most existing work, we do not impose any restrictions on individual preferences, apart from the indifference relation being reflexive and symmetric. This assumption is motivated by the fact that many realistic types of preferences in computational contexts such as incomplete or quasi-transitive preferences may lead to general pairwise majority relations that need not be complete.

REFERENCES

• 1: Noga Alon, Ranking Tournaments, SIAM Journal on Discrete Mathematics, v.20 n.1, p.137-142, 2006 [doi>10.1137/050623905]
• 2: A. Altman and M. Tennenholtz. On the axiomatic foundations of ranking systems. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), pages 917--922. Professional Book Center, 2005.
• 3: K. J. Arrow, A. K. Sen, and K. Suzumura, editors. Handbook of Social Choice and Welfare: Volume 1. North-Holland, 2002.
• 4: J. S. Banks. Sophisticated voting outcomes and agenda control. Social Choice and Welfare, 3:295--306, 1985.
• 5: J. Bartholdi, III, C. A. Tovey, and M. A. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6(3):157--165, 1989.
• 6: A. K. Chandra, L. Stockmeyer, and U. Vishkin. Constant depth reducibility. SIAM Journal on Computing, 13(2): 423--439, 1984.
• 7: V. Chvátal. On the computational complexity of finding a kernel. Report CRM-300, Centre de Recherches Mathématiques, Université de Montréal, 1973.
• 8: A. H. Copeland. A 'reasonable' social welfare function. mimeographed, University of Michigan Seminar on Applications of Mathematics to the social sciences, 1951.
• 9: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 10: Marquis de Condorcet. Essai sur l'application de l'analyse à la probabilité de décisions rendues à la pluralité de voix. Imprimerie Royal, 1785. Facsimile published in 1972 by Chelsea Publishing Company, New York.
• 11: B. Dutta. Covering sets and a new Condorcet choice correspondence. Journal of Economic Theory, 44:63--80, 1988.
• 12: P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. A richer understanding of the complexity of election systems. Technical Report TR-903, Department of Computer Science, University of Rochester, 2006.
• 13: P. C. Fishburn. The Theory of Social Choice. Princeton University Press, 1973.
• 14: P. C. Fishburn. Condorcet social choice functions. SIAM Journal on Applied Mathematics, 33(3):469--489, 1977.
• 15: Q. Hudry. A note on "Banks winners in tournaments are difficult to recognize" by G. J. Woeginger. Social Choice and Welfare, 23:113--114, 2004.
• 16: David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 17: G. Laffond, J. F. Laslier, and M. Le Breton. Condorcet choice correspondences: A set-theoretical comparison. Mathematical Social Sciences, 30:23--35, 1995.
• 18: S. Lahiri. Stable sets of weak tournaments. Yugoslav Journal of Operations Research, 14:33--40, 2004.
• 19: J.-F. Laslier. Tournament Solutions and Majority Voting. Springer, 1997.
• 20: K. May. A set of independent, necessary and sufficient conditions for simple majority decisions. Econometrica, 20: 680--684, 1952.
• 21: D. C. McGarvey. A theorem on the construction of voting paradoxes. Econometrica, 21(4):608--610, 1953.
• 22: N. R. Miller. Graph-theoretic approaches to the theory of voting. American Journal of Political Science, 21(4): 769--803, 1977.
• 23: H. Moulin. Choosing from a tournament. Social Choice and Welfare, 3:271--291, 1986.
• 24: M. Richardson. Solutions of irreflexive relations. The Annals of Mathematics, 58(3):573--590, 1953.
• 25: M. Schulze. A new monotonic and clone-independent single-winner election method. Voting Matters, 17:9--19, 2003.
• 26: T. Schwartz. Rationality and the myth of the maximum. Noûs, 6(2):97--117, 1972.
• 27: A. K. Sen. Collective Choice and Social Welfare. North-Holland, 1969.
• 28: P. Slater. Inconsistencies in a schedule of paired comparisons. Biometrica, 48(3--4):303--312, 1961.
• 29: J. H. Smith. Aggregation of preferences with variable electorate. Econometrica, 41(6):1027--1041, 1973.
• 30: A. M. A. van Deemen. A note on generalized stable sets. Social Choice and Welfare, 8:255--260, 1991.
• 31: J. von Neumann and O. Morgenstern. The Theory of Games and Economic Behavior. Princeton University Press, 1944.
• 32: G. J. Woeginger. Banks winners in tournaments are difficult to recognize. Social Choice and Welfare, 20:523--528, 2003.