# Existence of MMS Allocations with Mixed Manna

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2024.

## Built on by (most cited first, 1 of 1)

- [The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items](https://mlsanity.com/paper/2601.12849/) (2026)

## Abstract (arXiv)

Maximin share (MMS) allocations are a popular relaxation of envy-free allocations that have received wide attention in the fair division of indivisible items. Although MMS allocations of goods can fail to exist, previous work has found conditions under which they exist. Specifically, MMS allocations of goods exist whenever m ≤ n+5, and this bound is tight in the sense that they can fail to exist when m = n+6. The techniques used to obtain these results do not apply to the mixed manna setting, leaving the question of whether similar results hold for the general setting. This paper addresses this by introducing new techniques to handle these settings. In particular, we are able to answer this question completely for the chores setting, and partially for the mixed manna setting. An agent i is a em chores agent if it considers every item to be a chore and a em non-negative agent if its MMS guarantee is non-negative. In this paper, we prove that an MMS allocation exists as long as m ≤ n+5 and either (i) every agent is a chores agent, or (ii) there exists a non-negative agent. In addition, for n ≤ 3, we also prove that an MMS allocation exists as long as m ≤ n+5, regardless of the types of agents. To the best of our knowledge, these are the first non-trivial results pertaining to the existence of exact MMS allocations in the mixed manna setting.