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

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

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).