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).
This project has focused on computational social choice. Social choice is the study of how to make decisions based on the preferences of multiple agents -- for example, by using a voting mechanism. Computational social choice concerns computational aspects of this process, with applications to multiagent systems in artificial intelligence, as well as to other disciplines such as economics. This particular project focused on building up the theory and techniques of computational social choice, with a focus on making these techniques feasible in rich domains, possibly with a combinatorial space of alternatives. For example, if multiple interrelated issues simultaneously require a decision, then an alternative specifies the decision on each individual issue. In accordance with the proposal, we have investigated topics such as: How should preferences be expressed in (combinatorial) social choice domains? How should an alternative be chosen based on these preferences, and how computationally hard is it to do so? Can we elicit the preferences incrementally, rather than force the agents to report them all at once? Generally, an agent may have an incentive to misreport her preferences or engage in other types of manipulation; can we prevent this, possibly by making it computationally hard? What are the consequences of such manipulation?
