Nearly Equitable Allocations Beyond Additivity and Monotonicity
Preprint
Abstract
Equitability (EQ) in fair division requires that items be allocated such that all agents value the bundle they receive equally. With indivisible items, an equitable allocation may not exist, and hence we instead consider a meaningful analog, EQx, that requires equitability up to any item. EQx allocations exist for monotone, additive valuations. However, if (1) the agents' valuations are not additive or (2) the set of indivisible items includes both goods and chores (positively and negatively valued items), then prior to the current work it was not known whether EQx allocations exist or not. We study both the existence and efficient computation of EQx allocations. (1) For monotone valuations (not necessarily additive), we show that EQx allocations always exist. Also, for the large class of weakly well-layered valuations, EQx allocations can be found in polynomial time. Further, we prove that approximately EQx allocations can be computed efficiently under general monotone valuations. (2) For non-monotone valuations, we show that an EQx allocation may not exist, even for two agents with additive valuations. Under some special cases, however, we establish existence and efficient computability of EQx allocations. This includes the case of two agents with additive valuations where each item is either a good or a chore, and there are no mixed items. In addition, we show that, under nonmonotone valuations, determining the existence of EQx allocations is weakly NP-hard for two agents and strongly NP-hard for more agents.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- The frontier of intractability for EFX with two agentsTheoretical Computer Science, 2025
- Equitability and welfare maximization for allocating indivisible itemsAutonomous Agents and Multi-Agent Systems, 2022
- Almost Envy-Freeness with General ValuationsSIAM Journal on Discrete Mathematics, 2020
- Existence of a simple and equitable fair division: A short proofMathematical Social Sciences, 2017
- The Efficiency of Fair Division with Connected PiecesACM Transactions on Economics and Computation, 2015
- On the existence of equitable cake divisionsInformation Sciences, 2013
- On the computability of equitable divisionsDiscrete Optimization, 2012
- Fair Division and Collective Welfare2003