Maximin Envy-Free Division of Indivisible Items

Brams, Steven and Kilgour, Marc and Klamler, Christian (2015): Maximin Envy-Free Division of Indivisible Items.

Abstract

Assume that two players have strict rankings over an even number of indivisible items. We propose algorithms to find allocations of these items that are maximin—maximize the minimum rank of the items that the players receive—and are envy-free and Pareto-optimal if such allocations exist. We show that neither maximin nor envy-free allocations may satisfy other criteria of fairness, such as Borda maximinality. Although not strategy-proof, the algorithms would be difficult to manipulate unless a player has complete information about its opponent’s ranking. We assess the applicability of the algorithms to real-world problems, such as allocating marital property in a divorce or assigning people to committees or projects.

• Item Type: MPRA Paper
• Language: English
• Keywords: Fair division; indivisible items; maximin; envy-free
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory; D - Microeconomics > D6 - Welfare Economics > D63 - Equity, Justice, Inequality, and Other Normative Criteria and Measurement; D - Microeconomics > D7 - Analysis of Collective Decision-Making

References

Aziz, Haris, Serge Gaspers, Simon Mackenzie, and Toby Walsh (2013). “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 (2010). “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., 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., D. Marc Kilgour, and Christian Klamler (2015). “A Better Way to Divide Things.” Preprint.

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 Draft,” American Mathematical Monthly 86, no. 2 (February): 80-88.

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

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

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