research-article

Efficiency, Sequenceability and Deal-Optimality in Fair Division of Indivisible Goods

Authors:

Aurélie Beynier,

Sylvain Bouveret,

Michel Lemaître,

Nicolas Maudet,

Parham ShamsAuthors Info & Claims

AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

Pages 900 - 908

Published: 08 May 2019 Publication History

Abstract

In fair division of indivisible goods, using sequences of sincere choices (or picking sequences) is a natural way to allocate the objects. The idea is as follows: at each stage, a designated agent picks one object among those that remain. Another intuitive way to obtain an allocation is to give objects to agents in the first place, and to let agents exchange them as long as such "deals" are beneficial. This paper investigates these notions, when agents have additive preferences over objects, and unveils surprising connections between them, and with other efficiency and fairness notions. In particular, we show that an allocation is sequenceable if and only if it is optimal for a certain type of deals, namely cycle deals involving a single object. Furthermore, any Pareto-optimal allocation is sequenceable, but not the converse. Regarding fairness, we show that an allocation can be envy-free and non-sequenceable, but that every competitive equilibrium with equal incomes is sequenceable. To complete the picture, we show how some domain restrictions may affect the relations between these notions. Finally, we experimentally explore the links between the scales of efficiency and fairness.

References

[1]

Haris Aziz, Péter Biró, Jérôme Lang, Julien Lesca, and Jérôme Monnot. 2016a. Optimal Reallocation Under Additive and Ordinal Preferences. In Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'16). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 402--410.

Digital Library

[2]

Haris Aziz, Serge Gaspers, Simon Mackenzie, and Toby Walsh. 2015a. Fair assignment of indivisible objects under ordinal preferences. Artificial Intelligence, Vol. 227 (2015), 71--92.

Digital Library

[3]

Haris Aziz, Thomas Kalinowski, Toby Walsh, and Lirong Xia. 2016b. Welfare of Sequential Allocation Mechanisms for Indivisible Goods. In 22nd European Conference on Artificial Intelligence (ECAI 2016), Gal A. Kaminka, Maria Fox, Paolo Bouquet, Eyke Hü llermeier, Virginia Dignum, Frank Dignum, and Frank van Harmelen (Eds.). IOS Press, 787--794.

Digital Library

[4]

Haris Aziz, Toby Walsh, and Lirong Xia. 2015b. Possible and necessary allocations via sequential mechanisms. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI'15). AAAI Press, 468--474.

Digital Library

[5]

Moshe Babaioff, Noam Nisan, and Inbal Talgam-Cohen. 2017. Competitive equilibria with indivisible goods and generic budgets. arXiv preprint arXiv:1703.08150 (2017).

[6]

Sophie Bade. 2018. Matching with single-peaked preferences. Journal of Economic Theory, Vol. 180 (2018), 81--99.

[7]

Miguel A Ballester and Guillaume Haeringer. 2011. A characterization of the single-peaked domain. Social Choice and Welfare, Vol. 36, 2 (2011), 305--322.

[8]

Nikhil Bansal and Maxim Sviridenko. 2006. The Santa Claus problem. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (STOC '06). ACM, New York, NY, USA, 31--40.

Digital Library

[9]

Nicola Bianchessi, Jean-Franccois Cordeau, Jacques Desrosiers, Gilbert Laporte, and Vincent Raymond. 2007. A Heuristic for the Multi-satellite, Multi-orbit and Multi-user Management of Earth Observation Satellites. European Journal of Operational Research, Vol. 177, 2 (March 2007), 750--762.

[10]

David Black. 1948. On the rationale of group decision-making. The journal of political economy (1948), 23--34.

[11]

Sylvain Bouveret and Jérôme Lang. 2011. A general elicitation-free protocol for allocating indivisible goods. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11), Toby Walsh (Ed.). IJCAI/AAAI, Barcelona, Spain, 73--78.

Digital Library

