Abstract
Fair division has emerged as a very hot topic in EconCS research, and envy-freeness is among the most compelling fairness concepts. An allocation of indivisible items to agents is envy-free if no agent prefers the bundle of any other agent to his own in terms of value. As envy-freeness is rarely a feasible goal, there is a recent focus on relaxations of its definition. An approach in this direction is to complement allocations with payments (or subsidies) to the agents. A feasible goal then is to achieve envy-freeness in terms of the total value an agent gets from the allocation and the subsidies.
We consider the natural optimization problem of computing allocations that are envy-freeable using the minimum amount of subsidies. As the problem is NP-hard, we focus on the design of approximation algorithms. On the positive side, we present an algorithm which, for a constant number of agents, approximates the minimum amount of subsidies within any required accuracy, at the expense of a graceful increase in the running time. On the negative side, we show that, for a superconstant number of agents, the problem of minimizing subsidies for envy-freeness is not only hard to compute exactly (as a folklore argument shows) but also, more importantly, hard to approximate.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Notice that deciding whether an envy-free allocation exists for two agents with identical item valuations requires solving Partition, a well-known NP-hard problem [16].
- 2.
In our exposition, we assume that valuations are non-negative, even though our positive result can be extended to work without this assumption, in the model of [5] where items can be goods or chores.
- 3.
This statement is actually weaker than the one proved in [14]. However, it suffices for our purpose to prove hardness of approximation. Note that we have made no particular attempt to optimize our inapproximability threshold.
References
Alkan, A., Demange, G., Gale, D.: Fair allocation of indivisible goods and criteria of justice. Econometrica 59(4), 1023–1039 (1991)
Amanatidis, G., Markakis, E., Ntokos, A.: Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination. Theoret. Comput. Sci. 841, 94–109 (2020)
Aragones, E.: A derivation of the money Rawlsian solution. Soc. Choice Welf. 12(3), 267–276 (1995). https://doi.org/10.1007/BF00179981
Aziz, H., Bouveret, S., Caragiannis, I., Giagkousi, I., Lang, J.: Knowledge, fairness, and social constraints. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pp. 4638–4645 (2018)
Aziz, H., Caragiannis, I., Igarashi, A., Walsh, T.: Fair allocation of indivisible goods and chores. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp. 53–59 (2019)
Barman, S., Krishnamurthy, S.K., Vaish, R.: Finding fair and efficient allocations. In: Proceedings of the 19th ACM Conference on Economics and Computation (EC), pp. 557–574 (2018)
Brustle, J., Dippel, J., Narayan, V.V., Suzuki, M., Vetta, A.: One dollar each eliminates envy. In: Proceedings of the 21st ACM Conference on Economics and Computation (EC), pp. 23–39 (2020)
Budish, E.: The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. J. Polit. Econ. 119(6), 1061–1103 (2011)
Caragiannis, I., Gravin, N., Huang, X.: Envy-freeness up to any item with high Nash welfare: the virtue of donating items. In: Proceedings of the 20th ACM Conference on Economics and Computation (EC), pp. 527–545 (2019)
Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., Wang, J.: The unreasonable fairness of maximum nash welfare. ACM Trans. Econ. Comput. 7(3), 12:1–12:32 (2019)
Chaudhury, B.R., Kavitha, T., Mehlhorn, K., Sgouritsa, A.: A little charity guarantees almost envy-freeness. SIAM J. Comput. 50(4), 1336–1358 (2021)
Chevaleyre, Y., Endriss, U., Estivie, S., Maudet, N.: Reaching envy-free states in distributed negotiation settings. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), pp. 1239–1244 (2007)
Chevaleyre, Y., Endriss, U., Maudet, N.: Distributed fair allocation of indivisible goods. Artif. Intell. 242, 1–22 (2017)
Chlebík, M., Chlebíková, J.: Complexity of approximating bounded variants of optimization problems. Theoret. Comput. Sci. 354(3), 320–338 (2006)
Foley, D.K.: Resource allocation and the public sector. Yale Econ. Essays 7(1), 45–98 (1967)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Haake, C.J., Raith, M.G., Su, F.E.: Bidding for envy-freeness: a procedural approach to n-player fair-division problems. Soc. Choice Welf. 19(4), 723–749 (2002)
Halpern, D., Shah, N.: Fair division with subsidy. In: Fotakis, D., Markakis, E. (eds.) SAGT 2019. LNCS, vol. 11801, pp. 374–389. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30473-7_25
Kann, V.: Maximum bounded 3-dimensional matching is MAXSNP-complete. Inf. Process. Lett. 37(1), 27–35 (1991)
Klijn, F.: An algorithm for envy-free allocations in an economy with indivisible objects and money. Soc. Choice Welf. 17(2), 201–215 (2000)
Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: On approximately fair allocations of indivisible goods. In: Proceedings of the 5th ACM Conference on Electronic Commerce (EC), pp. 125–131 (2004)
Maskin, E.: On the fair allocation of indivisible goods. In: Arrow and the Foundations of the Theory of Economic Policy (Essays in Honor of Kenneth Arrow), pp. 341–349. MacMillan (1987). https://doi.org/10.1007/978-1-349-07357-3_12
Meertens, M., Potters, J., Reijnierse, H.: Envy-free and pareto efficient allocations in economies with indivisible goods and money. Math. Soc. Sci. 44(3), 223–233 (2002)
Myerson, R.B.: Optimal auction design. Math. Oper. Res. 6(1), 58–73 (1981)
Plaut, B., Roughgarden, T.: Almost envy-freeness with general valuations. SIAM J. Discret. Math. 34(2), 1039–1068 (2020)
Procaccia, A.D.: An answer to fair division’s most enigmatic question: technical perspective. Commun. ACM 63(4), 118 (2020)
Su, F.E.: Rental harmony: Sperner’s lemma in fair division. Am. Math. Mon. 106(10), 930–942 (1999)
Svensson, L.G.: Large indivisibles: an analysis with respect to price equilibrium and fairness. Econometrica 51(4), 939–954 (1983)
Varian, H.R.: Equity, envy, and efficiency. J. Econ. Theory 9(1), 63–91 (1974)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001). https://doi.org/10.1007/978-3-662-04565-7
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this paper
Cite this paper
Caragiannis, I., Ioannidis, S.D. (2022). Computing Envy-Freeable Allocations with Limited Subsidies. In: Feldman, M., Fu, H., Talgam-Cohen, I. (eds) Web and Internet Economics. WINE 2021. Lecture Notes in Computer Science(), vol 13112. Springer, Cham. https://doi.org/10.1007/978-3-030-94676-0_29
Download citation
DOI: https://doi.org/10.1007/978-3-030-94676-0_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-94675-3
Online ISBN: 978-3-030-94676-0
eBook Packages: Computer ScienceComputer Science (R0)