DIMACS Tutorial on Social Choice and Computer Science

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

Kevin Chang, University of Illinois, kcchang@cs.uiuc.edu
Michel Regenwetter, University of Illinois, regenwet@uiuc.edu
Presented under the auspices of the Special Focus on Computation and the Socio-Economic Sciences.

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:


Agrawal, R., and Wimmers, E., "A framework for expressing and combining preferences," SIGMOD 2000, Proceedings of ACM SIGMOD International Conference on Management of Data, 2000, 297-306.

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
Contacting the Center
Document last modified on March 26, 2004.