![[2602.20541] Maximin Share Guarantees via Limited Cost-Sensitive Sharing](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.20541] Maximin Share Guarantees via Limited Cost-Sensitive Sharing
Summary
This paper explores fair allocation of indivisible goods through limited cost-sensitive sharing, demonstrating how controlled sharing can restore fairness guarantees in multi-agent scenarios.
Why It Matters
The study addresses the challenge of fairly allocating resources in situations where traditional maximin share allocations may fail. By introducing cost-sensitive sharing, it provides a framework that enhances fairness in resource distribution, which is crucial in fields like economics, game theory, and AI.
Key Takeaways
- Exact maximin share allocations can exist with controlled sharing among agents.
- The Shared Bag-Filling Algorithm offers a practical approach to achieve approximate MMS allocations.
- The Sharing Maximin Share (SMMS) fairness notion extends MMS to scenarios with limited sharing.
Computer Science > Computer Science and Game Theory arXiv:2602.20541 (cs) [Submitted on 24 Feb 2026] Title:Maximin Share Guarantees via Limited Cost-Sensitive Sharing Authors:Hana Salavcova, Martin Černý, Arpita Biswas View a PDF of the paper titled Maximin Share Guarantees via Limited Cost-Sensitive Sharing, by Hana Salavcova and 1 other authors View PDF HTML (experimental) Abstract: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 allocat...