RI: Small: Computational Social Choice: For the People

RI：小：计算社会选择：为了人民

• 批准号: 1714140
• 负责人: Ariel Procaccia
• 金额: $ 42万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-08-01 至 2020-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1714140&HistoricalAwards=false
• 关键词: RI; Small; Computational; Social; Choice

The field of social choice theory deals with aggregating the preferences or opinions of individuals towards a collective decision; voting is a paradigmatic example. This rich space of problems has long been studied in economics and mathematics, leading to a slew of striking theoretical results. But real-world applications have been sparse. From the AI viewpoint, the study of computational social choice is seen by many researchers as a central component in the effort to build the foundations of multiagent systems. This research extends this theoretical work in computational social choice to enable people to make joint decisions. This project aims to put human decision making at the center of computational social choice, while leveraging the very approaches and techniques developed for voting in multiagent systems. The research plan is directly motivated by the not-for-profit website RoboVote.org, which enables people to implement whichever voting methods appear to be best based on analysis and empirical evidence. This project will realize the full potential of RoboVote for education, outreach, and societal impact with the aim of transforming the way people make group decisions in a wide range of applications.The specific challenges that will be tackled are divided into two subsets, corresponding to the two fundamentally different types of polls currently modeled on RoboVote. 1. Subjective preferences: Preferences are subjective when the desirability of each alternative is a matter of taste. RoboVote aggregates subjective rankings by assuming that voters have latent utilities for the alternatives, and selecting an outcome that maximizes the sum of utilities by using the reported rankings as a proxy for those utilities. An immediate gap that must be addressed is that the approach does not extend to the case where the outcome is a ranking. A second, far-reaching challenge is to rethink the way voters express their preferences, in order to obtain more useful information regarding their actual utility functions while keeping the cognitive burden low. Finally, the project includes a study of the axiomatic properties of optimal aggregation methods in the foregoing framework. 2. Objective opinions: In this scenario, some alternatives are objectively better than others, but this objective comparison is not known to voters. The solutions deployed on RoboVote aim to handle worst-case noise. The research aims to create and test algorithms that improve upon naïve approaches, especially by building on synergistic advances in the design of fixed-parameter tractable algorithms.

社会选择理论的领域涉及将个人的偏好或意见聚集到集体决策中;投票是一个典型的例子。这个丰富的问题空间长期以来一直在经济学和数学中进行研究，导致了一系列引人注目的理论结果。但在现实世界中的应用却很少。从人工智能的角度来看，计算社会选择的研究被许多研究人员视为建立多智能体系统基础的核心组成部分。这项研究扩展了计算社会选择的理论工作，使人们能够做出联合决策。该项目旨在将人类决策置于计算社会选择的中心，同时利用多智能体系统中为投票而开发的方法和技术。 该研究计划的直接动机是非营利网站RoboVote.org，该网站使人们能够根据分析和经验证据实施任何最佳投票方法。该项目将充分发挥RoboVote在教育、推广和社会影响方面的潜力，旨在改变人们在广泛应用中做出群体决策的方式。将解决的具体挑战分为两个子集，对应于目前以RoboVote为模型的两种根本不同类型的民意调查。 1.主观偏好：当每个选择的可取性是一个品味问题时，偏好是主观的。RoboVote通过假设投票者对备选方案具有潜在效用来聚合主观排名，并通过使用报告的排名作为这些效用的代理来选择使效用总和最大化的结果。必须解决的一个直接差距是，该方法没有扩展到结果是排名的情况。第二个影响深远的挑战是重新思考选民表达偏好的方式，以便在保持低认知负担的同时获得更多关于其实际效用函数的有用信息。最后，该项目包括在上述框架中的最佳聚合方法的公理性质的研究。 2.客观意见：在这种情况下，一些替代方案客观上比其他方案更好，但选民不知道这种客观比较。RoboVote上部署的解决方案旨在处理最坏情况下的噪音。该研究旨在创建和测试改进朴素方法的算法，特别是通过建立在固定参数易处理算法设计方面的协同进步。

项目成果

Collaborative PAC Learning

• 发表时间: 2017-12
• 作者: Avrim Blum;Nika Haghtalab;Ariel D. Procaccia;Mingda Qiao

Ignorance Is Almost Bliss: Near-Optimal Stochastic Matching with Few Queries

无知几乎是福：几乎没有查询的近乎最优随机匹配

• DOI: 10.1287/opre.2019.1856
• 发表时间: 2020
• 期刊: Operations Research
• 影响因子: 2.7
• 作者: Blum, Avrim;Dickerson, John P.;Haghtalab, Nika;Procaccia, Ariel D.;Sandholm, Tuomas;Sharma, Ankit
• 通讯作者: Sharma, Ankit

Strategyproof Mean Estimation from Multiple-Choice Questions

多项选择题的策略证明均值估计

• 发表时间: 2020
• 期刊: ICML
• 作者: Kahng, A.;Kehne, G.;Procaccia, A.
• 通讯作者: Procaccia, A.

Migration as Submodular Optimization

• DOI: 10.1609/aaai.v33i01.3301549
• 发表时间: 2018-09
• 期刊: ArXiv
• 作者: Paul Gölz;Ariel D. Procaccia

Fair Rent Division on a Budget

预算公平租金司

• 发表时间: 2018
• 期刊: AAAI 2018
• 作者: Procaccia, A. D.;Velez, R. A.;Yu, D.
• 通讯作者: Yu, D.