Residential College | false |
Status | 即將出版Forthcoming |
Approximate envy-freeness in indivisible resource allocation with budget constraints | |
Wu, Xiaowei1![]() ![]() | |
2025-03-01 | |
Source Publication | Information and Computation
![]() |
ISSN | 0890-5401 |
Volume | 303Pages: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. |
DOI | 10.1016/j.ic.2024.105264 |
URL | View the original |
Language | 英語English |
Scopus ID | 2-s2.0-85214571089 |
Fulltext Access | |
Citation statistics | |
Document Type | Journal article |
Collection | THE STATE KEY LABORATORY OF INTERNET OF THINGS FOR SMART CITY (UNIVERSITY OF MACAU) |
Corresponding Author | Li, Bo |
Affiliation | 1.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 Affilication | University 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. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment