AF: Small: Distortion and the Quality of Agent Preferences in Social Choice, Facility Location, and Other Settings with Limited Information

这个项目的主要目标是在信息有限的情况下为各种设置设计和分析算法。只有有限的信息可用，而选择最佳结果取决于潜在的(不可用的)真相的情况很常见。例如，考虑社会选择(即投票)环境，在这种环境中，目标是选择尽可能有利于选民的结果，但唯一可用的信息是选民对结果的有限偏好，而不是这些偏好的强度或结果对选民的确切好处。同样的问题也发生在匹配问题上(例如将学生与学校、申请者与工作人员或可用肾脏与患者匹配)、集群和设施位置(例如选择在哪里放置新的邮局或其他服务)，以及许多其他存在多个具有个人兴趣的独立代理人的环境，包括项目分配和经济市场。在所有这些设置中，算法设计者的目标是选择幸福最大化、社会福利最大化、公平以及其他目标的结果。不幸的是，这些设置还包括社交交互，在社交交互中，尽管获得对代理首选项和实用程序的基本理解是可行的，但可能很难得出代理首选项和实用程序的真实详细结构。该项目旨在开发用于这些设置的算法和技术，以提供接近真正最优的结果(如果算法是全知的，并且知道有关代理偏好和好处的所有信息，则获得的结果)，而只使用非常有限的信息。这类算法将允许上述许多设置获得更好的结果，或者包括保证即使有更多的数据和信息，也不可能有更好的结果选择，这应该会增加用户对结果的满意度。本项目将专注于上述设置，其中包含许多具有个人偏好的独立代理。它将为这些设置开发算法，这些设置将只接受关于代理首选项的有限信息作为输入，但与基于完全(不可用)代理首选项的最优解相比，将产生具有可证明的近似保证的结果。在该项目中形成的近似算法可以被用来建议新的协议，其不仅将优化某些公平性概念(如在这种设置中常见的)，或者专注于仅计算最优解而不考虑其他期望的属性，并且将取而代之地对所得到的(非最优)解的质量具有可证明的保证。该项目将重点关注的主要问题如下。(1)对于上述设置，本项目将仔细研究关于代理偏好的哪些类型的信息使算法的性能接近全知最优，以及哪些类型的信息使算法的性能不可能达到全知最优，以及量化已知信息量和结果质量之间的权衡。这个项目将考虑序数信息、阈值信息、能够选择哪些部分的真实信息是已知的，以及许多其他类型的有限信息。与给定的有限信息已经产生好的解决方案的设置相比，理解这种权衡允许了解在哪些设置中值得努力工作以获得一点额外的信息。(2)本项目对形成同时逼近多个目标的算法特别感兴趣，这些目标包括社会成本、公平目标、选择结果的多样性和解的稳定性。(3)该项目还将致力于研究代理人自身利益如何与结果解决方案的质量相互作用，以及使用特定类型的有限信息可以获得什么。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The main goal of this project is to design and analyze algorithms for various settings with limited information. Settings where only limited information is available, while choosing the best outcomes depends on the underlying (unavailable) truth, are common. For example, consider social choice (i.e., voting) settings in which the goal is to choose outcomes which benefit the voters as much as possible, but the only information available is the limited preferences of the voters for the outcomes, not the strength of those preferences or the exact benefits of the outcomes for the voters. The same occurs in matching problems (such as matching students with schools, applicants with jobs, or available kidneys with patients), clustering and facility location (such as choosing where to place new post offices or other services), and many other settings with the presence of multiple independent agents with individual interests, including project assignment and economic markets. In all these settings, the goal of the algorithm designer is to choose outcomes maximizing happiness, the welfare of society, fairness, as well as other objectives. Unfortunately, these settings also include social interactions where eliciting the true detailed structure of the agent preferences and utilities may be difficult, although obtaining a basic understanding of it is feasible. This project aims to develop algorithms and techniques for these settings to provide outcomes which are close to the true optimum (the one obtained if the algorithm were omniscient and knew all the information about the agent preferences and benefits), while only using very limited information. Such algorithms would allow better outcomes for many settings mentioned above, or include guarantees that much better outcome choice would not be possible, even with much more data and information, which should increase the satisfaction of the users with the resulting outcomes.This project will focus on the settings mentioned above containing many independent agents with individual preferences. It will develop algorithms for these settings which will take as input only limited information about the agent preferences, but will produce outcomes with provable approximation guarantees as compared with optimum solutions based on the full (unavailable) agent preferences. Approximation algorithms formed in this project could be used to suggest new protocols, which would not only optimize some notion of fairness (as is common in such settings), or focus on computing only optimum solutions regardless of sacrificing other desirable properties, but would instead have provable guarantees on the quality of the resulting (non-optimal) solutions. The main issues this project will focus on are as follows. (1) For the settings mentioned above, this project will perform a careful study of which types of information about agent preferences allow algorithms with performance close to that of the omniscient optimum, and which types of information make such performance impossible, as well as quantify the tradeoffs between how much information is known and the quality of the resulting outcomes. This project will consider ordinal information, threshold information, being able to select which part of the true information is known, and many other types of limited information. Understanding such tradeoffs allows the knowledge of in which settings it is worth working hard to obtain a little bit of extra information, compared to settings in which the given limited information already yields good solutions. (2) This project is especially interested in forming algorithms which approximate multiple objectives simultaneously, including social cost, fairness objectives, the diversity of selected outcomes, and stability of solutions. (3) This project will also devote a significant amount of effort to studying how agent self-interest interacts with the quality of resulting solutions and what is possible to obtain using specific types of limited information.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.