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.