Proceedings

Uniform Welfare Guarantees Under Identical Subadditive Valuations

Video Download BibTeX Cite

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. Main track. Pages 46-52.

https://doi.org/10.24963/ijcai.2020/7

© 2020 International Joint Conferences on Artificial Intelligence

Abstract

We study the problem of allocating indivisible goods among agents that have an identical subadditive valuation over the goods. The extent of fair- ness and efficiency of allocations is measured by the generalized means of the values that the alloca- tions generate among the agents. Parameterized by an exponent term p, generalized-mean welfares en- compass multiple well-studied objectives, such as social welfare, Nash social welfare, and egalitarian welfare. We establish that, under identical subadditive valu- ations and in the demand oracle model, one can efficiently find a single allocation that approximates the optimal generalized-mean welfare—to within a factor of 40—uniformly for all p ∈ (−∞,1]. Hence, by way of a constant-factor approximation algorithm, we obtain novel results for maximizing Nash social welfare and egalitarian welfare for identical subadditive valuations.

  1. [Annamalai et al., 2017] Chidambaram Annamalai, Christos Kalaitzis, and Ola Svensson. Combinatorial algorithm for restricted max-min fair allocation. ACM Transactions on Algorithms (TALG), 13(3):1-28, 2017.
  2. [Barman et al., 2018a] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding fair and efficient allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 557-574. ACM, 2018.
  3. [Barman et al., 2018b] Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Greedy algorithms for maximizing nash social welfare. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 7-13. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
  4. [Bei et al., 2019] Xiaohui Bei, Xinhang Lu, Pasin Manu- rangsi, and Warut Suksompong. The price of fairness for indivisible goods. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 81-87. AAAI Press, 2019. IJCAI
  5. [Bertsimas et al., 2011] Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. The price of fairness. Operations research, 59(1):17-31, 2011.
  6. [Brandt et al., 2016] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. Handbook of computational social choice. Cambridge University Press, 2016.
  7. [Chakrabarty et al., 2009] Deeparnab Chakrabarty, Julia Chuzhoy, and Sanjeev Khanna. On allocating goods to maximize fairness. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 107-116. IEEE, 2009.
  8. [Cole and Gkatzelis, 2018] Richard Cole and Vasilis Gkatzelis. Approximating the nash social welfare with indivisible items. SIAM Journal on Computing, 47(3):1211-1236, 2018.
  9. [Dobzinski et al., 2005] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 610-618. ACM, 2005.
  10. [Dobzinski et al., 2010] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. Math. Oper. Res., 35(1):1-13, 2010.
  11. [Endriss, 2017] Ulle Endriss. Trends in Computational So- cial Choice. Lulu. com, 2017.
  12. [Feige, 2009] Uriel Feige. On maximizing welfare when utility functions are subadditive. SIAM Journal on Com- puting, 39(1):122-142, 2009.
  13. [Garg et al., 2020] Jugal Garg, Pooja Kulkarni, and Rucha Kulkarni. Approximating nash social welfare under sub- modular valuations through (un) matchings. In Proceed- ings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2673-2687. SIAM, 2020.
  14. [Goemans et al., 2009] Michel X Goemans, Nicholas JA Harvey, Satoru Iwata, and Vahab Mirrokni. Approximat- ing submodular functions everywhere. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 535-544. Society for Industrial and Ap- plied Mathematics, 2009.
  15. [Goldman and Procaccia, 2015] Jonathan Goldman and Ariel D Procaccia. Spliddit: Unleashing fair division algorithms. ACM SIGecom Exchanges, 13(2):41-46, 2015.
  16. [Khot et al., 2008] Subhash Khot, Richard J Lipton, Evan- gelos Markakis, and Aranyak Mehta. Inapproximability results for combinatorial auctions with submodular utility functions. Algorithmica, 52(1):3-18, 2008.
  17. [Moulin, 2004] Hervé Moulin. Fair division and collective welfare. MIT press, 2004.
  18. [Nguyen and Rothe, 2014] Trung Thanh Nguyen and Jörg Rothe. Minimizing envy and maximizing average nash so- cial welfare in the allocation of indivisible goods. Discrete Applied Mathematics, 179:54-68, 2014.
  19. [Nisan et al., 2007] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani. Algorithmic game theory. Cambridge university press, 2007.
  20. [Vondrák, 2008] Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 67-74. ACM, 2008.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards