Abstract
How can one fairly assign a finite set of m indivisible items between n agents? This question has been extensively studied last few decades with a focus on structure of utility functions representing the agent’s preferences over subsets of items. This paper considers a scenario where all agents’ utility functions are lexicographic and subadditive. In this setting, each agent has a linear order over single items, and this order is then extended to a total order over all subsets of items using the lexicographic order. Every agent is equipped with a utility function consistent with her lexicographic preference, which is either additive or, more general, subadditive. Our task is to determine a fair allocation in the sense that the minimum utility over all agents or the product of individual utilities is maximized. As a result, we obtain 1/2-approximation algorithms for both problems with lexicographic subadditive functions. In addition, we show that the factor of 1/2 is tight for the former problem, but is not for the latter one.
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.
It is noticed that the \(\mathrm {NP}\)-hardness result obtained in [10] is for the NWP problem with an objective function maximizing the product of individual utilities, but the result also applies to the case considered in this paper, where the objective is the n-th root of the product, since the both objectives have always the same optimum. However, they are different in terms of approximation.
References
Aziz, H., Biró, P., Lang, J., Lesca, J., Monnot, J.: Optimal reallocation under additive and ordinal preferences. In: AAMAS, IFAAMAS 2016, pp. 402–410 (2016)
Barman, S., Krishnamurthy, S.K., Vaish, R.: Finding fair and efficient allocations. In: ACM EC, pp. 557–574 (2018)
Baumeister, D., Bouveret, S., Lang, J., Nguyen, N., Nguyen, T., Rothe, J., Saffidine, A.: Axiomatic and computational aspects of scoring allocation rules for indivisible goods. In: Procaccia, A., Walsh, T. (eds.) Proceedings of the 5th International Workshop on Computational Social Choice, Pittsburgh, USA. Carnegie Mellon University, June 2014
Baumeister, D., Bouveret, S., Lang, J., Nguyen, N., Nguyen, T.T., Rothe, J., Saffidine, A.: Positional scoring-based allocation of indivisible goods. Auton. Agents Multi-Agent Syst. 31(3), 628–655 (2017)
Bezáková, I., Dani, V.: Nobody left behind: fair allocation of indivisible goods. ACM SIGecom Exch. 5(3) (2005)
Bouveret, S., Chevaleyre, Y., Maudet, N.: Fair allocation of indivisible goods. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A. (eds.) Handbook of Computational Social Choice, Chap. 12. Cambridge University Press (2016)
Bouveret, S., Lang, J.: A general elicitation-free protocol for allocating indivisible goods. In: IJCAI, IJCAI/AAAI 2011, pp. 73–78 (2011)
Chevaleyre, Y., Dunne, P., Endriss, U., Lang, J., Lemaître, M., Maudet, N., Padget, J., Phelps, S., Rodríguez-Aguilar, J., Sousa, P.: Issues in multiagent resource allocation. Informatica 30, 3–31 (2006)
Cole, R., Gkatzelis, V.: Approximating the Nash social welfare with indivisible items. In: STOC, pp. 371–380. ACM (2015)
Darmann, A., Schauer, J.: Maximizing nash product social welfare in allocating indivisible goods. Eur. J. Oper. Res. 247(2), 548–559 (2015)
Khot, S., Ponnuswami, A.K.: Approximation algorithms for the max-min allocation problem. In: Approx-random. Lecture Notes in Computer Science, pp. 204–217 (2007)
Lang, J., Rothe, J.: Fair division of indivisible goods. In: Rothe, J. (ed.) Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, Chap. 8. Springer-Verlag (2016)
Lee, E.: APX-hardness of maximizing Nash social welfare with indivisible items. Inf. Process. Lett. 122, 17–20 (2017)
Moulin, H.: Fair Division and Collective Welfare. MIT Press (2004)
Nguyen, N., Baumeister, D., Rothe, J.: Strategy-proofness of scoring allocation correspondences for indivisible goods. In: IJCAI, pp. 1127–1133. AAAI Press (2015)
Nguyen, N., Nguyen, T.T., Rothe, J.: Approximate solutions to max-min fair and proportionally fair allocations of indivisible goods. In: AAMAS, IFAAMAS 2017, pp. 262–271 (2017)
Nguyen, T.T., Roos, M., Rothe, J.: A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation. Ann. Math. Artif. Intell. 68(1–3), 65–90 (2013)
Nguyen, T.T., Rothe, J.: Envy-ratio and average-Nash social welfare optimization in multiagent resource allocation. In: AAMAS, IFAAMAS, 2013, pp. 1139–1140 (2013)
Nguyen, T.T., Rothe, J.: Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods. Discr. Appl. Math. 179, 54–68 (2014)
Rothe, J.: Complexity Theory and Cryptology. An Introduction to Cryptocomplexity. EATCS Texts in Theoretical Computer Science. Springer-Verlag, Berlin (2005)
Vazirani, V.: Approximation Algorithms, Second edn. Springer-Verlag, Berlin (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Nguyen, T.T. (2020). How to Fairly Allocate Indivisible Resources Among Agents Having Lexicographic Subadditive Utilities. In: Satapathy, S., Bhateja, V., Nguyen, B., Nguyen, N., Le, DN. (eds) Frontiers in Intelligent Computing: Theory and Applications. Advances in Intelligent Systems and Computing, vol 1013. Springer, Singapore. https://doi.org/10.1007/978-981-32-9186-7_18
Download citation
DOI: https://doi.org/10.1007/978-981-32-9186-7_18
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-32-9185-0
Online ISBN: 978-981-32-9186-7
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)