# (Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 34 references that are in the map.
- First posted on arXiv 6 Feb 2022.

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

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [EFX Exists for Three Agents](https://mlsanity.com/paper/2002.05119/) (2020)
- [Maximum Nash Welfare and Other Stories About EFX](https://mlsanity.com/paper/2001.09838/) (2020)
- [Fair Division with Binary Valuations: One Rule to Rule Them All](https://mlsanity.com/paper/2007.06073/) (2020)
- [Finding Fair and Efficient Allocations](https://mlsanity.com/paper/1707.04731/) (2017)
- [Approximation Algorithms for Maximin Fair Division](https://mlsanity.com/paper/1703.01851/) (2017)
- [A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation](https://mlsanity.com/paper/1909.00740/) (2019)
- [Greedy Algorithms for Maximizing Nash Social Welfare](https://mlsanity.com/paper/1801.09046/) (2018)
- [Fair and Efficient Allocations of Chores under Bivalued Preferences](https://mlsanity.com/paper/2110.09601/) (2021)
- [On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources](https://mlsanity.com/paper/2012.06788/) (2020)
- [Competitive division of a mixed manna](https://mlsanity.com/paper/1702.00616/) (2017)
- [An Algorithmic Framework for Approximating Maximin Share Allocation of Chores](https://mlsanity.com/paper/1907.04505/) (2019)
- [Greedy Algorithms for Fair Division of Mixed Manna](https://mlsanity.com/paper/1911.11005/) (2019)
- [Two Algorithms for Additive and Fair Division of Mixed Manna](https://mlsanity.com/paper/2007.04129/) (2020)
- [PROPm Allocations of Indivisible Goods to Multiple Agents](https://mlsanity.com/paper/2105.11348/) (2021)

## Abstract (arXiv)

We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents, where each item may be a good (positively valued) for some agents and a bad (negatively valued) for others, i.e., a mixed manna. As fairness notions, we consider arguably the strongest possible relaxations of envy-freeness and proportionality, namely envy-free up to any item (EFX and EFX0), and proportional up to the maximin good or any bad (PropMX and PropMX0). Our efficiency notion is Pareto-optimality (PO). We study two types of instances: (i) Separable, where the item set can be partitioned into goods and bads, and (ii) Restricted mixed goods (RMG), where for each item j, every agent has either a non-positive value for j, or values j at the same vj>0. We obtain polynomial-time algorithms for the following: (i) Separable instances: PropMX0 allocation. (ii) RMG instances: Let pure bads be the set of items that everyone values negatively. - PropMX allocation for general pure bads. - EFX+PropMX allocation for identically-ordered pure bads. - EFX+PropMX+PO allocation for identical pure bads. Finally, if the RMG instances are further restricted to binary mixed goods where all the vj's are the same, we strengthen the results to guarantee EFX0 and PropMX0 respectively.