Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm
AbstractMany procedures have been suggested for the venerable problem of dividing a set of indivisible items between two players. We propose a new algorithm (AL), related to one proposed by Brams and Taylor (BT), which requires only that the players strictly rank items from best to worst. Unlike BT, in which any item named by both players in the same round goes into a “contested pile,” AL may reduce, or even eliminate, the contested pile, allocating additional or more preferred items to the players. The allocation(s) that AL yields are Pareto-optimal, envy-free, and maximal; as the number of items (assumed even) increases, the probability that AL allocates all the items appears to approach infinity if all possible rankings are equiprobable. Although AL is potentially manipulable, strategizing under it would be difficult in practice.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by University Library of Munich, Germany in its series MPRA Paper with number 47400.
Date of creation: Jun 2013
Date of revision:
Two-person fair division; indivisible items; envy-freeness; efficiency; algorithm;
Find related papers by JEL classification:
- C7 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory
- C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
- D6 - Microeconomics - - Welfare Economics
- D61 - Microeconomics - - Welfare Economics - - - Allocative Efficiency; Cost-Benefit Analysis
- D63 - Microeconomics - - Welfare Economics - - - Equity, Justice, Inequality, and Other Normative Criteria and Measurement
- D7 - Microeconomics - - Analysis of Collective Decision-Making
- D74 - Microeconomics - - Analysis of Collective Decision-Making - - - Conflict; Conflict Resolution; Alliances
This paper has been announced in the following NEP Reports:
- NEP-ALL-2013-06-24 (All new papers)
- NEP-GTH-2013-06-24 (Game Theory)
- NEP-HPE-2013-06-24 (History & Philosophy of Economics)
- NEP-MIC-2013-06-24 (Microeconomics)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Brams,S.L. & Kaplan,T.R., 2002.
"Dividing the indivisible : procedures for allocating cabinet ministries to political parties in a parliamentary system,"
340, Bielefeld University, Center for Mathematical Economics.
- Steven J. Brams & Todd R. Kaplan, 2002. "Dividing the Indivisible: Procedures for Allocating Cabinet Ministries to Political Parties in a Parliamentary System," Discussion Papers 0202, Exeter University, Department of Economics.
- Brams, Steven J. & Kilgour, D. Marc & Klamler, Christian, 2009.
"The undercut procedure: an algorithm for the envy-free division of indivisible items,"
12774, University Library of Munich, Germany.
- Steven Brams & D. Kilgour & Christian Klamler, 2012. "The undercut procedure: an algorithm for the envy-free division of indivisible items," Social Choice and Welfare, Springer, vol. 39(2), pages 615-631, July.
- Dorothea Herreiner & Clemens Puppe, 2002. "A simple procedure for finding equitable allocations of indivisible goods," Social Choice and Welfare, Springer, vol. 19(2), pages 415-430, April.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Ekkehart Schlicht).
If references are entirely missing, you can add them using this form.