The budgeted maximin share allocation problem

Abstract We are given a set of indivisible goods and a set of n agents where each good has a size and each agent has an additive valuation function and a budget. The budgeted maximin share allocation problem is to find a feasible allocation such that the size of the bundle allocated to each agent does not exceed its budget, and the minimum ratio of the valuation and the maximin share (MMS) value of any agent is as large as possible, where the MMS value of each agent is that he can achieve by dividing the goods into n bundles, and receiving his least desirable bundle. In this paper, we prove that the existence of 1/3 -approximate MMS allocation and give an instance which does have a (3 /4 + ε)-approximate MMS allocation, for any ε ∈ (0, 1). Moreover, we provide a polynomial time algorithm to find an ( 1/3 − ε)-approximate MMS allocation, and prove that there is no polynomial time algorithm which can find a ( 2/3 + ε)-approximate MMS allocation for any instance unless P = N P.