AF: Small: Using Ordinal Information to Approximate Cardinal Objectives in Social Choice, Matching, Group Formation, and Assignment Problems

AF：小：使用序数信息来近似社会选择、匹配、群体形成和分配问题中的基本目标

• 批准号: 1527497
• 负责人: Elliot Anshelevich
• 金额: $ 33.45万
• 依托单位: Rensselaer Polytechnic Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-06-15 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1527497&HistoricalAwards=false
• 关键词: AF; Small; Using; Ordinal; Information

Many modern algorithms must make decisions using only limited information: they not only need to make the best choices given the input, but also don't know what the "true" input actually is; and yet they are required to make good choices anyway. This problem arises often in settings where the goal is to maximize the total happiness (a.k.a. social welfare or total utility) of the system, such as social choice settings in which voters submit their preferences for different alternatives, matching settings (e.g., matching people with job openings or organ donors with patients), assigning people to groups or projects, economic market settings, and many others. In all of these settings, the people or agents involved may care deeply about which outcome is selected (e.g., which alternative is selected by the voting mechanism, or which patients are assigned a donated kidney), with the mechanism designer's goal being to maximize the overall welfare and satisfaction. Unfortunately, in all these applications, only limited information is usually available: it is relatively easy to obtain *ordinal* information (which choice is preferred to which other choice by each participant), but almost impossible to obtain the underlying numerical information (how *much* each choice is preferred by each participant). This project will use a novel notion of approximation to give new insight into the design and evaluation of many mechanisms for the settings mentioned above. The approximation algorithms resulting from this project will be used to suggest new protocols, which would not only optimize some notion of fairness (as is common in social choice), or maximize the size of a matching (as is common in kidney exchange), but would have provable guarantees on the quality of the outcomes. One reason why such guarantees have not been considered in the past is that without the knowledge of exact numerical utilities or exact compatibilities between matches, protocols can only rely on ordinal, or otherwise limited, information. However, as preliminary work shows, one can often design algorithms which behave well no matter what the *true* information is, as long as the underlying (unknown) numerical values have some reasonable structure, or are at least correlated in some way, which is certainly the case for most applications. Because of this, this project will provide a different perspective, and will result in algorithms which produce provably good outcomes while using only limited ordinal information. Due to the applications touched by this project, the work done should be of interest to researchers in many fields, including Social Choice, Artificial Intelligence, Game Theory, Social Networks, and Economics. This research will be strongly complemented by the PI's education plan, which includes teaching several courses with research components, presenting this work at numerous scientific seminars, and recruiting several graduate and undergraduate students to work on this project.The primary goal of this project is to design and analyze algorithms which only know ordinal information, and yet create solutions which are provably close to the "true" optimal solution: the one which would be chosen if the full numerical information were known. The project will specifically focus on the settings of social choice, matching, group formation, and economic markets. Very little is known about approximation algorithms in the presence of ordinal information, and designing such algorithms for the settings above will likely require new and interesting techniques. When the numerical values are completely uncorrelated, it is of course impossible to form good approximations from only ordinal information, so this work will involve looking at different kinds of correlations (e.g., lying in a metric space, symmetric values, values from a common distribution, etc), and determining how much power this structure gives to the ordinal information, as compared to the true numerical information. The PI will also consider optimization problems with other interesting constraints which deserve further study, focusing especially on computing good solutions in the presence of self-interested agents, in the contexts of social choice, matching, and envy-free pricing. This work should lead to basic understanding of the fundamental power of ordinal information, by determining under which settings and conditions ordinal information is enough to approximate the numerical truth, and when such an approximation is impossible.

