Pareto optimal allocation under uncertain preferences

Haris Aziz, Ronald de Haan, Baharak Rastegari

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

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.
Original languageEnglish
Title of host publicationAAMAS '17
Subtitle of host publicationProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems
Place of PublicationRichland, SC
PublisherInternational Foundation for Autonomous Agents and MultiAgent Systems
Pages1472-1474
Number of pages3
Publication statusPublished - 8 May 2017

Keywords

  • Pareto optimality, house allocation, matching under preferences, uncertain preferences

Fingerprint Dive into the research topics of 'Pareto optimal allocation under uncertain preferences'. Together they form a unique fingerprint.

Cite this