An algorithm for the proportional division of indivisible items

Brams, Steven J. and Kilgour, D. Marc and Klamler, Christian (2014): An algorithm for the proportional division of indivisible items.

Abstract

An allocation of indivisible items among n ≥ 2 players is proportional if and only if each player receives a proportional subset—one that it thinks is worth at least 1/n of the total value of all the items. We show that a proportional allocation exists if and only if there is an allocation in which each player receives one of its minimal bundles, from which the subtraction of any item would make the bundle worth less than 1/n.

We give a practicable algorithm, based on players’ rankings of minimal bundles, that finds a proportional allocation if one exists; if not, it gives as many players as possible minimal bundles. The resulting allocation is maximin, but it may be neither envy-free nor Pareto-optimal. However, there always exists a Pareto-optimal maximin allocation which, when n = 2, is also envy-free. We compare our algorithm with two other 2-person algorithms, and we discuss its applicability to real-world disputes among two or more players.

• Item Type: MPRA Paper
• Language: English
• Keywords: Fair division; indivisible items; proportionality; envy-freeness
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C78 - Bargaining Theory ; Matching Theory; D - Microeconomics > D6 - Welfare Economics > D61 - Allocative Efficiency ; Cost-Benefit Analysis; D - Microeconomics > D6 - Welfare Economics > D63 - Equity, Justice, Inequality, and Other Normative Criteria and Measurement; D - Microeconomics > D7 - Analysis of Collective Decision-Making > D74 - Conflict ; Conflict Resolution ; Alliances ; Revolutions; D - Microeconomics > D7 - Analysis of Collective Decision-Making > D78 - Positive Analysis of Policy Formulation and Implementation

References

Aziz, Haris, Serge Gaspers, Simon Mackenzie, and Toby Walsh, “Fair Assignment of Indivisible Objects under Ordinal Preferences.” Preprint, University of New South Wales, Australia. http://www.cse.unsw.edu.au/~sergeg/papers/AzizGMW14aamas.pdf

Bouveret, Sylvain, Ulle Endriss, and Jérôme Lang, “Fair Division under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods,” Proceedings of the 2010 Conference on ECAA 2010: 19th European Conference on Artificial Intelligence, vol. 215. Amsterdam: IOS Press, pp. 387-392.

Brams, Steven J., Paul H. Edelman, and Peter C. Fishburn (2001). “Paradoxes of Fair Division,” Journal of Philosophy 98, no. 6 (June): 300-314.

Brams, Steven J., Paul H. Edelman, and Peter C. Fishburn (2003). “Fair Division of Indivisible Goods,” Theory and Decision 55, no. 2 (September): 147-180.

Brams, Steven J., and Peter C. Fishburn (2000). ‘Fair Division of Indivisible Items between Two People with Identical Preferences: Envy-Freeness, Pareto- Optimality, and Equity,” Social Choice and Welfare 17, no. 2 (February): 247-267.

Brams, Steven J., and D. Marc Kilgour (2001). “Fallback Bargaining,” Group Decision and Negotiation 10, no. 4 (July): 287-316.

Brams, Steven J., D. Marc Kilgour, and Christian Klamler (2012). “The Undercut Procedure: An Algorithm for the Envy-Free Division of Indivisible Items,” Social Choice and Welfare 39, no. 2-3 (July): 615-631.

Brams, Steven J., D. Marc Kilgour, and Christian Klamler (2014). “Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm,” Notices of the AMS 61, no. 2 (February): 130-141.

Brams, Steven J., and Alan D. Taylor (1996). Fair Division: From Cake-Cutting to Dispute Resolution. New York: Cambridge University Press.

Brams, Steven J., and Alan D. Taylor (1999). The Win-Win Solution: Guaranteeing Fair Shares to Everybody. New York: W. W. Norton.

Brams, Steven J., and Daniel L. King (2005). “Efficient Fair Division: Help the Worst Off or Avoid Envy,” Rationality and Society 17, no. 4 (November): 387-421.

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

Edelman, Paul H., and Peter C. Fishburn (2001). “Fair Division of Indivisible Items among People with Similar Preferences,” Mathematical Social Sciences 41, no. 3 (May): 327-347.

Procaccia, Ariel D., and Junxing Wang (2014). “Fair Enough: Guaranteeing Approximate Maximin Shares.” Preprint, Computer Science Department, Carnegie Mellon University. http://www.cs.cmu.edu/~arielpro/papers/mms.pdf

Ramaekers, Eve (2013). “Fair Allocation of Indivisible Goods: The Two-Agent Case,” Social Choice and Welfare 41, no. 2 (July): 359-380.

Rawls, John (1971). A Theory of Fairness. Cambridge, MA: Harvard University Press.