RI: Small: Computational Social Choice: For the People

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

• 批准号: 2024287
• 负责人: Ariel Procaccia
• 金额: $ 24.32万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-01-01 至 2021-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2024287&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上部署的解决方案旨在处理最坏情况下的噪音。这项研究的目的是创建和测试改进幼稚方法的算法，特别是通过在设计固定参数易处理算法方面的协同进步。

项目成果

The Unreasonable Fairness of Maximum Nash Welfare

• DOI: 10.1145/2940716.2940726
• 发表时间: 2016-07
• 期刊: Proceedings of the 2016 ACM Conference on Economics and Computation
• 作者: I. Caragiannis;David Kurokawa;H. Moulin;Ariel D. Procaccia;Nisarg Shah;Junxing Wang

Fair Division with Binary Valuations: One Rule to Rule Them All

二元估值的公平除法：一条规则来统治它们

• 发表时间: 2020
• 期刊: WINE
• 作者: Halpern, Daniel;Shah, Nisarg;Psomas, Alexandros;Procaccia, Ariel D.
• 通讯作者: Procaccia, Ariel D.

In This Apportionment Lottery, the House Always Wins

在这场分配彩票中，众议院总是获胜

• 发表时间: 2022
• 期刊: EC'22
• 作者: Paul Gölz, Dominik Peters

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.