# Fair Division with Bounded Sharing: Binary and Non-Degenerate Valuations

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2019.

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

- [Maximin Share Guarantees via Limited Cost-Sensitive Sharing](https://mlsanity.com/paper/2602.20541/) (2026)
- [Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations](https://mlsanity.com/paper/2610.05237/) (2026)

## Abstract (arXiv)

A set of objects is to be divided fairly among agents with different tastes, modeled by additive utility-functions. If we consider the objects as indivisible, many instances of the decision problem: ``Is there a fair division of the objects among the agents'' are negative. In addition, this question is hard to solve even for most of the special cases. The latter reasons give us a good motivation to relax the problem for which the running time complexity is better, and the number of positive instances (admitting a fair division) will significantly grow. Whereas many works relax the fairness criteria, this paper introduces another relaxation: an agent is allowed to share a bounded number of objects between two or more agents in order to attain fairness. The paper studies various notions of fairness, such as proportionality, envy-freeness, equitability, and consensus. We analyze the run-time complexity of finding a fair allocation with a given number of sharings under several restrictions on the agents' valuations, such as: binary, generalized-binary, and non-degenerate.