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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Maximin Share Allocation Under Knapsack Constraints

  • Bin Deng

摘要

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.