Proceedings

Budget-feasible Maximum Nash Social Welfare is Almost Envy-free

Xiaowei Wu, Bo Li, Jiarui Gan

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 465-471.

https://doi.org/10.24963/ijcai.2021/65

Keywords

  • AI Ethics, Trust, Fairness: Fairness
  • Agent-based and Multi-agent Systems: Computational Social Choice
  • Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems

Abstract

The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget-feasible allocation problem, in which each item has a cost that will be incurred to the agent it is allocated to, and each agent has a budget constraint on the total cost of items she receives. We show that a budget-feasible allocation that maximizes the NSW achieves a 1/4-approximation of EF1 and the approximation ratio is tight. The approximation ratio improves gracefully when the items have small costs compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity.

Xiaowei Wu, Bo Li, and Jiarui Gan. 2021. Budget-feasible Maximum Nash Social Welfare is Almost Envy-free. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 465–471. https://doi.org/10.24963/ijcai.2021/65
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards