<p>The maximin share (MMS) allocation problem under a knapsack constraint is to allocate a set of indivisible goods to a set of <i>n</i> 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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1331_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="65" /> </InlineMediaObject> <EquationSource Format="TEX">$\epsilon \in (0, 1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϵ</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, we prove that <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1331_Article_IEq2.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="55" /> </InlineMediaObject> <EquationSource Format="TEX">$(\frac{93}{95}+ \epsilon )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mfrac> <mn>93</mn> <mn>95</mn> </mfrac> <mo>+</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-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 <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1331_Article_IEq3.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="30" /> </InlineMediaObject> <EquationSource Format="TEX">$\frac{n}{3n-2}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mi>n</mi> <mrow> <mn>3</mn> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> </mfrac> </math></EquationSource> </InlineEquation>-approximate MMS allocation. When <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1331_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$n=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1331_Article_IEq5.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$n=3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, by more careful analysis, we improve the approximation ratios to <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1331_Article_IEq6.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="8" /> </InlineMediaObject> <EquationSource Format="TEX">$\frac{2}{3}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>2</mn> <mn>3</mn> </mfrac> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1331_Article_IEq7.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="8" /> </InlineMediaObject> <EquationSource Format="TEX">$\frac{1}{2}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </math></EquationSource> </InlineEquation>, respectively.</p>

Approximate maximin share allocation for indivisible goods under a knapsack constraint

期刊论文
发表日期：

2025年7月3日

查看全文

Bin Deng,
Weidong Li

摘要

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)$ $ϵ \in (0, 1)$ , we prove that $(\frac{93}{95}+ \epsilon )$ $(\frac{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}$ $\frac{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}$ $\frac{2}{3}$ and $\frac{1}{2}$ $\frac{1}{2}$ , respectively.