[12]

Sylvain Bouveret and Michel Lemaître. 2016a. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems, Vol. 30, 2 (2016), 259--290.

Digital Library

[13]

Sylvain Bouveret and Michel Lemaître. 2016b. Efficiency and Sequenceability in Fair Division of Indivisible Goods with Additive Preferences. Proceedings of the Sixth International Workshop on Computational Social Choice (COMSOC'16). (2016).

[14]

Steven J. Brams, Marc D. Kilgour, and Christian Klamler. 2012. The undercut procedure: an algorithm for the envy-free division of indivisible items. Social Choice and Welfare, Vol. 39, 2--3 (2012), 615--631.

[15]

Steven J. Brams and Daniel King. 2005. Efficient Fair Division--Help the Worst off or Avoid Envy? Rationality and Society, Vol. 17, 4 (2005), 387--421.

[16]

Steven J. Brams and Alan D. Taylor. 1996. Fair Division -- From Cake-cutting to Dispute Resolution .Cambridge University Press.

[17]

Steven J. Brams and Alan D. Taylor. 2000. The Win-win Solution. Guaranteeing Fair Shares to Everybody .W. W. Norton & Company.

[18]

Simina Brânzei, Hadi Hosseini, and Peter Bro Miltersen. 2015. Characterization and computation of equilibria for indivisible goods. In International Symposium on Algorithmic Game Theory. Springer, 244--255.

[19]

Eric Budish. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, Vol. 119, 6 (dec 2011), 1061--1103.

[20]

Anastasia Damamme, Aurélie Beynier, Yann Chevaleyre, and Nicolas Maudet. 2015. The Power of Swap Deals in Distributed Resource Allocation. In The 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015). Istanbul, Turkey, 625--633.

Digital Library

[21]

Bart de Keijzer, Sylvain Bouveret, Tomas Klos, and Yingqian Zhang. 2009. On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. In Proceedings of the 1st International Conference on Algorithmic Decision Theory (ADT'09) (Lecture Notes in Artificial Intelligence). Springer Verlag, Venice, Italy, 98--110.

Digital Library

[22]

Edith Elkind, Martin Lackner, and Dominik Peters. 2016. Preference Restrictions in Computational Social Choice: Recent Progress. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9--15 July 2016 . 4062--4065.

Digital Library

[23]

Ulle Endriss, Nicolas Maudet, Fariba Sadri, and Francesca Toni. 2006. Negotiating Socially Optimal Allocations of Resources. Journal of Artificial Intelligence Research, Vol. 25 (2006), 315--348.

Digital Library

[24]

Irving Fisher. 1892. Mathematical Investigations in the Theory of Value and Prices, and Appreciation and Interest .Augustus M. Kelley, Publishers.

[25]

Duncan K. Foley. 1967. Resource Allocation and the Public Sector. Yale Economic Essays, Vol. 7, 1 (1967), 45--98.

[26]

Judy Goldsmith and Robert H Sloan. 2007. The AI conference paper assignment problem. In Proc. AAAI Workshop on Preference Handling for Artificial Intelligence, Vancouver. 53--57.

[27]

Thomas Kalinowski, Nina Narodytska, and Toby Walsh. 2013a. A Social Welfare Optimal Sequential Allocation Procedure. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI-13), Francesca Rossi (Ed.). IJCAI/AAAI, Beijing, China, 227--233.

Digital Library

[28]

Thomas Kalinowski, Nina Narodytska, Toby Walsh, and Lirong Xia. 2013b. Strategic Behavior when Allocating Indivisible Goods Sequentially. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI-12). AAAI Press, Bellevue, WA, 452--458.

Digital Library

[29]

David A Kohler and R Chandrasekaran. 1971. A class of sequential games. Operations Research, Vol. 19, 2 (1971), 270--277.

Digital Library

[30]

