Loading...
Please wait, while we are loading the content...
Similar Documents
Pareto Optimal Allocation under Uncertain Preferences : extended abstract
| Content Provider | Semantic Scholar |
|---|---|
| Author | Aziz, Haris Haan, Roland De Rastegari, Baharak Das, Sanmay Durfee, Edmund H. Larson, Kate Winikoff, Michael |
| Copyright Year | 2017 |
| 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. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://www.ac.tuwien.ac.at/files/tr/ac-tr-17-007.pdf |
| Alternate Webpage(s) | http://www.ifaamas.org/Proceedings/aamas2017/pdfs/p1472.pdf |
| Journal | AAMAS 2017 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
