# Fair Shares: Feasibility, Domination and Incentives

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 31 references that are in the map.
- First posted on arXiv 16 May 2022.

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

- [Fair Public Decision Making](https://mlsanity.com/paper/1611.04034/) (2016)
- [Fair Allocation of Indivisible Goods: Improvement and Generalization](https://mlsanity.com/paper/1704.00222/) (2017)
- [Approximation Algorithms for Computing Maximin Share Allocations](https://mlsanity.com/paper/1503.00941/) (2015)
- [An Improved Approximation Algorithm for Maximin Shares](https://mlsanity.com/paper/1903.00029/) (2019)
- [Best-of-Both-Worlds Fair-Share Allocations](https://mlsanity.com/paper/2102.04909/) (2021)
- [On Truthful Mechanisms for Maximin Share Allocations](https://mlsanity.com/paper/1605.04026/) (2016)
- [A tight negative example for MMS fair allocations](https://mlsanity.com/paper/2104.04977/) (2021)
- [Fair-Share Allocations for Agents with Arbitrary Entitlements](https://mlsanity.com/paper/2103.04304/) (2021)
- [Fair Allocation of Indivisible Goods to Asymmetric Agents](https://mlsanity.com/paper/1703.01649/) (2017)
- [Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness](https://mlsanity.com/paper/2109.08644/) (2021)
- [An Algorithmic Framework for Approximating Maximin Share Allocation of Chores](https://mlsanity.com/paper/1907.04505/) (2019)
- [Approximate and Strategyproof Maximin Share Allocation of Chores with Ordinal Preferences](https://mlsanity.com/paper/2012.13884/) (2020)
- [Guaranteeing Maximin Shares: Some Agents Left Behind](https://mlsanity.com/paper/2105.09383/) (2021)
- [Improved maximin fair allocation of indivisible items to three agents](https://mlsanity.com/paper/2205.05363/) (2022)

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

- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Fair Allocation in Dynamic Mechanism Design](https://mlsanity.com/paper/2406.00147/) (2024)

## Abstract (arXiv)

We consider fair allocation of a set M of indivisible goods to n equally-entitled agents, with no monetary transfers. Every agent i has a valuation vi from some given class of valuation functions. A share s is a function that maps a pair (vi,n) to a value, with the interpretation that if an allocation of M to n agents fails to give agent i a bundle of value at least equal to s(vi,n), this serves as evidence that the allocation is not fair towards i. For such an interpretation to make sense, we would like the share to be feasible, meaning that for any valuations in the class, there is an allocation that gives every agent at least her share. The maximin share was a natural candidate for a feasible share for additive valuations. However, Kurokawa, Procaccia and Wang [2018] show that it is not feasible. We initiate a systematic study of the family of feasible shares. We say that a share is self maximizing if truth-telling maximizes the implied guarantee. We show that every feasible share is dominated by some self-maximizing and feasible share. We seek to identify those self-maximizing feasible shares that are polynomial time computable, and offer the highest share values. We show that a SM-dominating feasible share -- one that dominates every self-maximizing (SM) feasible share -- does not exist for additive valuations (and beyond). Consequently, we relax the domination property to that of domination up to a multiplicative factor of ρ (called ρ-dominating). For additive valuations we present shares that are feasible, self-maximizing and polynomial-time computable. For n agents we present such a share that is frac2n3n-1-dominating. For two agents we present such a share that is (1 - ε)-dominating. Moreover, for these shares we present poly-time algorithms that compute allocations that give every agent at least her share.