EAGER: Changing Minds, Changing Probabilities

ABSTRACT: Our work seeks to gain novel insights into the area of reasoning under uncertainty. We will create and validate social choice models describing preference aggregation procedures. We will create and validate models of agent influence in preference aggregation settings using tools from interdisciplinary fields such as political science and social network theory. These models will remove the widely held assumptions of deterministic information; issue and agent independence; fixed coalitions, and permanent belief change. In addition to the construction and validation of the models we will perform a rigorous formal analysis of the models. This analysis will include computational complexity and approximation algorithms for reasoning in these complex, uncertain domains. RATIONALE FOR EAGER CONSIDERATION: Our goal is to work toward a model of group decision making that takes 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. Much of the work in computational social choice takes extremely simplified models of preference aggregation and voting and looks at the feasibility of reasining in these models. Other complications, such as uncertainty and coalition-based voting, have been introduced hesitantly at best. We are interested in building models sufficient to give us insight into both human and computational preferance 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. While some of the work will be complexity analysis and algorithm development, a major thrust will be to align the developed models with political science's understanding of the way preference aggregation and competition are effected by internal and exogenous pressures. Thus, our work extends beyond the usual confines of mathematical modeling and algorithmic development. The deliverables for this project will be formal models, complexity analysis (theorems), and algorithms for evaluation and optimization. The part that distinguishes our work from the funded work on computational social choice is that our work will be both informed by, and validated by, theories from the political sciences literature. This two-factor analysis means that we are not a good fit for the Algorithmic Foundations Group. BROADER IMPACTS: This work addresses BI category 3: 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 do the hard work 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. INTELLECTUAL MERIT: 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 if'fluence in group decision making, and algorithms for influencing and blocking influence in such settings.