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

在传统的社会选择中，假设每个主体明确地对所有的选择进行排序。在人工智能应用程序中，这通常是不切实际的：例如，任务/资源的联合计划分配呈指数级增长。然而，即使是计算社会选择社区到目前为止也主要集中在显式排名模型上。虽然这是为这条研究路线建立坚实基础的必要阶段，但现在是时候继续考虑具有指数级备选方案的组合领域了，这些备选方案首先激发了计算社会选择。这就是拟议中的研究要做的。PI提出了以下5部分的研究计划。首先，他计划研究代理人如何？投票应该被表示，也就是说，代理应该用什么语言来表达他们在组合领域的偏好。一旦语言确定，他计划研究应该使用什么规则来根据投票做出决定。如果没有一个好的算法来执行这样的规则，也就是说，如果没有一个好的算法来解决赢家确定问题，这样的规则将是无用的。即使有一个很好的语言，它可能会压倒一个代理报告其完整的偏好，所以PI计划研究如何引出（相关部分）代理？通过向代理询问简单的查询来实现首选项。最后，他计划解决代理人不诚实投票以操纵决策的问题，部分通过调查这种操纵是否可以在计算上不可行的。更广泛的影响拟议的研究将允许代理在解决一个复杂问题时进行协调，即使它们是由不同的设计师为了不同的目标而创造的。例如，在搜索和救援或其他探索设置中的机器人可以投票决定他们将如何分配探索。这允许更多的代理参与这样的任务，无疑会带来更好的结果。此外，一些研究可能适用于人类的决策。欧洲开始在计算社会选择方面处于领先地位；如果获得资助，该提案将确保美国保留在这一新兴研究领域的专业知识，并继续塑造这一领域。当然，研究不是零和游戏，PI计划与该领域的其他研究人员密切合作。实际上，这个建议对应于PI？这是欧洲科学基金会（ESF）刚刚推荐的12名研究人员提案的一部分。该（NSF）提案也将支持PI？与Jeff Rosenschein（希伯来大学）合作；为了这次合作，Jeff和PI已经收到了一笔小额的美国-以色列两国科学基金会资助，用于支持以色列方面以及旅行。该提案还包括计划开设一门关于计算社会选择的新研究生课程，指导研究生和本科生，建立与经济学和政治学的联系，吸引更多女性学习计算机科学（以及参与其他拓展活动）。

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 plansor allocations of tasks/resources. Nevertheless, even the computational social choice community has sofar focused primarily on the explicit-ranking model. While this was a necessary phase to establish a solidfoundation for this line of research, it is now time to move on and consider the combinatorial domains withexponentially many alternatives that motivated computational social choice in the first place. This is whatthe proposed research will do.The PI proposes the following 5-part research plan. First, he plans to study how agents? votes shouldbe represented, that is, what language the agents should use to express their preferences in a combinatorialdomain. Once the language has been determined, he plans to study what rule should be used to make adecision based on the votes. Such a rule would be useless without a good algorithm for executing it, thatis, for solving the winner determination problem. Even with a good language, it may be overwhelmingfor 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 agentsvoting insincerely to manipulate the decision, in part by investigating whether such manipulation can bemade computationally infeasible.Broader ImpactsThe proposed research will allow agents to coordinate when solving a complex problem, even if they havebeen created by different designers with different objectives. For example, robots in search-and-rescue orother exploration settings can vote over how they will divide the exploration. This allows a much greaterdiversity of agents to participate in such a task, undoubtedly leading to better results. Also, some of theresearch 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 thatthe U.S. retains expertise in and continues to shape this burgeoning research area. Of course, research is nota zero-sum game, and the PI plans to collaborate closely with the other researchers in the area. In fact, thisproposal corresponds to the PI?s part of a 12-investigator proposal that was just recommended for fundingby the European Science Foundation (ESF). This (NSF) proposal would also support the PI?s collaborationwith Jeff Rosenschein (Hebrew University); for this collaboration, Jeff and the PI already received a smallUS-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, andattract more women to computer science (as well as participate in other outreach activities).