Residential Collegefalse
Status已發表Published
Budget-feasible Maximum Nash Social Welfare is Almost Envy-free
Xiaowei Wu1; Bo Li2; Jiarui Gan3
2021-08
Conference Name30th International Joint Conference on Artificial Intelligence (IJCAI-21)
Source PublicationProceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021.
Conference Date19-27 27 August 2021
Conference PlaceVirtual, Online
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.

KeywordBudget-feasible Nash Social Welfare Envy-free
URLView the original
Language英語English
The Source to ArticlePB_Publication
Scopus ID2-s2.0-85125458425
Citation statistics
Document TypeConference paper
CollectionTHE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU)
Affiliation1.IOTSC, University of Macau
2.Department of Computing, The Hong Kong Polytechnic University
3.Max Planck Institute for Software Systems
First Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Xiaowei Wu,Bo Li,Jiarui Gan. Budget-feasible Maximum Nash Social Welfare is Almost Envy-free[C], 2021.
APA Xiaowei Wu., Bo Li., & Jiarui Gan (2021). Budget-feasible Maximum Nash Social Welfare is Almost Envy-free. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021..
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Xiaowei Wu]'s Articles
[Bo Li]'s Articles
[Jiarui Gan]'s Articles
Baidu academic
Similar articles in Baidu academic
[Xiaowei Wu]'s Articles
[Bo Li]'s Articles
[Jiarui Gan]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Xiaowei Wu]'s Articles
[Bo Li]'s Articles
[Jiarui Gan]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.