Abstract
The assignment problem is one of the most well-studied settings in social choice, matching, and discrete allocation. We consider this problem with the additional feature that agents' preferences involve uncertainty. The setting with uncertainty leads to a number of interesting questions including the following ones. How to compute an assignment with the highest probability of being Pareto optimal? What is the complexity of computing the probability that a given assignment is Pareto optimal? Does there exist an assignment that is Pareto optimal with probability one? We consider these problems under two natural uncertainty models: (1) the lottery model in which each agent has an independent probability distribution over linear orders and (2) the joint probability model that involves a joint probability distribution over preference profiles. For both of these models, we present a number of algorithmic and complexity results highlighting the differences and similarities in the complexity of the two models.
| Original language | English |
|---|---|
| Title of host publication | AAMAS '17 |
| Subtitle of host publication | Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems |
| Place of Publication | Richland, SC |
| Publisher | International Foundation for Autonomous Agents and MultiAgent Systems |
| Pages | 1472-1474 |
| Number of pages | 3 |
| Publication status | Published - 8 May 2017 |
Keywords
- Pareto optimality, house allocation, matching under preferences, uncertain preferences