Residential Collegefalse
Status即將出版Forthcoming
Approximate envy-freeness in indivisible resource allocation with budget constraints
Wu, Xiaowei1; Li, Bo2; Gan, Jiarui3
2025-03-01
Source PublicationInformation and Computation
ISSN0890-5401
Volume303Pages:105264
Abstract

We study the fair allocation of indivisible resources under knapsack constraints, where a set of items with varied costs and values are to be allocated among a group of agents. Each agent has a budget constraint on the total cost of items she can receive. The goal is to compute a budget-feasible allocation that is envy-free (EF), in which the agents do not envy each other for the items they receive, nor do they envy a charity, which is endowed with all the unallocated items. Since EF allocations barely exist (even without the budget constraints), we are interested in the relaxed notion of envy-freeness up to one item (EF1). Our results are twofold. Firstly, for the general setting where agents have heterogeneous valuations and budgets, we show that a budget-feasible allocation that maximizes the Nash social welfare (NSW) achieves a 1/4-approximation of EF1. This approximation ratio carries to the general case of arbitrary monotone subadditive valuations. The approximation ratio improves gracefully when the items have small cost compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity, and to 1 if the agents further have identical valuations. Secondly, when agents have identical valuations, we design a polynomial-time algorithm that computes a 1/2-approximate EF1 allocation for an arbitrary number of agents. For the case of identical agents and the case of two agents, we propose polynomial-time algorithms for computing EF1 allocations.

DOI10.1016/j.ic.2024.105264
URLView the original
Language英語English
Scopus ID2-s2.0-85214571089
Fulltext Access
Citation statistics
Document TypeJournal article
CollectionTHE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU)
Corresponding AuthorLi, Bo
Affiliation1.State Key Laboratory of Internet of Things for Smart City, University of Macau, Macao
2.Department of Computing, The Hong Kong Polytechnic University, Hong Kong
3.Department of Computer Science, University of Oxford, United Kingdom
First Author AffilicationUniversity of Macau
Recommended Citation
GB/T 7714
Wu, Xiaowei,Li, Bo,Gan, Jiarui. Approximate envy-freeness in indivisible resource allocation with budget constraints[J]. Information and Computation, 2025, 303, 105264.
APA Wu, Xiaowei., Li, Bo., & Gan, Jiarui (2025). Approximate envy-freeness in indivisible resource allocation with budget constraints. Information and Computation, 303, 105264.
MLA Wu, Xiaowei,et al."Approximate envy-freeness in indivisible resource allocation with budget constraints".Information and Computation 303(2025):105264.
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
[Wu, Xiaowei]'s Articles
[Li, Bo]'s Articles
[Gan, Jiarui]'s Articles
Baidu academic
Similar articles in Baidu academic
[Wu, Xiaowei]'s Articles
[Li, Bo]'s Articles
[Gan, Jiarui]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Wu, Xiaowei]'s Articles
[Li, Bo]'s Articles
[Gan, Jiarui]'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.