# Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations

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

## Key facts

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

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

- [Fairness Behind a Veil of Ignorance: A Welfare Analysis for Automated Decision Making](https://mlsanity.com/paper/1806.04959/) (2018)
- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning](https://mlsanity.com/paper/2104.14504/) (2021)
- [Maximum Nash Welfare and Other Stories About EFX](https://mlsanity.com/paper/2001.09838/) (2020)
- [Fair and Truthful Mechanisms for Dichotomous Valuations](https://mlsanity.com/paper/2002.10704/) (2020)
- [Fair Allocation of Indivisible Goods: Improvement and Generalization](https://mlsanity.com/paper/1704.00222/) (2017)
- [Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations](https://mlsanity.com/paper/2005.07370/) (2020)
- [Weighted Envy-Freeness in Indivisible Item Allocation](https://mlsanity.com/paper/1909.10502/) (2019)
- [Finding Fair and Efficient Allocations When Valuations Don't Add Up](https://mlsanity.com/paper/2003.07060/) (2020)
- [Maximizing Nash Social Welfare in 2-Value Instances](https://mlsanity.com/paper/2107.08965/) (2021)
- [Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions](https://mlsanity.com/paper/2202.08713/) (2022)
- [Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations](https://mlsanity.com/paper/2012.12710/) (2020)
- [Truthful and Fair Mechanisms for Matroid-Rank Valuations](https://mlsanity.com/paper/2109.05810/) (2021)
- [Fair and Efficient Allocations of Chores under Bivalued Preferences](https://mlsanity.com/paper/2110.09601/) (2021)
- [How to Fairly Allocate Easy and Difficult Chores](https://mlsanity.com/paper/2110.11285/) (2021)
- [Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations](https://mlsanity.com/paper/2206.08495/) (2022)

## Abstract (arXiv)

We study the problem of fairly allocating a set of indivisible goods among agents with em bivalued submodular valuations -- each good provides a marginal gain of either a or b (a < b) and goods have decreasing marginal gains. This is a natural generalization of two well-studied valuation classes -- bivalued additive valuations and binary submodular valuations. We present a simple sequential algorithmic framework, based on the recently introduced Yankee Swap mechanism, that can be adapted to compute a variety of solution concepts, including max Nash welfare (MNW), leximin and p-mean welfare maximizing allocations when a divides b. This result is complemented by an existing result on the computational intractability of MNW and leximin allocations when a does not divide b. We show that MNW and leximin allocations guarantee each agent at least frac25 and fracab+2a of their maximin share, respectively, when a divides b. We also show that neither the leximin nor the MNW allocation is guaranteed to be envy free up to one good (EF1). This is surprising since for the simpler classes of bivalued additive valuations and binary submodular valuations, MNW allocations are known to be envy free up to any good (EFX).