The undercut procedure: an algorithm for the envy-free division of indivisible items

Brams, Steven J. and Kilgour, D. Marc and Klamler, Christian (2009): The undercut procedure: an algorithm for the envy-free division of indivisible items.

Abstract

We propose a procedure for dividing indivisible items between two players in which each player ranks the items from best to worst and has no information about the other player’s ranking. It ensures that each player receives a subset of items that it values more than the other player’s complementary subset, given that such an envy-free division is possible. We show that the possibility of one player’s undercutting the other’s proposal, and implementing the reduced subset for himself or herself, makes the proposer “reasonable” and generally leads to an envy-free division, even when the players rank items exactly the same. Although the undercut procedure is manipulable, each player’s maximin strategy is to be truthful. Applications of the undercut procedure are briefly discussed.

• Item Type: MPRA Paper
• Language: English
• Keywords: Fair division; allocation of indivisible items; envy-freeness; ultimatum game
• Subjects: 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; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games

References

Barberà, Salvador, Walter Bossert, and Prasanta Pattanaik (2004). “Ranking Sets of Objects.” In Salvador Barberà, Peter J. Hammond, and Christian Seidl (eds.), Handbook of Utility Theory, vol. 2. Boston: Kluwer Academic Publishers.

Brams, Steven J. (2008). Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures. Princeton, NJ: Princeton University Press.

Brams, Steven J. (2006). “Fair Division.” In Barry R. Weingast and Donald Wittman (eds.), Oxford Handbook of Political Economy. Oxford, UK: Oxford University Press, pp. 425-437.

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 Todd R. Kaplan (2004). “Dividing the Indivisible: Procedures for Allocating Cabinet Ministries in a Parliamentary System.” Journal of Theoretical Politics 16, no. 2 (April): 143-173.

Brams, Steven J., and D. Marc Kilgour (2001). “Competitive Fair Division.” Journal of Political Economy 109, no.2 (April): 418-443.

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.

Brams, Steven J., and Philip D. Straffin, Jr. (1979). “Prisoners’ Dilemma and Professional Sports Drafts.” American Mathematical Monthly 86, no. 2 (February): 80-88.

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.

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.

Foley, Duncan K. (1967). “Resource Allocation and the Public Sector.” Yale Economic Essays 7, no. 1 (Spring): 45-98.

Hasse diagram (Wikipedia, 2008). http://en.wikipedia.org/wiki/Hasse_diagram

Herreiner, Dorothea, and Clemens Puppe (2002). “A Simple Procedure for Finding Equitable Allocations of Indivisible Items.” Social Choice and Welfare 19, no. 2 (April): 415-430.

Raiffa, Howard (1982). The Art and Science of Negotiation. Cambridge, MA: Harvard University Press.

Taylor, Alan D., and William S. Zwicker (1999). Simple Games: Desirability Relations, Trading, Pseudoweightings. Princeton, NJ: Princeton University Press.