(RI+hcc)-Small: Computational Social Choice: Aggregating Preferences in Combinatorial Domains

Duke University, Durham NC

Investigators

Abstract

In traditional social choice, it is assumed that each agent explicitly ranks all of the alternatives. In Artificial Intelligence applications this is generally impractical: for example, there are exponentially many joint plans or allocations of tasks/resources. Nevertheless, even the computational social choice community has so far focused primarily on the explicit-ranking model. While this was a necessary phase to establish a solid foundation for this line of research, it is now time to move on and consider the combinatorial domains with exponentially many alternatives that motivated computational social choice in the first place. This is what the proposed research will do. The PI proposes the following 5-part research plan. First, he plans to study how agents? votes should be represented, that is, what language the agents should use to express their preferences in a combinatorial domain. Once the language has been determined, he plans to study what rule should be used to make a decision based on the votes. Such a rule would be useless without a good algorithm for executing it, that is, for solving the winner determination problem. Even with a good language, it may be overwhelming for an agent to report its complete preferences, so the PI plans to study how to elicit the (relevant parts of) agents? preferences by asking the agents simple queries. Finally, he plans to address the problem of agents voting insincerely to manipulate the decision, in part by investigating whether such manipulation can be made computationally infeasible. Broader Impacts The proposed research will allow agents to coordinate when solving a complex problem, even if they have been created by different designers with different objectives. For example, robots in search-and-rescue or other exploration settings can vote over how they will divide the exploration. This allows a much greater diversity of agents to participate in such a task, undoubtedly leading to better results. Also, some of the research is likely to be applicable to human decision making. Europe is starting to take the lead in computational social choice; if funded, this proposal will ensure that the U.S. retains expertise in and continues to shape this burgeoning research area. Of course, research is not a zero-sum game, and the PI plans to collaborate closely with the other researchers in the area. In fact, this proposal corresponds to the PI?s part of a 12-investigator proposal that was just recommended for funding by the European Science Foundation (ESF). This (NSF) proposal would also support the PI?s collaboration with Jeff Rosenschein (Hebrew University); for this collaboration, Jeff and the PI already received a small US-Israel Binational Science Foundation grant that serves to support the Israeli side as well as travel. The proposal also includes plans to develop a new graduate course on computational social choice, mentor graduate and undergraduate students, build connections to economics and political science, and attract more women to computer science (as well as participate in other outreach activities).