A generalization of the AL method for fair allocation of indivisible objects

Haris Aziz ()
Additional contact information
Haris Aziz: NICTA and UNSW

Economic Theory Bulletin, 2016, vol. 4, issue 2, No 13, 307-324

Abstract: Abstract We consider the assignment problem in which agents express ordinal preferences over m objects and the objects are allocated to the agents based on the preferences. In a recent paper Brams, Kilgour, and Klamler (Not AMS 61(2):130–141, 2014) , presented the AL method to compute an envy-free assignment for two agents. The AL method crucially depends on the assumption that agents have strict preferences over objects. We generalize the AL method to the case where agents may express indifferences and prove the axiomatic properties satisfied by the algorithm. As a result of the generalization, we also get a O(m) speedup on previous algorithms to check whether a complete envy-free assignment exists or not. Finally, we show that unless $$P=NP$$ P = N P , there can be no polynomial time extension of GAL to the case of arbitrary number of agents.

Keywords: Fair division; Envy-freeness; Pareto optimality; AL method (search for similar items in EconPapers)
JEL-codes: C70 D61 D71 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s40505-015-0089-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:etbull:v:4:y:2016:i:2:d:10.1007_s40505-015-0089-1

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/40505

DOI: 10.1007/s40505-015-0089-1

Access Statistics for this article

Economic Theory Bulletin is currently edited by Nicholas C. Yannelis

More articles in Economic Theory Bulletin from Springer, Society for the Advancement of Economic Theory (SAET) Contact information at EDIRC.
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().