Approximately EFX allocations for indivisible chores

DOI10.1016/J.ARTINT.2023.104037arXiv2109.07313OpenAlexW4388440994MaRDI QIDQ6152663FDOQ6152663

Authors: Sheng-Wei Zhou, Xiaowei Wu 

Publication date: 13 February 2024

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

Abstract: In this paper we study how to fairly allocate a set of m indivisible chores to a group of n agents, each of which has a general additive cost function on the items. Since envy-free (EF) allocation is not guaranteed to exist, we consider the notion of envy-freeness up to any item (EFX). In contrast to the fruitful results regarding the (approximation of) EFX allocations for goods, very little is known for the allocation of chores. Prior to our work, for the allocation of chores, it is known that EFX allocations always exist for two agents, or general number of agents with identical ordering cost functions. For general instances, no non-trivial approximation result regarding EFX allocation is known. In this paper we make some progress in this direction by showing that for three agents we can always compute a 5-approximation of EFX allocation in polynomial time. For n>=4 agents, our algorithm always computes an allocation that achieves an approximation ratio of 3n^2 regarding EFX. We also study the bi-valued instances, in which agents have at most two cost values on the chores, and provide polynomial time algorithms for the computation of EFX allocation when n=3, and (n-1)-approximation of EFX allocation when n>=4.

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

Recommendations

• EFX allocations for indivisible chores: matching-based approach
• EFX allocations for indivisible chores: matching-based approach
• On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources
• Computing fair and efficient allocations with few utility values

zbMATH Keywords

approximation algorithmfair allocation

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Approximation algorithms (68W25)

Cites Work

• Rental Harmony: Sperner's Lemma in Fair Division
• Splitting necklaces
• Almost envy-freeness with general valuations
• Fair division of indivisible goods: recent progress and open questions
• Computing fair and efficient allocations with few utility values
• A Little Charity Guarantees Almost Envy-Freeness
• A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
• Maximum Nash welfare and other stories about EFX
• Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
• On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources

Cited In (6)

• Almost proportional allocations of indivisible chores: computation, approximation and efficiency
• Algorithms for Competitive Division of Chores
• On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources
• EFX allocations for indivisible chores: matching-based approach
• EFX allocations for indivisible chores: matching-based approach
• Envy-free relaxations for goods, chores, and mixed items

This page was built for publication: Approximately EFX allocations for indivisible chores

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