Two-Person Fair Division of Indivisible Items: Compatible and Incompatible Properties

Brams, Steven J. and Kilgour, Marc and Klamler, Christian (2021): Two-Person Fair Division of Indivisible Items: Compatible and Incompatible Properties.

Abstract

Suppose two players wish to divide a finite set of indivisible items, over which each distributes a specified number of points. Assuming the utility of a player’s bundle is the sum of the points it assigns to the items it contains, we analyze what divisions are fair. We show that if there is an envy-free (EF) allocation of the items, two other desirable properties—Pareto-optimality (PO) and maximinality (MM)—can also be satisfied, rendering these three properties compatible, but other properties—balance (BL), maximum Nash welfare (MNW), maximum total welfare (MTW), and lexicographic optimality (LO)—may fail. If there is no EF division, as is likely, it is always possible to satisfy EFx, a weaker form of EF, but an EFx allocation may not be PO, BL, MNW, MTW, or LO. Moreover, if one player considers an item worthless (i.e., assigns zero points to it), an EFx division may be Pareto dominated by a nonEFx allocation that is MNW. Although these incompatibilities suggest that there is no “perfect” 2-person fair division of indivisible items, EFx and MNW divisions—if they give different allocations when there is no EF-PO-MM division—seem the most compelling alternatives, with EFx, we conjecture, satisfying the Rawlsian objective of helping the worse-off player and MNW, a modification of MTW, suggesting a more Benthamite view.

• Item Type: MPRA Paper
• Language: English
• Keywords: Two-person fair division; indivisible items; envy-freeness
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games; D - Microeconomics > D6 - Welfare Economics; 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

References

Amanatidis, Goergios, Georgios Birmpas, Aris Folos-Ratsikas, Alexandros Hollender, and Alexandros A. Voudouris (2021). “Maximum Nash Welfare and Other Stories about EFX,” Theoretical Computer Science, 863 (April): 69-85.

Bentham, Jeremy (1789/2017). An Introduction to the Principles of Morals and Legislation. London: UCL Bentham Project.

Berger, Ben, Avi Cohen, Michal Feldman, and Amos Fiat (2021). “(Almost Full) EFx Exists for Four Agents (and Beyond).” Preprint, arXiv2102.10654.

Brams, Steven J., D. Marc Kilgour, and Christian Klamler (2015). “How to Divide Things Fairly.” Mathematics Magazine 88, no. 5 (December): 338-348.

Brams, Steven J., and Alan D. Taylor (1994). 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.

Caragiannis, Ioannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang (2019). “The Unreasonable Fairness of Maximum Nash Welfare.” In ACM Transactions on Economics and Computation 7, no. 3 (September): 305-322.

Klamler, Christian (2021). “The Notion of Fair Division in Negotiations.” In D. Marc Kilgour and Colin Eden (eds), Handbook of Group Decision and Negotiation, 2nd ed. New York: Springer, pp. 81-109.

Rawls, John (1971/1999). A Theory of Justice. Cambridge, MA: Belknap/Harvard University Press.