[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The Price of Fairness for Indivisible Goods

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and equitability. However, these notions cannot always be satisfied for indivisible goods, leading to certain instances being ignored in the analysis. In this paper, we focus instead on notions with guaranteed existence, including envy-freeness up to one good (EF1), balancedness, maximum Nash welfare (MNW), and leximin. We also introduce the concept of strong price of fairness, which captures the efficiency loss in the worst fair allocation as opposed to that in the best fair allocation as in the price of fairness. We mostly provide tight or asymptotically tight bounds on the worst-case efficiency loss for allocations satisfying these notions, for both the price of fairness and the strong price of fairness.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

Notes

  1. From the above example, one may think that such scenarios are rare exceptions. However, for envy-freeness, these scenarios are in fact common if the number of goods is not too large compared to the number of agents [19, 29].

  2. Indeed, the instance that Caragiannis et al. used to show that the price of proportionality is at least n − 1 + 1/n admits no envy-free allocation. Thus, it is still possible that the price of envy-freeness is lower than the price of proportionality for indivisible goods.

  3. See Section 2 for the formal definitions of these notions.

  4. See the example in Theorem 3.5.

  5. Moreover, a round-robin allocation is likely to be envy-free and proportional as long as the number of goods is sufficiently larger than the number of agents [28].

  6. In addition to these exceptions, MNW, MEW, and leximin allocations are hard to compute regardless of price of fairness considerations (see, e.g., [33], footnote 7).

  7. Interestingly, this stands in contrast to our result that the price of MNW for indivisible goods is Θ(n).

  8. See [17] for the definitions of MMS and PMMS.

  9. Recently, Chaudhury et al. [18] showed that the existence is also guaranteed for three agents.

  10. In case there are ties between goods, we may assume worst-case tie breaking, since it is possible to obtain an instance with infinitesimal difference in welfare and any desired tie-breaking between goods by slightly perturbing the utilities.

  11. In the case where the maximum Nash welfare is 0, an allocation is an MNW allocation if it gives positive utility to a set of agents of maximal size and moreover maximizes the product of utilities of the agents in that set.

  12. To see the first and third inequalities, one may prove by induction that in general, if we have \(\frac {a_{1}}{b_{1}}\geq \dots \geq \frac {a_{k}}{b_{k}}\), then \(\frac {a_{1}}{b_{1}}\geq \frac {a_{1}+\dots +a_{k}}{b_{1}+\dots +b_{k}}\geq \frac {a_{k}}{b_{k}}\). The case k = 2 holds because \(\frac {a_{1}}{b_{1}}\geq \frac {a_{1}+a_{2}}{b_{1}+b_{2}}\) is equivalent to \(\frac {a_{1}}{b_{1}}\geq \frac {a_{2}}{b_{2}}\), and similarly for \(\frac {a_{1}+a_{2}}{b_{1}+b_{2}}\geq \frac {a_{2}}{b_{2}}\).

References

  1. Amanatidis, G., Birmpas, G., Markakis, E.: Comparing approximate relaxations of envy-freeness. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pp 42–48 (2018)

  2. Amanatidis, G., Ntokos, A., Markakis, E.: Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theor. Comput. Sci. 841, 94–109 (2020)

    Article  MathSciNet  Google Scholar 

  3. Aumann, Y., Dombb, Y.: The efficiency of fair division with connected pieces. ACM Trans. Econ. Comput. 3(4), 23:1–23:16 (2015)

    Article  MathSciNet  Google Scholar 

  4. Bansal, N., Sviridenko, M.: The Santa Claus problem. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pp 31–40 (2006)

  5. Barman, S., Bhaskar, U., Shah, N.: Settling the price of fairness for indivisible goods. In: Proceedings of the 16th Conference on Web and Internet Economics (WINE), pp. 356–369 (2020)

  6. Barman, S., Krishnamurthy, S.K.: Approximation algorithms for maximin fair division. ACM Trans. Econ. Comput. 8(1), 5:1–5:28 (2020)

    Article  MathSciNet  Google Scholar 

  7. Bei, X., Lu, X., Manurangsi, P., Suksompong, W.: The price of fairness for indivisible goods. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp 81–87 (2019)

  8. Benabbou, N., Chakraborty, M., Igarashi, A., Zick, Y.: Finding fair and efficient allocations when valuations don’t add up. In: Proceedings of the 13th International Symposium on Algorithmic Game Theory, SAGT, pp 32–46 (2020)

  9. Bérczi, K., Bérczi-Kovács, E.R., Boros, E., Gedefa, F.T., Kamiyama, N., Kavitha, T., Kobayashi, Y., Makino, K.: Envy-free relaxations for goods, chores, and mixed items. arXiv:2006.04428 (2020)

  10. Bertsimas, D., Farias, V.F., Trichakis, N.: The price of fairness. Oper. Res. 59(1), 17–31 (2011)

    Article  MathSciNet  Google Scholar 

  11. Bezáková, I., Dani, V.: Allocating indivisible goods. ACM SIGecom. Exchanges. 5(3), 11–18 (2005)

    Article  Google Scholar 

  12. Bilò, V., Fanelli, A., Flammini, M., Monaco, G., Moscardelli, L.: The price of envy-freeness in machine scheduling. Theor. Comput. Sci. 613, 65–78 (2016)

    Article  MathSciNet  Google Scholar 

  13. Biswas, A., Barman, S.: Fair division under cardinality constraints. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pp 91–97 (2018)

  14. Bogomolnaia, A., Moulin, H.: Random matching under dichotomous preferences. Econometrica 72(1), 257–279 (2004)

    Article  MathSciNet  Google Scholar 

  15. Brams, S.J., Taylor, D.: Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, Cambridge (1996)

    Book  Google Scholar 

  16. Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. Theory. Comput. Syst. 50(4), 589–610 (2012)

    Article  MathSciNet  Google Scholar 

  17. 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)

    Article  MathSciNet  Google Scholar 

  18. Chaudhury, B.R., Garg, J., Mehlhorn, K.: EFX exists for three agents. In: Proceedings of the 21st ACM Conference on Economics and Computation (EC), pp 1–19 (2020)

  19. Dickerson, J.P., Goldman, J., Karp, J., Procaccia, A.D., Sandholm, T.: The computational rise and fall of fairness. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pp 1405–1411 (2014)

  20. Dubins, L.E., Spanier, E.H.: How to cut a cake fairly. Am. Math. Mon. 68(1), 1–17 (1961)

    Article  MathSciNet  Google Scholar 

  21. Ghodsi, M., HajiAghayi, M., Seddighin, M., Seddighin, S., Yami, H.: Fair allocation of indivisible goods Improvement and generalization. In: Proceedings of the 19th ACM Conference on Economics and Computation (EC), pp 539–556 (2018)

  22. Heydrich, S., van Stee, R.: Dividing connected chores fairly. Theor. Comput. Sci. 593, 51–61 (2015)

    Article  MathSciNet  Google Scholar 

  23. Kurokawa, D., Procaccia, A.D., Shah, N.: Leximin allocations in the real world. ACM Trans. Econ. Comput. 6(3–4), 11:1–11:24 (2018a)

    MathSciNet  Google Scholar 

  24. Kurokawa, D., Procaccia, A.D., Wang, J.: Fair enough: Guaranteeing approximate maximin shares. J. ACM 64(2), 8:1–8:27 (2018b)

    MathSciNet  MATH  Google Scholar 

  25. Kurz, S.: The price of fairness for a small number of indivisible items. In: Operations Research Proceedings, pp 335–340 (2014)

  26. Kyropoulou, M., Suksompong, W., Voudouris, A.A.: Almost envy-freeness in group resource allocation. Theor. Comput. Sci. 841, 110–123 (2020)

    Article  MathSciNet  Google Scholar 

  27. 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)

  28. Manurangsi, P., Suksompong, W.: Closing gaps in asymptotic fair division. arXiv:2004.05563 (2020a)

  29. Manurangsi, P., Suksompong, W.: When do envy-free allocations exist? SIAM J. Discret. Math. 34(3), 1505–1521 (2020b)

    Article  MathSciNet  Google Scholar 

  30. Markakis, E.: Approximation algorithms and hardness results for fair division. In: Ulle, E. (ed.) Trends in Computational Social Choice, chapter 12. AI Access, pp 231–247 (2017)

  31. Michorzewski, M., Peters, D., Skowron, P.: Price of fairness in budget division and probabilistic social choice. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp 2184–2191 (2020)

  32. Oh, H., Procaccia, A.D., Suksompong, W.: Fairly allocating many goods with few queries. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), pp 2141–2148 (2019)

  33. Plaut, B., Roughgarden, T.: Almost envy-freeness with general valuations. SIAM J. Discret. Math. 34(2), 1039–1068 (2020)

    Article  MathSciNet  Google Scholar 

  34. Segal-Halevi, E., Suksompong, W.: Democratic fair allocation of indivisible goods. Artif. Intell. 277, 103167 (2019)

    Article  MathSciNet  Google Scholar 

  35. Steinhaus, H.: The problem of fair division. Econometrica 16(1), 101–104 (1948)

    Google Scholar 

  36. Suksompong, W.: Approximate maximin shares for groups of agents. Math. Soc. Sci. 92, 40–47 (2018)

    Article  MathSciNet  Google Scholar 

  37. Suksompong, W.: Fairly allocating contiguous blocks of indivisible items. Discret. Appl. Math. 260, 227–236 (2019)

    Article  MathSciNet  Google Scholar 

  38. Suksompong, W.: On the number of almost envy-free allocations. Discret. Appl. Math. 284, 606–610 (2020)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

