We propose to formalize mathematical models of group decision making that take into account expected behaviors, the effects of exogenous events and influences, and the psychological effects of belief modifications, all in the context of probabilistic reasoning. We are interested in building models sufficient to give us insight into both human and computational preference aggregation and voting processes. For instance, we want to leverage the growing political science work on social networks and voting to build models of voting that reflect complex interpersonal influence between voters. We want to explore work on belief changes in the political science, psychology, and decision sciences literature to include in our models the human tendency to revert to earlier-held beliefs.
The intellectual merit of this work lies in the mathematical formalization of theories of group decision making and influence in a stochastic setting; the alignment of such models with those from the political science literature; computational complexity analysis of stochastic models of influence in group decision making, and algorithms for influencing and blocking influence in such settings.
This work addresses NSF's third broader impacts category: "Enhance infrastructure for research and education." The field of computational social choice is often said to have begun with Bartholdi, Tovey, and Trick's 1989 paper in the journal Social Choice and Welfare. However, computer scientists were very slow to notice it, and it generated little initial attention in political science. Even now, cooperation and even communication between political and computer scientists about "social choice'" is limited. We will take on the challenging task of interdisciplinary research, attempting to understand problem statements, goals, and results from both bodies of research. We have seen great success by SIGECOM in supporting interdisciplinary work in algorithmic computer science, complexity theory, and economics. We hope to bring that level of interaction to the social choice research areas.
The primary goals of this award were to investigate the robustness of various preference aggregation schemes to attacks from both external and internal participants. Ultimately, while we want participants, be they sports teams or individuals rating movies, to perform and report their preferences honestly, the first step in these directions is understanding how schemes in current use may be attacked or manipulated for individual gain. Specifically, we looked at voting schemes and attempted to characterize their susceptibility to manipulation based on the types of information that was available to attackers. In this stream we formalized models to encode information probabilistically and also conditionally. This is an important first step in understanding the relationship between information and security in voting systems as most existing research focuses on complete information settings. We found that while conditional preference information may not be enough to discourage manipulation through complexity, even rough probabilistic information may be useful in protecting certain aggregation schemes. Additionally we instigated some of the largest studies of preference aggregation functions using real world data from the Netflix Prize Challenge as a data source. We examined statistical patterns occurring in "elections" based on those preferences; occurrences of preference cycles; the differences in outcomes amongst different voting schemes, and the effectiveness of manipulation algorithms on these elections. Our findings are mixed and we are still working with others in the community to understand and generalize what we have found. Another goal is to formalize preference representations that both capture real, human preferences in at least some of their complexity, yet allow feasible computation about those preferences. Our work on CP-nets (conditional preference networks) is part of the second goal. An additional goal of this work has been understanding and communicating probabilistic information to larger audiences. The testbed for this portion of the work has been a recommendation system that works in the area of academic advising; attempting to convince students to consider long term, probabilistic information in their individual assessments of what courses to take in future semesters. We have produced and tested algorithms and model-building in these domains as well as conducted large, cross sectional studies of student populations. This grant has also supported work on computer science education, ranging from statistical analyses of teacher/course evaluations to studies of the effect of allowing students use reviews of science fiction as a springboard into the artificial intelligence research literature.
