@inproceedings{69aca5d9ec8542af922fcc17933a4cbb,
title = "Fair allocation of indivisible goods to asymmetric agents",
abstract = "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.).",
keywords = "Approximation, Entitlements, Fairness, Indivisible, Proportionality, Stochastic",
author = "Alireza Farhadi and Mohammadtaghi Hajiaghayi and David Pennock and Mohammad Ghodsi and Masoud Seddighin and Sebastien Lahaie and Saeed Seddighin and Hadi Yami",
year = "2017",
language = "American English",
series = "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS",
publisher = "International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)",
pages = "1535--1537",
editor = "Edmund Durfee and Michael Winikoff and Kate Larson and Sanmay Das",
booktitle = "16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017",
note = "16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017 ; Conference date: 08-05-2017 Through 12-05-2017",
}