Fair Allocation of Indivisible Goods to Asymmetric Agents

DOI10.1613/JAIR.1.11291zbMATH Open1454.91104arXiv1703.01649OpenAlexW2910782816WikidataQ128628358 ScholiaQ128628358MaRDI QIDQ4611397FDOQ4611397

Authors: Alireza Farhadi, Mohammad Ghodsi, Sébastien Lahaie, David M. Pennock, Masoud Seddighin, S. Seddighin, Hadi Yami, Mohammad T. Hajiaghayi 

Publication date: 18 January 2019

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Abstract: We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. 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 wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. 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. Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem w.l.o.g, 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.

Full work available at URL: https://arxiv.org/abs/1703.01649

Recommendations

• Fair allocation of indivisible goods: the two-agent case
• Distributed fair allocation of indivisible goods
• Fair Allocation of Indivisible Goods
• Allocating indivisible goods to strategic agents: pure Nash equilibria and fairness
• scientific article; zbMATH DE number 910820
• Fair allocation of indivisible goods: beyond additive valuations
• Fair allocation of indivisible goods with minimum inequality or minimum envy
• Asymmetrically fair rules for an indivisible good problem with a budget constraint
• Fair allocation of indivisible goods: improvement
• Fair division of mixed divisible and indivisible goods

zbMATH Keywords

fair allocation of indivisible goodsagents with unequal entitlementsstochastic agentsstochastic items

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Stochastic models in economics (91B70)

Cited In (24)

• A Little Charity Guarantees Almost Envy-Freeness
• Maximin share guarantee for goods with positive externalities
• Almost proportional allocations of indivisible chores: computation, approximation and efficiency
• The price of fairness for indivisible goods
• Asymptotic existence of proportionally fair allocations
• Weighted fair division of indivisible items: a review
• The fair division of hereditary set systems
• An improved approximation algorithm for maximin shares
• Competitive equilibrium with indivisible goods and generic budgets
• Closing gaps in asymptotic fair division
• Fair division with two-sided preferences
• Fair Allocation of Indivisible Goods
• Almost envy-freeness for groups: improved bounds via discrepancy theory
• Weighted fair division with matroid-rank valuations: monotonicity and strategyproofness
• Picking sequences and monotonicity in weighted fair division
• Approximate maximin shares for groups of agents
• On maximum weighted Nash welfare for binary valuations
• Fair division of indivisible goods: recent progress and open questions
• Fairly allocating many goods with few queries
• FAIR ALLOCATION BASED ON TWO CRITERIA : A DEA GAME VIEW OF "ADD THEM UP AND DIVIDE BY TWO"(<Special Issue>Operations Research for Performance Evaluation)
• Fairness in temporal slot assignment
• Communication complexity of discrete fair division
• A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
• Mind the gap: cake cutting with separation

This page was built for publication: Fair Allocation of Indivisible Goods to Asymmetric Agents

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4611397)