Nearly Equitable Allocations Beyond Additivity and Monotonicity

Abstract

Equitability (EQ) in fair division requires that items be allocated such that all agents value the bundle they receive equally. With indivisible items, equitability is not guaranteed when the allocation is complete. We hence consider a meaningful analog: equitability up to any item (EQX). 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 this 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, and for the large class of weakly well-layered valuations, these allocations can be found in polynomial time. Further, we prove that approximately EQX allocations can be computed efficiently under general monotone valuations. (2) For nonmonotone valuations, we show that an EQX allocation may not exist, even for two agents with additive valuations. Under some special cases, however, we establish the 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 general, we show that, under additive nonmonotone valuations, determining the existence of EQX allocations is weakly NP-hard for two agents and strongly NP-hard for more agents. We also give a pseudo-polynomial time algorithm for this problem for a constant number of agents.