This work is partially supported by NSF Award CCF-1815434, by the European Research Council (ERC) under grant number 639945 (ACCORD), and by an NUS Start-up Grant. We are grateful to the reviewers of IJCAI 2019 and Theory of Computing Systems for many helpful comments, and to Ioannis Caragiannis for pointing us to the price of envy-freeness result by Bertsimas et al. [10].

Author information

Authors and Affiliations

  1. School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore

    Xiaohui Bei & Xinhang Lu

  2. Department of Electrical Engineering and Computer Sciences, UC Berkeley, California, Berkeley, USA

    Pasin Manurangsi

  3. School of Computing, National University of Singapore, Singapore, Singapore

    Warut Suksompong

Authors
  1. Xiaohui Bei
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xinhang Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pasin Manurangsi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Warut Suksompong
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Warut Suksompong.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of the paper appeared in Proceedings of the 28th International Joint Conference on Artificial Intelligence [7]. This version includes several proofs that were omitted or partially omitted in the preliminary version (Theorems 3.2, 3.3, 3.4, 3.8, 3.9, 4.1, 4.2, 5.2, 5.3, 5.4, 5.5, 6.1, 6.2, and 6.3). We also included additional discussion of our results and updated the state of related work. The third author is now at Google Research. Most of the work was done while the fourth author was at the University of Oxford.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bei, X., Lu, X., Manurangsi, P. et al. The Price of Fairness for Indivisible Goods. Theory Comput Syst 65, 1069–1093 (2021). https://doi.org/10.1007/s00224-021-10039-8

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-021-10039-8

Keywords

Search

Navigation