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

这个项目的主要目标是设计和分析算法，用于各种信息有限的设置。只有有限信息可用的环境，而选择最佳结果取决于潜在的（不可用的）真相，这是常见的。例如，考虑社会选择（即，投票）设置，其中目标是选择尽可能有利于选民的结果，但唯一可用的信息是选民对结果的有限偏好，而不是这些偏好的强度或结果对选民的确切益处。同样的情况也发生在匹配问题上（比如将学生与学校、申请人与工作、可用肾脏与病人相匹配）、集群和设施选址（比如选择在哪里设立新的邮局或其他服务），以及许多其他存在多个具有个人利益的独立代理人的环境中，包括项目分配和经济市场。在所有这些设置中，算法设计者的目标是选择最大化幸福、社会福利、公平以及其他目标的结果。不幸的是，这些设置还包括社会互动，其中引出代理偏好和效用的真实详细结构可能是困难的，尽管获得基本的理解是可行的。该项目旨在为这些设置开发算法和技术，以提供接近真正最优的结果（如果算法无所不知，并且知道有关代理偏好和利益的所有信息，则获得的结果），同时只使用非常有限的信息。这样的算法将允许更好的结果为上述许多设置，或包括保证，更好的结果的选择将是不可能的，即使有更多的数据和信息，这应该增加用户的满意度与所产生的outcomes.This项目将集中在上述设置包含许多独立的代理人与个人喜好。它将为这些设置开发算法，这些设置将只接受有关代理偏好的有限信息作为输入，但与基于完整（不可用）代理偏好的最佳解决方案相比，将产生具有可证明近似保证的结果。在这个项目中形成的近似算法可以用来建议新的协议，这不仅会优化一些公平的概念（在这种设置中很常见），或者只专注于计算最优解而不牺牲其他期望的属性，但会对所得（非最优）解的质量有可证明的保证。该项目将重点关注的主要问题如下。(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.