Two-Person Fair Division of Indivisible Items when Envy-Freeness Is Impossible

Brams, Steven J. and Kilgour, D. Marc and Klamler, Christian (2021): Two-Person Fair Division of Indivisible Items when Envy-Freeness Is Impossible.

Abstract

Assume two players, A and B, must divide a set of indivisible items that each strictly ranks from best to worst. If the number of items is even, assume that the players desire that the allocations be balanced (each player gets half the items), item-wise envy-free (EF), and Pareto-optimal (PO).

Meeting this ideal is frequently impossible. If so, we find a balanced maximal partial allocation of items to the players that is EF, though it may not be PO. Then we show how to augment it in a way that makes it a complete allocation that is EF for one player (say, A) and almost-EF for the other player (B) in the sense that it is EF for B except for one item – it would be EF for B if a specific item assigned to A were removed. Moreover, we show how low-ranked that exceptional item can be for B, thereby finding an almost-EF allocation that is as close as possible to EF – as well as complete, balanced, and PO. We provide algorithms to find such almost-EF allocations, adapted from algorithms that apply when complete balanced EF-PO allocations are possible.

• Item Type: MPRA Paper
• Language: English
• Keywords: 2-person fair division, indivisible items, envy-freeness up to one item, Pareto-optimality
• Subjects: C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61 - Optimization Techniques ; Programming Models ; Dynamic Analysis; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games; D - Microeconomics > D6 - Welfare Economics > D63 - Equity, Justice, Inequality, and Other Normative Criteria and Measurement

References

Barberà, S., Bossert, W., and P.K. Pattanaik (2004). “Ranking Sets of Objects.” In Barberà, S., Hammond, P.J., and C. Seidl (eds). Handbook of Utility Theory. Springer, Boston, MA.

Bilò, V., Caragiannis, I., Flammini, M., Igarashi, A., Monaco, G., Peters, D., Vinci, C. and W.S. Zwicker (2018). “Almost Envy-Free Allocations with Connected Bundles.” arXiv:1808.09406.

Bouveret, S., Chevaleyre, Y., and N. Maudet (2016). ``Fair Allocation of Indivisible Goods.’’ In Brandt, F., Conitzer, V., Endriss, U., Lang, J., and A.D. Procaccia (eds). Handbook of Computational Social Choice, Cambridge University Press, New York: 284-310.

Brams, S. J., and Fishburn, P. (2000). “Fair division of indivisible items between two people with identical preferences: Envy-freeness, Pareto-optimality, and equity.” Social Choice and Welfare 17, 247-267.

Brams, S. J., Kilgour, D.M., and C. 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, S. J., Kilgour, D.M., and C. 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, S. J., Kilgour, D.M., and C. Klamler (2015). “How to Divide Things Fairly.” Mathematics Magazine 88, no. 5 (December): 338-348.

Brams, S. J., Kilgour, D.M., and C. Klamler (2017). “Maximin Envy-Free Division of Indivisible Items.” Group Decision and Negotiation 46, no. 1 (January): 115-131.

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

Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., and J. Wang (2019). “The Unreasonable Fairness of Maximum Nash Welfare.” ACM Transactions on Economics and Computation 7, no. 3, https://doi.org/10.1145/3355902.

Chung, K.L., and W. Feller (1949). “On Fluctuations in Coin-Tossing.” Proceedings of the National Academy of Sciences of the USA 35, no. 10 (October): 605-608.

Kilgour, D.M., and R. Vetschera (2018). “Two-Player Fair Division of Indivisible Items: Comparison of Algorithms.” European Journal of Operational Research 271, no. 2: 620-631.

Klamler, C. (2020). “The Notion of Fair Division in Negotiations.” In D.M. Kilgour and C. Eden (eds). Handbook of Group Decision and Negotiation, 2nd ed., https://doi.org/10.1007/978-3-030-12051-1_12-1. Plaut, B., and T. Roughgarden (2020). “Almost Envy-Freeness with General Valuations.” SIAM Journal on Discrete Mathematics 34, no. 2: 1039-1068.