g
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.