# Fair and Truthful Mechanisms for Dichotomous Valuations

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2020.

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

- [Longitudinal Fairness with Censorship](https://mlsanity.com/paper/2203.16024/) (2022)
- [Pushing the Frontier on Approximate EFX Allocations](https://mlsanity.com/paper/2406.12413/) (2024)
- [Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness](https://mlsanity.com/paper/2109.08644/) (2021)
- [Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations](https://mlsanity.com/paper/2206.08495/) (2022)
- [EFX Allocations Exist for Binary Valuations](https://mlsanity.com/paper/2308.05503/) (2023)
- [Understanding EFX Allocations: Counting and Variants](https://mlsanity.com/paper/2504.03951/) (2025)
- [On the existence of EFX allocations in multigraphs](https://mlsanity.com/paper/2502.09777/) (2025)
- [Multilevel Fair Allocation with Matroid-Rank Preferences](https://mlsanity.com/paper/2512.24105/) (2025)
- [Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations](https://mlsanity.com/paper/2302.03087/) (2023)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)
- [EFX Allocation In (Multi)Hypergraphs](https://mlsanity.com/paper/2608.03171/) (2026)
- [Simultaneous Envy and Equitability Guarantees](https://mlsanity.com/paper/2608.26410/) (2026)
- [Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations](https://mlsanity.com/paper/2610.05237/) (2026)

## Abstract (arXiv)

We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations. To gauge the robustness of our positive results, we also study ε-dichotomous valuations, in which the added value of any item to a set is either non-positive, or in the range [1, 1 + ε]. We show several impossibility results in this setting, and also a positive result: for players that have additive ε-dichotomous valuations with sufficiently small ε, we design a randomized truthful mechanism with strong ex-post guarantees. For ρ = frac11 + ε, the allocations that it produces generate at least a ρ-fraction of the maximum welfare, and enjoy ρ-approximations for various fairness properties, such as being envy-free up to one item (EF1), and giving each player at least her maximin share.