- Author
- Year
- 2017
- host editors
-
S. Das
E. Durfee
K. Larson
M. Winikoff - Title
- Pareto Optimal Allocation under Uncertain Preferences
- Event
- 16th International Conference on Autonomous Agents and Multiagent Systems
- Book/source title
- AAMAS '17
- Book/source subtitle
- proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems : May, 8-12, 2017, São Paulo, Brazil
- Pages (from-to)
- 1472-1474
- Publisher
- Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems
- Volume (Publisher)
- 3
- Document type
- Conference contribution
- Faculty
- Interfacultary Research
- Institute
- Institute for Logic, Language and Computation (ILLC)
- 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.
- Link
- Final publisher version
Final publisher version - Language
- English
- Note
- Extended abstract
- Persistent Identifier
- https://hdl.handle.net/11245.1/dac38014-8244-4e3c-9f8e-5c3c0d0eedf2
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.