许多现代算法必须仅使用有限的信息做出决策：它们不仅需要在给定输入的情况下做出最佳选择，而且不知道“真实”输入实际上是什么；但无论如何，他们都必须做出正确的选择。这个问题经常出现在目标是最大化系统的总幸福（又称社会福利或总效用）的环境中，例如选民提交他们对不同替代方案的偏好的社会选择环境、匹配环境（例如，将人员与职位空缺或器官捐赠者与患者进行匹配）、将人们分配到团体或项目、经济市场环境等等。在所有这些设置中，所涉及的人员或代理人可能非常关心选择哪种结果（例如，投票机制选择哪种替代方案，或者为哪些患者分配捐赠的肾脏），机制设计者的目标是最大化总体福利和满意度。不幸的是，在所有这些应用中，通常只能获得有限的信息：相对容易获得“顺序”信息（每个参与者更喜欢哪个选择），但几乎不可能获得底层的数字信息（每个参与者对每个选择的偏好程度）。该项目将使用一种新颖的近似概念，为上述设置的许多机制的设计和评估提供新的见解。该项目产生的近似算法将用于提出新的协议，这不仅会优化某些公平概念（如社会选择中常见的情况），或最大化匹配的规模（如肾脏交换中常见的情况），而且会对结果的质量提供可证明的保证。过去没有考虑此类保证的原因之一是，如果不了解确切的数字效用或匹配之间的确切兼容性，协议只能依赖序数或其他有限的信息。然而，正如初步工作所示，无论“真实”信息是什么，只要底层（未知）数值具有某种合理的结构，或者至少以某种方式相关，人们通常可以设计出表现良好的算法，这对于大多数应用来说都是这种情况。因此，该项目将提供不同的视角，并将产生仅使用有限序数信息即可产生可证明良好结果的算法。 由于该项目涉及的应用，所做的工作应该会引起许多领域的研究人员的兴趣，包括社会选择、人工智能、博弈论、社交网络和经济学。这项研究将得到 PI 教育计划的有力补充，其中包括教授几门带有研究内容的课程，在众多科学研讨会上展示这项工作，并招募几名研究生和本科生来从事该项目。该项目的主要目标是设计和分析仅知道序数信息的算法，并创建可证明接近“真实”最优解决方案的解决方案：如果有完整的数值信息，将选择该解决方案 被知道了。该项目将特别关注社会选择、匹配、群体形成和经济市场的设置。人们对存在序数信息的近似算法知之甚少，并且为上述设置设计此类算法可能需要新的有趣的技术。当数值完全不相关时，当然不可能仅从序数信息形成良好的近似，因此这项工作将涉及查看不同类型的相关性（例如，位于度量空间中、对称值、共同分布的值等），并确定与真实的数值信息相比，该结构赋予序数信息多少权力。 PI 还将考虑具有其他值得进一步研究的有趣约束的优化问题，特别关注在存在自利代理的情况下，在社会选择、匹配和无嫉妒定价的背景下计算良好的解决方案。这项工作应该通过确定在哪些设置和条件下序数信息足以近似数字事实，以及何时不可能进行这种近似，从而对序数信息的基本力量有基本的了解。

项目成果

The Distortion of Distributed Metric Social Choice

分布式度量社会选择的扭曲

• DOI: 10.1007/978-3-030-94676-0_26
• 发表时间: 2022
• 期刊: Artificial intelligence
• 影响因子: 14.4
• 作者: Anshelevich, Elliot;Filos-Ratsikas, Aris;Voudouris, Alexandros A.
• 通讯作者: Voudouris, Alexandros A.

Distortion in Social Choice Problems: An Annotated Reading List.

社会选择问题的扭曲：带注释的阅读清单。

• 发表时间: 2021
• 期刊: SIGecom exchanges
• 作者: Anshelevich, Elliot;Filos-Ratsikas, Aris;Shah, Nisarg;Voudouris, Alexandros A
• 通讯作者: Voudouris, Alexandros A

Distortion in Social Choice Problems: The First 15 Years and Beyond

社会选择问题的扭曲：前 15 年及以后

• DOI: 10.24963/ijcai.2021/589
• 发表时间: 2021
• 期刊: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence Survey Track.
• 作者: Anshelevich, Elliot;Filos-Ratsikas, Aris;Shah, Nisarg;Voudouris, Alexandros A.
• 通讯作者: Voudouris, Alexandros A.

How to Amend a Constitution? Model, Axioms, and Supermajority Rules.

如何修改宪法？

• 发表时间: 2021
• 期刊: AAMAS Conference proceedings
• 作者: Ben Abramowitz, Ehud Shapiro