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

点击翻译按钮获取中文摘要

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.