# Maximin Share Guarantees via Limited Cost-Sensitive Sharing

arXiv: https://arxiv.org/abs/2602.20541 · HTML: https://mlsanity.com/paper/2602.20541/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 30 references that are in the map.
- First posted on arXiv 24 Feb 2026.

## Builds on (most cited first, 13 of 13)

- [Online Fair Division: A Survey](https://mlsanity.com/paper/1911.09488/) (2019)
- [A Little Charity Guarantees Almost Envy-Freeness](https://mlsanity.com/paper/1907.04596/) (2019)
- [Fair Division Under Cardinality Constraints](https://mlsanity.com/paper/1804.09521/) (2018)
- [Envy-freeness up to any item with high Nash welfare: The virtue of donating items](https://mlsanity.com/paper/1902.04319/) (2019)
- [An Improved Approximation Algorithm for Maximin Shares](https://mlsanity.com/paper/1903.00029/) (2019)
- [Approximation Algorithms for Maximin Fair Division](https://mlsanity.com/paper/1703.01851/) (2017)
- [Breaking the 3/4 Barrier for Approximate Maximin Share](https://mlsanity.com/paper/2307.07304/) (2023)
- [Improving EFX Guarantees through Rainbow Cycle Number](https://mlsanity.com/paper/2103.01628/) (2021)
- [A tight negative example for MMS fair allocations](https://mlsanity.com/paper/2104.04977/) (2021)
- [Fair Division: The Computer Scientist's Perspective](https://mlsanity.com/paper/2005.04855/) (2020)
- [Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations](https://mlsanity.com/paper/1912.00459/) (2019)
- [Efficient Fair Division with Minimal Sharing](https://mlsanity.com/paper/1908.01669/) (2019)
- [Group Fairness and Multi-criteria Optimization in School Assignment](https://mlsanity.com/paper/2403.15623/) (2024)

## Abstract (arXiv)

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) ≥ 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.