Abstract
The assignment problem is one of the most wellstudied 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 difference and similarities in the complexity of the two models.
Original language | English |
---|---|
Title of host publication | 26th International Joint Conference on Artificial Intelligence, IJCAI 2017 |
Publisher | International Joint Conferences on Artificial Intelligence |
Pages | 77-83 |
Number of pages | 7 |
ISBN (Electronic) | 9780999241103 |
DOIs | |
Publication status | Published - 2017 |
Event | 26th International Joint Conference on Artificial Intelligence, IJCAI 2017 - Melbourne, Australia Duration: 19 Aug 2017 → 25 Aug 2017 |
Conference
Conference | 26th International Joint Conference on Artificial Intelligence, IJCAI 2017 |
---|---|
Country/Territory | Australia |
City | Melbourne |
Period | 19/08/17 → 25/08/17 |
Keywords
- agent based and multi- agent systems
- social choice theory