g DIMACS Tutorial on Social Choice and Computer Science

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.


Kevin Chang, University of Illinois at Urbana-Champaign

Title: Ranking and Preference in Computer Science: Models and Semantics

Many computer science problems require ranking-- In particular, this tutorial will survey the notion of ranking in fuzzy search (which return ranked results). We will study three major paradigms, in terms of their semantics and models, for such rankings: By similarity (e.g., image search for finding "similar" images), by relevance (e.g., text search for "relevant" documents), and by preference (e.g., e-commerce product search for finding "preferred" items). We will generally survey these paradigms developed in various contexts (of databases and information retrieval), with a specific focus on preference-based ranking.

Kevin Chang, University of Illinois at Urbana-Champaign

Title: Rank-based Top-k Query Algorithms in Database Search

As database systems are facing new challenges in non-traditional fuzzy retrieval scenarios, top-k or ranked queries are crucial for matching data by "soft" conditions such as similarity, relevance, or preference, in order to return top ranked results. For these applications, Boolean queries (e.g., SQL) are too restrictive as they do not capture partial matching and result ranking.

This tutorial will discuss query processing techniques for such queries. We will survey two types of ranked queries. 1) Order-based: A query aggregates several partial orders, each of which represents a query condition, to determine the overall ranking; and 2) Score-based: a query combines several numeric scores, each of which represents a query condition, to determine the overall ranking.

William Cohen, Carnegie Mellon University

Title: Collaborative Filtering in Information Retrieval

Collaborative filtering methods are used to recommend books to customers at Amazon.com, Netflix, and hundreds of other on-line stores; to guide Google's ranking of pages to a search query; and to decide which shows to record for Tivo PVR's. In my tutorial I will survey the development of collaborative filtering methods, and discuss some of the techniques that have been most successfully used for collaborative filtering, among which are techniques for learning to rank objects given rankings as input. I will also review formalisms for combining collaborative and content-based recommendation, and discuss ways in which collaborative filtering methods can be used with "implicit recommendations", such as web site links and web page structures.

Jonathan Goler, Massachusetts Institute of Technology, Media Lab / Artificial Intelligence Lab

Title: Internet Voting, Possibilities and Perils

Internet voting is heralded as the a step in the natural evolution of electronic voting. This tutorial discusses the possibilities of internet voting to improve participation, particularly for traditionally disenfranchised groups of voters, through better physical accessibility and user interfaces. In addition, this tutorial discusses some of the technical and security challenges with maintaining the integrity and reliability of elections. Finally, this tutorial addresses possible methods for dealing with security and reliability, including n-version programming. modularity and cryptographic protocols.

Ravi Kumar, IBM Almaden Research Center

Title: Internet search and meta-search

The tutorial will consist of two parts. The first part focuses on internet search and retrieval algorithms. Link-based ranking algorithms such as HITS/Clever/PageRank and their variants will be described. Additional topics include applications of link-based methods to community extraction and crawling, duplicate detection, and template elimination. The second part focuses on rank aggregation and meta-search. The rank aggregation paradigm, basic rank aggregation algorithms, and applications to meta-search and intranet search will be presented. Other meta-search algorithms will also be discussed.

Michel Regenwetter, University of Illinois at Urbana-Champaign

Title: Mathematical Representations of Preference and Utility

This tutorial will give a review of mathematical representations of preference and/or utility for finitely many choice alternatives, including binary preference relations of various kinds, real representations of binary preferences, probability distributions over binary preference relations and distribution free random utility models.

Michel Regenwetter, University of Illinois at Urbana-Champaign

Title: Behavioral Social Choice Theory

This tutorial will give a basic introduction to behavioral models of social choice by real actors and the confrontation of such models with empirical data, as well as with normative benchmarks of rational social choice. In particular, this framework attempts to bring an approach to social choice theory that is analogous to behavioral approaches in individual devision research, as well as behavioral approaches to economics.

Craig Tovey, Georgia Institute of Technology

Title: Computational Complexity of Social Choice Procedures

Computational complexity is a relatively new consideration in the centuries-old field of social choice. Some procedures which are otherwise attractive are impractical in the sense that they are NP-hard to compute. On the other hand, computational complexity might help safeguard the integrity of social choice. Impossibility theorems prohibit any reasonable voting procedure from being immune to manipulation (strategic insincere voting), but for some well-known procedures it is NP-hard to manipulate. In contrast, many procedures are easy to manipulate, although there exists a general method for tweaking most procedures to make them theoretically hard to manipulate. Complexity can also help guard against various kinds of agenda manipulation, such as padding the set of alternatives. I will add some speculations on cognitive complexity and the revelation principle.

Complexity can also serve another very useful purpose. In the widely used spatial model of voting, a co(NP)-completeness result explains the failure of decades of research attempts to derive succinct necessary and sufficient conditions for equilibrium.

Arnold Urken, Stevens Institute of Technology

Title: Introduction to Voting Theory: History and Procedures

Before the 18th century, voting theorists had theoretical insights, but their knowledge was not developed cumulatively. However early theorists raised many issues that were addressed during the classical "Golden Age" of voting theory in the 18th century French Academy of Sciences, where Borda, Condorcet, and others first developed mathematical models of voting procedures.

In the 20th century, Black's rediscovery of Condorcet's work and Arrow's axiomatization of the problem of collective intransitivity identified by Condorcet in 1785 has led to the current emphasis on problems of preference aggregation. This stream of analysis has spawned the development of new theoretical approaches to understanding the properties of voting systems by Saari, Brams, and others. However Condorcet's idea of designing voting procedures to maximize the group probability of making a "correct" choice has been revived by analysts such as Grofman, Owen, Feld, and Young.

Arnold Urken, Stevens Institute of Technology

Title: Voting and Security

Voting theory can be used to design network decision making software that enables groups to overcome network communications error and delay to reach a consensus and/or to maximize the group probability of making a correct choice. This capability is important because networks are critical channels for sharing data and creating new knowledge. Yet computer networks?wired or wireless?are inherently risky environments. However, error-resilient, waitless collective decisions can improve the trustworthiness of network-centric decision making for applications in Homeland Security, finance, and network transmission of electricity.

This introduction focuses on Homeland Security scenarios in which groups of humans or sensors make collective decisions in client-server or peer-to-peer mode. The tutorial explains how to design error-resilient voting procedures and highlights issues for future research. For example, can in multidimensional, multi-objective decision tasks be error-resilient? Current results show that voting outcomes can be error resilient on two or more dimensions even if they are not resilient on a single dimension. So complexity can serve a stabilizing role in enabling collective decisions to be error-resilient. But the conditions under which error-resilience is feasible are not well understood.

Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on April 23, 2004.