Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm

Brams, Steven J. and Kilgour, D. Marc and Klamler, Christian (2013): Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm.

Abstract

Many 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.

• Item Type: MPRA Paper
• Language: English
• Keywords: Two-person fair division, indivisible items, envy-freeness, efficiency, algorithm
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C78 - Bargaining Theory ; Matching Theory; 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; D - Microeconomics > D7 - Analysis of Collective Decision-Making; D - Microeconomics > D7 - Analysis of Collective Decision-Making > D74 - Conflict ; Conflict Resolution ; Alliances ; Revolutions

References

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

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., 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., 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. Cambridge, NY: 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.

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

Kohler, David A., and R. Chandrasekaran (1971). “A Class of Sequential Games,” Operations Research 19, no. 2 (March/April): 270-277.

Levine, Lionel, and Katherine E. Stange (2012). “How to Make the Most of a Shared Meal: Plan the Last Bit First,” American Mathematical Monthly 119, no. 7 (August-September): 550-565.

Vetschera, Rudolf and D. Marc Kilgour (2013). “Strategic Behavior in Contested-Pile Methods for Fair Division of Indivisible Items,” Group Decision and Negotiation 22, no. 2: 299-319.

Vetschera, Rudolf and D. Marc Kilgour (2014). “Fair Division of Indivisible Items Between Two Players: Design Parameters for Contested-Pile Methods,” Theory and Decision (forthcoming).