Michel Lemaître, Gérard Verfaillie, and Nicolas Bataille. 1999. Exploiting a Common Property Resource under a Fairness Constraint: a Case Study. In Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99). Stockholm, Sweden, 206--211.

Digital Library

[31]

Richard Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On Approximately Fair Allocations of Divisible Goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC-04). ACM, New York, NY, 125--131.

Digital Library

[32]

Hervé Moulin. 2003. Fair Division and Collective Welfare .MIT Press.

[33]

Abraham Othman, Tuomas Sandholm, and Eric Budish. 2010. Finding approximate competitive equilibria: efficient and fair course allocation. In Proceedings of the 9th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS-10), Wiebe van der Hoek, Gal A. Kaminka, Yves Lespérance, Michael Luck, and Sandip Sen (Eds.). IFAAMAS, Toronto, Canada, 873--880.

Digital Library

[34]

Senjuti Basu Roy, Ioanna Lykourentzou, Saravanan Thirumuruganathan, Sihem Amer-Yahia, and Gautam Das. 2015. Task assignment optimization in knowledge-intensive crowdsourcing. VLDB J., Vol. 24, 4 (2015), 467--491.

Digital Library

[35]

Tuomas W. Sandholm. 1998. Contract Types for Satisficing Task Allocation: I. Theoretical Results. In Proceedings of the AAAI Spring Symposium: Satisficing Models, Sandip Sen (Ed.). AAAI Press, Menlo Park, California, 68--75.

[36]

Amartya K Sen. 1966. A possibility theorem on majority decisions. Econometrica (1966), 491--499.

[37]

Lloyd Shapley and Herbert Scarf. 1974. On cores and indivisibility. Journal of mathematical economics, Vol. 1, 1 (1974), 23--37.

[38]

Jan Tinbergen. 1953. Redeljke Inkomensverdeling .N. V. DeGulden Pers., Haarlem.

[39]

Hal R. Varian. 1974. Equity, Envy and Efficiency . Journal of Economic Theory, Vol. 9 (1974), 63--91.

[40]

Léon Walras. 1874. Éléments d'économie politique pure ou Théorie de la richesse sociale 1st ed.). L. Corbaz.

Cited By

Hosseini HSikdar SVaish RXia LAgmon NAn BRicci AYeoh W(2023)Fairly Dividing Mixtures of Goods and Chores under Lexicographic PreferencesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598632(152-160)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598632

Index Terms

Efficiency, Sequenceability and Deal-Optimality in Fair Division of Indivisible Goods
1. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Intelligent agents
      2. Multi-agent systems

Recommendations

Fair Division of Indivisible Goods Among Strategic Agents
AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

We study fair division of indivisible goods among strategic agents in a single-parameter environment. This work specifically considers fairness in terms of envy freeness up to one good (EF1) and maximin share guarantee (MMS). We show that (in a single-...
The Price of Fairness for Indivisible Goods
Abstract
We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and equitability. However, ...
Mechanism design for fair division: allocating divisible items without payments
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

May 2019

2518 pages

ISBN:9781450363099

General Chairs:
Edith Elkind
University of Oxford, UK
,
Manuela Veloso
CMU (on leave), JPMorgan, USA
,
Program Chairs:
Noa Agmon
Bar-Ilan University, Israel
,
Matthew E. Taylor
Borealis AI, Canada

Sponsors

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 08 May 2019

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

ANR

Conference

AAMAS '19

Sponsor:

SIGAI

AAMAS '19: International Conference on Autonomous Agents and Multiagent Systems

May 13 - 17, 2019

Montreal QC, Canada

Acceptance Rates

AAMAS '19 Paper Acceptance Rate 193 of 793 submissions, 24%;

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
47
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hosseini HSikdar SVaish RXia LAgmon NAn BRicci AYeoh W(2023)Fairly Dividing Mixtures of Goods and Chores under Lexicographic PreferencesProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598632(152-160)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.5555/3545946.3598632

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents