Guaranteeing fairness and efficiency under budget constraints

Yuanyuan Wang (), Xin Chen (), Qizhi Fang (), Qingqin Nong () and Wenjing Liu ()
Additional contact information
Yuanyuan Wang: Ocean University of China
Xin Chen: Ocean University of China
Qizhi Fang: Ocean University of China
Qingqin Nong: Ocean University of China
Wenjing Liu: Ocean University of China

Journal of Combinatorial Optimization, 2025, vol. 49, issue 3, No 9, 21 pages

Abstract: Abstract We study the problem of how to fairly and efficiently allocate indivisible items (goods) to agents under budget constraints. Each item has a specific size, and each agent has a budget that limits the total size of the items received. To better explore efficiency, we introduce the concept of tightness, where all agents are tight. An agent is considered as tight if adding any unallocated item to her bundle would exceed her budget. Interestingly, we observe that all individual optimal (IO) allocations, which contain Pareto optimal (PO) allocations, can be extended into a tight allocation while maintaining the values of the agents’ bundles. We achieve an overall negative result for general even identical or binary valuations: there exists no allocation meeting both tightness and envy-freeness up to any item (EFX), and even relaxing it to any desired approximate EFX has been proven to be impossible. However, for single-valued valuations, we illustrate that an EFX and tight (or IO) allocation always exist, and it can be computed using a polynomial algorithm. For single-valued valuations, we establish the existence of 1/2-EFX and PO allocations, with the approximation ratio being the best possible. To further our efforts to study fairness and efficiency, we introduce a relaxed concept of tightness, partial tightness (PT), in which only the unenvied agents are tight. We find that 1/2-EFX and PT allocations are achievable by providing a pseudo-polynomial time algorithm. When agents’ budgets are identical, we can compute a 1/2-EFX and PT allocation in polynomial time.

Keywords: Fair allocation; Budget constraints; EFX; PO (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01275-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:3:d:10.1007_s10878-025-01275-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01275-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().