AF: Small: Using Ordinal Information to Approximate Cardinal Objectives in Social Choice, Matching, Group Formation, and Assignment Problems

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

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.