Cited By
View all- Cechlárová KGourvès LLesca J(2019)On the problem of assigning PhD grantsProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367032.3367052(130-136)Online publication date: 10-Aug-2019
Pareto optimal allocation under uncertain preferences
Pages 77 - 83
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 difference and similarities in the complexity of the two models.
References
[1]
Atila Abdulkadiroglu and Tayfun Sönmez. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica , 66(3):689-701, 1998.
[2]
Atila Abdulkadiroglu and Tayfun Sönmez. House allocation with existing tenants. Journal of Economic Theory , 88(2):233-260, 1999.
[3]
David J. Abraham, Katarína Cechlárová, David F. Manlove, and Kurt Mehlhorn. Pareto optimality in house allocation problems. In Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC) , volume 3341 of Lecture Notes in Computer Science (LNCS) , pages 1163-1175, 2005.
[4]
Haris Aziz and Bart de Keijzer. Housing markets with indifferences: a tale of two mechanisms. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI) , pages 1249-1255, 2012.
[5]
Haris Aziz, Simon Mackenzie, Lirong Xia, and Chun Ye. Ex post efficiency of random assignments. In Proceedings of the 14th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) , pages 1639-1640, 2015.
[6]
Haris Aziz, Péter Biró, Serge Gaspers, Ronald de Haan, Nicholas Mattei, and Baharak Rastegari. Stable matching with uncertain linear preferences. In Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT) , pages 195-206, 2016.
[7]
Haris Aziz, Péter Biró, Jérôme Lang, Julien Lesca, and Jérôme Monnot. Optimal reallocation under additive and ordinal preferences. In Proceedings of the 15th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS) , pages 402-410, 2016.
[8]
Haris Aziz, Jérôme Lang, and Jérôme Monnot. Computing Pareto Optimal Committees. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI) , pages 60-66, 2016.
[9]
Anna Bogomolnaia and Hervé Moulin. A new solution to the random assignment problem. Journal of Economic Theory , 100(2):295-328, 2001.
[10]
Steven J. Brams and Daniel L. King. Efficient fair division: Help the worst off or avoid envy? Rationality and Society , 17(4):387-421, 2005.
[11]
Joanna Drummond and Craig Boutilier. Preference elicitation and interview minimization in stable matchings. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI) , pages 645-653. AAAI Press, 2014.
[12]
Aytek Erdil and Haluk Ergin. Two-sided matching with indi_erences. June 2015.
[13]
Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM Journal on Computing , 33(4):892-922, 2004.
[14]
Jörg Flum and Martin Grohe. Parameterized Complexity Theory . Texts in Theoretical Computer Science. Springer-Verlag, 2006.
[15]
Peter Gärdenfors. Assignment problem based on ordinal preferences. Management Science , 20:331-340, 1973.
[16]
Noam Hazon, Yonatan Aumann, Sarit Kraus, and Michael Wooldridge. On the evaluation of election outcomes under uncertainty. Artificial Intelligence , 189:1-18, 2012.
[17]
Piotr Krysta, David Manlove, Baharak Rastegari, and Jinshan Zhang. Size versus truthfulness in the house allocation problem. In Proceedings of the 15th ACM Conference on Economics and Computation (ACM-EC) , pages 453-470. ACM Press, 2014.
[18]
David Manlove. Algorithmics of Matching Under Preferences . World Scientific Publishing Company, 2013.
[19]
Baharak Rastegari, Anne Condon, Nicole Immorlica, and Kevin Leyton-Brown. Two-sided matching with partial information. In Proceedings of the 14th ACM Conference on Electronic Commerce (ACM-EC) , pages 733-750. ACM Press, 2013.
[20]
Baharak Rastegari, Anne Condon, Nicole Immorlica, Robert Irving, and Kevin Leyton-Brown. Reasoning about optimal stable matchings under partial information. In Proceedings of the 15th ACM Conference on Economics and Computation (ACM-EC) , pages 431-448. ACM Press, 2014.
[21]
Daniela Saban and Jay Sethuraman. House allocation with indifferences: a generalization and a unified view. In Proceedings of the 14th ACM Conference on Electronic Commerce (ACM-EC) , pages 803-820. ACM Press, 2013.
[22]
Daniela Saban and Jay Sethuraman. The complexity of computing the random priority allocation matrix. Mathematics of Operations Research , 40(4):1005 - 1014, 2015.
[23]
Lars-Gunnar Svensson. Queue allocation of indivisible goods. Social Choice and Welfare , 11:323- 330, 1994.
[24]
Lars-Gunnar Svensson. Strategy-proof allocation of indivisible goods. Social Choice and Welfare , 16(4):557-567, 1999.
[25]
Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing , 8(3):410-421, 1979.
- Pareto optimal allocation under uncertain preferences
Recommendations
Pareto Optimal Allocation under Uncertain Preferences
AAMAS '17: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent SystemsThe 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 ...
Pareto optimal allocation under compact uncertain preferences
AAAI'19/IAAI'19/EAAI'19: Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial IntelligenceThe assignment problem is one of the most well-studied settings in multi-agent resource allocation. Aziz, de Haan, and Rastegari (2017) considered this problem with the additional feature that agents' preferences involve uncertainty. In particular, they ...
Hypervolume Optimal -Distributions on Line-Based Pareto Fronts in Three Dimensions
Parallel Problem Solving from Nature – PPSN XVIAbstractHypervolume optimal -distribution is a fundamental research topic which investigates the distribution of solutions on the Pareto front for hypervolume maximization. It has been theoretically shown that the optimal distribution of solutions on a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- Australian Comp Soc: Australian Computer Society
- NSF: National Science Foundation
- Griffith University
- University of Technology Sydney
- AI Journal: AI Journal
Publisher
AAAI Press
Publication History
Published: 19 August 2017
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
Cited By
View all- Cechlárová KGourvès LLesca J(2019)On the problem of assigning PhD grantsProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367032.3367052(130-136)Online publication date: 10-Aug-2019