Approximate maximin share allocation for indivisible goods under a knapsack constraint

Bin Deng () and Weidong Li ()
Additional contact information
Bin Deng: Yunnan University
Weidong Li: Yunnan University

Journal of Combinatorial Optimization, 2025, vol. 50, issue 1, No 5, 16 pages

Abstract: Abstract The maximin share (MMS) allocation problem under a knapsack constraint is to allocate a set of indivisible goods to a set of n heterogeneous agents, such that the total cost of the allocated goods does not exceed the given budget, and the approximation ratio of the MMS allocation is as large as possible. For any $$\epsilon \in (0, 1)$$ ϵ ∈ ( 0 , 1 ) , we prove that $$(\frac{93}{95}+ \epsilon )$$ ( 93 95 + ϵ ) -approximate MMS allocation does not always exist for two agents, while the MMS allocation problem without a knapsack constraint always has an MMS allocation for two agents. We propose a bag-filling based algorithm that can produce a $$\frac{n}{3n-2}$$ n 3 n - 2 -approximate MMS allocation. When $$n=2$$ n = 2 and $$n=3$$ n = 3 , by more careful analysis, we improve the approximation ratios to $$\frac{2}{3}$$ 2 3 and $$\frac{1}{2}$$ 1 2 , respectively.

Keywords: Fair allocation; Maximin share; Bag-filling; Knapsack constraint (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-01331-1 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:50:y:2025:i:1:d:10.1007_s10878-025-01331-1

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

DOI: 10.1007/s10878-025-01331-1

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 ().