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

AF：小：社会选择、设施位置和其他信息有限的设置中的扭曲和代理偏好的质量

• 批准号: 2006286
• 负责人: Elliot Anshelevich
• 金额: $ 36.17万
• 依托单位: Rensselaer Polytechnic Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006286&HistoricalAwards=false
• 关键词: AF; Small; Distortion; Quality; Agent

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.

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

项目成果

Optimizing Multiple Simultaneous Objectives for Voting and Facility Location.

优化投票和设施选址的多个同时目标。

• 发表时间: 2023-02
• 期刊: Proceedings of the AAAI Conference on Artificial Intelligence
• 作者: Han, Yue;Jerrett, Chris;Anshelevich, Elliot
• 通讯作者: Anshelevich, Elliot

Distortion in Social Choice Problems: An Annotated Reading List.

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

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

The Distortion of Distributed Metric Social Choice

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

• DOI: 10.1007/978-3-030-94676-0_26
• 发表时间: 2022-07
• 期刊: Artificial intelligence
• 影响因子: 14.4
• 作者: Anshelevich, Elliot;Filos;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-08
• 期刊: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence Survey Track.
• 作者: Anshelevich, Elliot;Filos;Shah, Nisarg;Voudouris, Alexandros A.
• 通讯作者: Voudouris, Alexandros A.