Search papers, labs, and topics across Lattice.
This paper investigates fair allocation of indivisible goods with limited sharing, where each good can be allocated to up to *k* agents at a cost. The authors prove the existence of exact maximin share (MMS) allocations when goods are cost-sensitively shared among at least half of the agents (for even numbers of agents) and provide a Shared Bag-Filling Algorithm for approximate MMS allocations with performance guarantees dependent on the sharing cost *C* and the sharing limit *k*. The paper also introduces and analyzes the Sharing Maximin Share (SMMS) fairness notion, demonstrating its existence under specific conditions and establishing connections to constrained MMS.
Sharing isn't always caring: allowing limited, cost-sensitive sharing of indivisible goods can actually guarantee fairer resource allocation than strict exclusivity.
We study the problem of fairly allocating indivisible goods when limited sharing is allowed, that is, each good may be allocated to up to $k$ agents, while incurring a cost for sharing. While classic maximin share (MMS) allocations may not exist in many instances, we demonstrate that allowing controlled sharing can restore fairness guarantees that are otherwise unattainable in certain scenarios. (1) Our first contribution shows that exact maximin share (MMS) allocations are guaranteed to exist whenever goods are allowed to be cost-sensitively shared among at least half of the agents and the number of agents is even; for odd numbers of agents, we obtain a slightly weaker MMS guarantee. (2) We further design a Shared Bag-Filling Algorithm that guarantees a $(1 - C)(k - 1)$-approximate MMS allocation, where $C$ is the maximum cost of sharing a good. Notably, when $(1 - C)(k - 1) \geq 1$, our algorithm recovers an exact MMS allocation. (3) We additionally introduce the Sharing Maximin Share (SMMS) fairness notion, a natural extension of MMS to the $k$-sharing setting. (4) We show that SMMS allocations always exist under identical utilities and for instances with two agents. (5) We construct a counterexample to show the impossibility of the universal existence of an SMMS allocation. (6) Finally, we establish a connection between SMMS and constrained MMS (CMMS), yielding approximation guarantees for SMMS via existing CMMS results. These contributions provide deep theoretical insights for the problem of fair resource allocation when a limited sharing of resources are allowed in multi-agent environments.
