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.
|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|
|Number of pages||3|
|Publication status||Published - 8 May 2017|
- Pareto optimality, house allocation, matching under preferences, uncertain preferences