Almost envy-freeness with general valuations. (English) Zbl 1437.91237
Summary: The goal of fair division is to distribute resources among competing players in a “fair” way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular fair division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the fair division of indivisible goods with different classes of player valuations.
MSC:
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
References:
| [1] | H. Aziz, S. Gaspers, S. Mackenzie, and T. Walsh, Fair assignment of indivisible objects under ordinal preferences, Artificial Intelligence, 227(C) (2015), pp. 71-92. · Zbl 1346.68106 |
| [2] | A. Bogomolnaia and H. Moulin, Random matching under dichotomous preferences, Econometrica, 72 (2004), pp. 257-279. · Zbl 1142.91691 |
| [3] | S. Bouveret and J. Lang, Efficiency and envy-freeness in fair division of indivisible goods: Logical representation and complexity, J. Artificial Intelligence Res., 32 (2008), pp. 525-564. · Zbl 1183.68570 |
| [4] | S. J. Brams, D. M. Kilgour, and C. Klamler, Maximin envy-free division of indivisible items, Group Decision Negotiation, 26 (2017), pp. 115-131. |
| [5] | S. J. Brams and A. D. Taylor, Fair Division: From Cake-Cutting to Dispute Resolution, Cambridge University Press, Cambridge, UK, 1996. · Zbl 0991.91019 |
| [6] | F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, Handbook of Computational Social Choice, Cambridge University Press, Cambridge, UK, 2016. · Zbl 1436.91001 |
| [7] | E. Budish, The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes, J. Political Econ., 119 (2011), pp. 1061-1103. |
| [8] | E. Budish, G. P. Cachon, J. B. Kessler, and A. Othman, Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation, Oper. Res., 65 (2016), pp. 314-336. · Zbl 1366.91099 |
| [9] | E. Budish, Y.-K. Che, F. Kojima, and P. Milgrom, Designing random allocation mechanisms: Theory and applications, Amer. Econom. Rev., 103 (2013), pp. 585-623. |
| [10] | I. Caragiannis, N. Gravin, and X. Huang, Envy-freeness up to any item with high Nash welfare: The virtue of donating items, in Proceedings of the 2019 ACM Conference on Economics and Computation, ACM, New York, 2019, pp. 527-545. |
| [11] | I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang, The unreasonable fairness of maximum Nash welfare, in Proceedings of the 2016 ACM Conference on Economics and Computation, 2016, pp. 305-322. |
| [12] | H. Chan, J. Chen, B. Li, and X. Wu, Maximin-aware allocations of indivisible goods, in Proceedings of the 18th International Conference on Autonomous Agents and Multi Agent Systems, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2019, pp. 1871-1873. |
| [13] | B. R. Chaudhury, T. Kavitha, K. Mehlhorn, and A. Sgouritsa, A little charity guarantees almost envy-freeness, in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2020, pp. 2658-2672. · Zbl 1529.91049 |
| [14] | G. de Clippel, H. Moulin, and N. Tideman, Impartial division of a dollar, J. Economic Theory, 139 (2008) pp. 176-191. · Zbl 1132.91509 |
| [15] | J. P. Dickerson, J. Goldman, J. Karp, A. D. Procaccia, and T. Sandholm, The computational rise and fall of fairness, in Proceedings of the 28th AAAI Conference on Artificial Intelligence, 2014, pp. 1405-1411. |
| [16] | H. Dinh and A. Russell, Quantum and randomized lower bounds for local search on vertex-transitive graphs, Quantum Inf. Comput., 10 (2010), pp. 636-652. · Zbl 1234.81054 |
| [17] | S. Dobzinski, H. Fu, and R. Kleinberg, On the complexity of computing an equilibrium in combinatorial auctions, in Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 2015, pp. 110-122. · Zbl 1372.91047 |
| [18] | S. Dobzinski and J. Vondrák, Communication complexity of combinatorial auctions with submodular valuations, in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 2013, pp. 1205-1215. · Zbl 1421.68213 |
| [19] | Y. Gal, M. Mash, A. D. Procaccia, and Y. Zick, Which is the fairest (rent division) of them all?, in Proceedings of the 2016 ACM Conference on Economics and Computation, 2016, pp. 67-84. · Zbl 1427.91144 |
| [20] | J. Goldman and A. D. Procaccia, Spliddit: Unleashing fair division algorithms, SIGecom Exch., 13 (2015), pp. 41-46. |
| [21] | M. Kaneko and K. Nakamura, The Nash social welfare function, Econometrica, 47 (1979), pp. 423-35. · Zbl 0431.90091 |
| [22] | B. Lehmann, D. Lehmann, and N. Nisan, Combinatorial auctions with decreasing marginal utilities, in Proceedings of the 3rd ACM Conference on Electronic Commerce, ACM, New York, 2001, pp. 18-28. · Zbl 1125.91043 |
| [23] | R. Lipton, E. Markakis, E. Mossel, and A. Saberi, On approximately fair allocations of indivisible goods, in Proceedings of the 5th ACM Conference on Electronic Commerce, 2004, pp. 125-131. |
| [24] | D. C. Llewellyn, C. Tovey, and M. Trick, Local optimization on graphs, Discrete Appl. Math., 23 (1989), pp. 157-178. · Zbl 0675.90085 |
| [25] | M. Matsumoto and N. Tokushige, The exact bound in the Erdös-Ko-Rado theorem for cross-intersecting families, J. Combin. Theory Seri. A, 52 (1989), pp. 90-97. · Zbl 0734.05085 |
| [26] | H. Moulin, Fair Division and Collective Welfare, MIT Press, Cambridge, MA, 2003. |
| [27] | J. Nash, The Bargaining Problem, Econometrica, 18 (1950), pp. 155-162. · Zbl 1202.91122 |
| [28] | H. Oh, A. D. Procaccia, and W. Suksompong, Fairly allocating many goods with few queries, in Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019, pp. 2141-2148. · Zbl 1466.91143 |
| [29] | E. A. Pazner and D. Schmeidler, Egalitarian equivalent allocations: A new concept of economic equity, Quart. J. Economi., 92 (1978), pp. 671-687. |
| [30] | B. Plaut and T. Roughgarden, Communication complexity of discrete fair division, In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019. · Zbl 1435.91109 |
| [31] | S. Ramezani and U. Endriss, Nash social welfare in multiagent resource allocation, in Proceedings of the 12th Annual Conference on Agent-Mediated Electronic Commerce, 2010. |
| [32] | J. Rawls, A Theory of Justice, Belknap Press, Cambridge, MA, 1971. |
| [33] | A. Sen, Welfare inequalities and Rawlsian axiomatics, Theory Decision, 7 (1976), pp. 243-262. · Zbl 0364.90015 |
| [34] | A. Sen, Social choice theory: A re-examination, Econometrica, 45 (1977), pp. 53-89. · Zbl 0353.90001 |
| [35] | M. Valencia-Pabon and J.-C. Vera, On the diameter of Kneser graphs, Discrete Math., 305 (2005), pp. 383-385. · Zbl 1100.05030 |
| [36] | S. Zheng, The Vertex Isoperimetric Problem on Kneser Graphs, Research project, Massachusetts Institute of Technology, Cambridge, 2015. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
