| Autor: |
Aziz, H., de Haan, R., Rastegari, B., Das, S., Durfee, E., Larson, K., Winikoff, M. |
| Přispěvatelé: |
ILLC (FNWI), Logic and Computation (ILLC, FNWI/FGw) |
| Jazyk: |
angličtina |
| Rok vydání: |
2017 |
| Zdroj: |
AAMAS '17: proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems : May, 8-12, 2017, São Paulo, Brazil, 3, 1472-1474 |
| Popis: |
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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
