DIMACS Tutorial on Social Choice and Computer Science

May 10 - 14, 2004
DIMACS Center, CoRE Building, Rutgers University

Organizers:

Kevin Chang, University of Illinois, kcchang@cs.uiuc.edu

Michel Regenwetter, University of Illinois, regenwet@uiuc.edu

The theory of social choice and voting has had a long history in the social sciences, dating back to early work of Condorcet and others in the 18th century. Some modern issues facing the theory of social choice relate heavily to computer science. Often we need to determine preferences for an individual or group, while maintaining accuracy, fairness and security, sometimes with only limited information and/or computational power. This tutorial will consider computer science and social science issues in insuring the best choices given limited information and computation. It will build on early work on the computational complexity of computing the winner of an election [Bartholdi and Tovey (1992), Bartholdi and Tovey (1989), Bartholdi and Tovey (1989).] Moreover, we are also seeing voting/social choice issues arising in strictly computer science applications such as database and information retrieval, Internet search and meta-search, and collaborative filtering. The tutorial will also consider such applications. The tutorial will present an introduction to the concepts and models of individual preference or utility as well as social choice theory and introduce participants to a variety of modern computational issues and computer science applications.

The following is a tentative list of topics:

• Introduction to Voting Theory: History and Procedures. Among the most famous social choice procedures are one person, one vote scoring, majority rule, the Borda score, Condorect scoring, plurality, Copeland scoring, approval voting and other scoring rules [Urken (1991), McLean and Urken (1995) ,Saari (1994),Saari (1995), Saari (1999)].
• Computational Complexity of Social Choice Procedures. In terms of computational resources, how hard is it to determine the results of an election [Bartholdi and Tovey (1992)? How hard is it for an individual to manipulate an election [Bartholdi and Tovey (1992), Bartholdi and Tovey (1989)]?
• Mathematical Representations of Preference and Utility. This includes various types of binary preference relations, representation theorems about the existence of corresponding real valued utility functions, as well as probabilistic representations, such as generalized mixture and random utility models [Fishburn (1985), Pirlot and Vincke (1997), Regenwetter (1996), Regenwetter and Marley (2001), Roberts (1979)].
• Ranking and Preference in Computer Science: Models and Semantics. Fuzzy search problems often require ranking the results. We will study the major paradigms for such rankings: By relevanceor similarity(e.g., text or image search) and by preference (e.g., product search), and in particular focus on recent efforts for preference modeling [Agrawal and Wimmers (2000), Hristidis, V., Koudas, N., and Papakonstantinou (2001), Kiebling (2002), Chomicki (2002)].
• Rank-based Top-k Query Algorithms in Database Search. For searching large databases with fuzzy criteria (e.g., in e-commerce or multimedia applications), we will study top-k query algorithms aiming at computing the k top results efficiently [Chang and Hwang (2002), Fagin, Lote, and Naor (2001), Nepal and Ramakrishna (1999), Wimmers, Haas, Roth, and Braendli (1999)], Bruno, Gravano, and Marian (2002)].
• Voting and Security: An introduction to the use of error-resilient, waitless methods of voting analysis to enable humans and sensors to reach collective decisions in unreliable client-server and peer-to-peer computer networking environments.[Urken (2003)].
• Collaborative Filtering in Information Retrieval. We will introduce recommender systems [Freund, Iyer, Schapire, and Singer (1998), Goldberg, Nichols, Oki and Terry (1992), Good, Schafer, Konstan, Borchers, Sarwar, Herlocker, and Riedl (1999)] which, as search agents, make recommendations to individuals based on aggregating their peers' preferences.
• Internet Search and Meta-Search. We will study Web search-engine ranking algorithms [Chakrabarti, Dom, Kumar, Raghavan, Rajagopalan, Tomkins, Gibson, and Kleinberg (1999), Kleinberg (1999)] as well as meta-search [ Dwork, Kumar, Naor, and Sivakumar (2001), Gravano, Chang, Garcia-Molina, and Paepcke (1997), Lawrence and Giles (1998)] which merges the results from several search engines.
• Behavioral Social Choice Theory. Much of traditional social choice theory has been of a normative nature. Recent work has investigated social choice behavior from a formal descriptive (behavioral) point of view [Regenwetter, Adams, and Grofman (2002), Regenwetter, Grofman, and Marley (2002), Regenwetter, Marley, and Grofman (2000), Regenwetter, Marley, and Grofman (2001)]. This work contrasts with some of the classical pessimistic predictions that normative social choice theory has produced in the past.
• Voting over the Internet. In recent years, there has been a growing interest in using the Internet for purposes of voting or polling. In 2000-2001, the Department of Defense carried out a pilot project (see http://www.fvap.gov/voi.html) on voting over the Internet. The European Science Foundation currently sponsors a major research effort aimed at Internet based complex decision support, called "Towards Electronic Democracy''.

References:

Bartholdi, J.J., Tovey, C.A., and Trick, M.A., "How hard is it to control an election," Mathematical and Computer Modelling, 16 (1992), 27-40.

Bartholdi, J.J., Tovey, C.A., and Trick, M.A., "The computational difficulty of manipulating an election," Social Choice and Welfare, 6 (1989), 227-241.

Bartholdi, J.J., Tovey, C.A., and Trick, M.A., "Voting schemes for which it can be difficult to tell who won the election," Social Choice and Welfare, 6 (1989), 157-165.

Bouyssou, D., "Ranking methods based on valued preference relations: A characterization of the net flow method," European J. of Operational Research, 60, 1992, 61-67.

Bouyssou, D., and Vincke, P., "Ranking alternatives on the basis of preference relations: A progress report with special emphasis on outranking," J. of Multi-criteria Decision Analysis, 6, 1997, 77-85.

Brans, J.P., Vincke, P., and Mareschal, B., "How to select and how to rank projects: The PROMETHEE Method," European J. of Operational Research, 24, 1986, 228-238.

Bruno, N., Gravano, L., and Marian, A., "Evaluating Top-k Queries over Web-Accessible Databases", ICDE, 2002.

Chakrabarti, S., Dom, B., Kumar, S.R., Raghavan, P., Rajagopalan, S., Tomkins, A., Gibson, D., and Kleinberg, J.M., "Mining the web's link structure," IEEE Computer, 32, 1999, 60-67.

Chomicki, J., "Querying with Intrinsic Preferences," EDBT (2002): 34-51.

Chang, K. C-C., and Hwang, S-W., "Minimal probing: Supporting expensive predicates for top-k queries," Proceedings of the 2002 ACM SIGMOD Conference, 2002, 346-357.

Dwork, C., Kumar, R., Naor, M., and Sivakumar, D., "Rank aggregation methods for the Web," Proc. WWW10, 2001.

Fagin, R., Lote, A., and Naor, M., "Opltimal aggregation algorithms for middleware," Proc. Twentieth ACM Symposium on Principles of Database Systems, 2001.

Fishburn, P.C., Interval Orders and Interval Graphs, Wiley, New York, 1985.

Y. Freund, R. Iyer, R.E. Schapire, and Y. Singer, "An efficient boosting algorithm for combining preferences," Machine Learning: Proceedings of the Fifteenth International Conference, 1998.

Goldberg, D., Nichols, D., Oki, B.M., and Terry, D., "Using collaborative filtering to weave an information tapestry," Communications of the ACM, 35, 1992, 61-70.

Good, N., Schafer, B., Konstan, J.A., Borchers, A., Sarwar, B.M., Herlocker, J.L., and Riedl, J., "Combining collaborative filtering with personal agents for better recommendations," AAAI/IAAI, 1999, 439-446.

Gravano, L., Chang, K.C-C., Garcia-Molina, H., and Paepcke, A., "Stanford Proposal for Internet Meta-Searching," Proceedings of the 1997 ACM SIGMOD Conference, 1997, 207-218.

Hristidis, V., Koudas, N., and Papakonstantinou, Y., "PREFER: A system for the efficient execution of multi-parametric ranked queries," Proceedings of ACM SIGMOD International Conference on Management of Data, 2001.

Kiebling, W., "Foundations of preferences in database systems," Proceedings of the VLDB 2002 Conference,2002, 311-322.

Kleinberg, J.M., "Authoritaive sources in a hyperlinked environment," JACM, 46, 1999, 604-632.

Lawrence, S., and Giles, C.L., "Inquirus: The NECI Meta Search Engine," Seventh International World Wide Web Conference, Elsevier Science, 1998, 95-105.

McLean, I. and A.B. (eds.) "Classics of Social Choice", Ann Arbor: University of Michigan Press, 1995.

Nepal, S., and Ramakrishna, M.V., "Query processing in image (multimedia) databases," International Conference on Data Engineering, 1999, 22-29.

Pirlot, M., and Vincke, P., Semiorders: Properties, Representations, Applications, Kluwer Academic Publishers, Dordrecht, Holland, 1997.

Regenwetter, M., "Random utility representations of finite m-ary relations," J. Math. Psychology, 40, 1996, 219-234.

Regenwetter, M., Adams, J., and Grofman, B., "On the sample Condorcet efficiency of majority rule: An alternative view of majority cycles and social homogeneity," Theory and Decision, 53, 2002, 153-186.

Regenwetter, M., Grofman, B., and Marley, A.A.A.J., "On the model dependence of majority preferences reconstructed from ballot or survey data," Mathematical Social Sciences, 43, 2002, 453-468.

Regenwetter, M., Marley, A.A.A.J., and Grofman, B., "A general concept of majority rule," Mathematical Social Sciences, 43, 2002, 407-430.

Regenwetter, M., Marley, A.A.A.J., and Grofman, B., "General concepts of value restriction and preference majority," Social Choice and Welfare, in press.

Regenwetter, M, Marley, A. A. J., "Random relations, random utilities, and random functions," Journal of Mathematical Psychology, 45, 2001, 864-912.

Roberts, F.S., "Graph theory and the social sciences," in R. Wilson and L. Beineke (eds.), Applications of Graph Theory, Academic Press, 1979, 255-291.

Saari, D.G., Geometry of Voting, Springer, New York, 1994.

Saari, D.G., {Basic Geometry of Voting, Springer, New York, 1995.

Saari, D.G., "Explaining all three-alternative voting outcomes," J. of Economic Theory, 87, 1999, 313-355.

Urken, A.B., "The Condorcet-Jefferson connection and the origins of social choice theory, Public Choice", 72: 213-236, 1991.

Urken, A.B. "Time, Error, and Collective Decision System Support, Proceedings of the International Conference on Telecommunications Systems", Monterey, 2003.

Vincke, P., Multi-criteria Decision-Aid, Wiley, Chichester, 1992.

Wimmers, E.L., Haas, L.M., Roth, M.T., and Braendli, C., "Using Fagin's algorithm for merging ranked results in multimedia middleware," International Conference on Cooperative Information Systems, 1999, 267-278.

Next: Call for Participation

Next: Program

Workshop Index

DIMACS Homepage