Fair Allocation of Indivisible Goods with Different Entitlements

We study fair allocation of indivisible goods to agents with unequal entitlements. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang [14] wherein the agents are assumed to be symmetric. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee. Next, we assume that the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. We show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items. (The full version of the paper is available in https://arxiv.org/abs/1703.01649.) CCS Concepts •Computing methodologies → Multi-agent systems;