Optimal Reallocation under Additive and Ordinal Preferences

Aziz, Haris; Biro, Peter; Lang, Jérôme; Lesca, Julien; Monnot, Jérôme

Aziz, Haris; Biro, Peter; Lang, Jérôme; Lesca, Julien; Monnot, Jérôme (2016), Optimal Reallocation under Additive and Ordinal Preferences, dans Catholijn M. Jonker, Stacy Marsella, John Thangarajah, Karl Tuyls, AAMAS '16 Proceedings of the 2016 International Conference on Autonomous Agents And Multiagent Systems, Singapore, May 9-13, 2016, IFAAMAS, p. 402-410

Type

Communication / Conférence

Lien vers un document non conservé dans cette base

http://arxiv.org/abs/1604.01091v1

Date

2016

Titre de l'ouvrage

AAMAS '16 Proceedings of the 2016 International Conference on Autonomous Agents And Multiagent Systems, Singapore, May 9-13, 2016

Auteurs de l’ouvrage

Catholijn M. Jonker, Stacy Marsella, John Thangarajah, Karl Tuyls

Éditeur

IFAAMAS

Isbn

978-1-4503-4239-1

Pages

402-410

Métadonnées

Afficher la notice complète

Auteur(s)

Aziz, Haris
Biro, Peter
Lang, Jérôme
Lesca, Julien
Monnot, Jérôme

Résumé (EN)

Reallocating resources to get mutually beneficial outcomes is a fundamental problem in various multi-agent settings. In the first part of the paper we focus on the setting in which agents express additive cardinal utilities over objects. We present computational hardness results as well as polynomial-time algorithms for testing Pareto optimality under different restrictions such as two utility values or lexicographic utilities. In the second part of the paper we assume that agents express only their (ordinal) preferences over single objects, and that their preferences are additively separable. In this setting, we present characterizations and polynomial-time algorithms for possible and necessary Pareto optimality.

Mots-clés

Computational Social Choice; Indivisible goods; Pareto; Computational Complexity