Maximin Share Allocation Under Knapsack Constraints
摘要
We study a fair knapsack constrained partitioning problem where a set of indivisible goods is assigned to a set of heterogeneous agents. Each good has a cost such that the total cost of partition does not exceed the given budget. We consider the widely studied concept of fairness, namely, maximin share (MMS) fairness. For this concept of fairness, we discussed the degree of existence of fair allocation and constant approximation algorithms for different setting. Specifically, we prove that 1/3-MMS allocation always exists for the general case. For two special cases, two agents and binary valuations, we improve this approximation guarantee to 2/3 for two agents and design polynomial time algorithms to find exact MMS allocation for binary valuations.