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

(RI hcc)-小：计算社会选择：聚合组合域中的偏好

• 批准号: 0812113
• 负责人: Vincent Conitzer
• 金额: $ 42.92万
• 依托单位: Duke University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0812113&HistoricalAwards=false
• 关键词: RI+hcc; Small; Computational; Social; Choice

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

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