EFX Allocations for Indivisible Chores: Matching-Based Approach
Authors:
- Yusuke KobayashiYKYusuke Kobayashi
- Ryoga MaharaRMRyoga Mahara
- Souta SakamotoSSSouta Sakamoto
Preprint
Abstract
One of the most important topics in discrete fair division is whether an EFX allocation exists for any instance. Although the existence of EFX allocations is a standing open problem for both goods and chores, the understanding of the existence of EFX allocations for chores is less established compared to goods. We study the existence of EFX allocation for chores under the assumption that all agent's cost functions are additive. Specifically, we show the existence of EFX allocations for the following three cases: (i) the number of chores is at most twice the number of agents, (ii) the cost functions of all agents except for one are identical ordering, and (iii) the number of agents is three and each agent has a personalized bi-valued cost function. Furthermore, we provide a polynomial time algorithm to find an EFX allocation for each case.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Unified Fair Allocation of Goods and Chores via CopiesACM Transactions on Economics and Computation, 2023
- Approximately EFX allocations for indivisible choresArtificial Intelligence, 2023
- Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle eliminationTheoretical Computer Science, 2020
- Almost Envy-Freeness with General ValuationsSIAM Journal on Discrete Mathematics, 2020
- The Unreasonable Fairness of Maximum Nash WelfareACM Transactions on Economics and Computation, 2019
- The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal IncomesJournal of Political Economy, 2011
- Fair Division and Collective Welfare2003
- Cake-Cutting Algorithms: Be Fair if You Can.The American Mathematical Monthly, 2000