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

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

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.