# Constrained Serial Dictatorships can be Fair

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 47 references that are in the map.
- First posted on arXiv 11 Jan 2023.

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

- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [On Truthful Mechanisms for Maximin Share Allocations](https://mlsanity.com/paper/1605.04026/) (2016)
- [Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions](https://mlsanity.com/paper/2202.08713/) (2022)
- [Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness](https://mlsanity.com/paper/1705.10706/) (2017)
- [Fair and Efficient Allocations under Lexicographic Preferences](https://mlsanity.com/paper/2012.07680/) (2020)
- [Complexity of Manipulating Sequential Allocation](https://mlsanity.com/paper/1602.06940/) (2016)
- [On Fair Division of Indivisible Items](https://mlsanity.com/paper/1805.06232/) (2018)
- [Algorithms for Manipulating Sequential Allocation](https://mlsanity.com/paper/1909.06747/) (2019)
- [Picking Sequences and Monotonicity in Weighted Fair Division](https://mlsanity.com/paper/2104.14347/) (2021)
- [Fair and Efficient Allocations Without Obvious Manipulations](https://mlsanity.com/paper/2206.11143/) (2022)
- [Strategyproof and Approximately Maxmin Fair Share Allocation of Chores](https://mlsanity.com/paper/1905.08925/) (2019)
- [Parameterized Complexity of Manipulating Sequential Allocation](https://mlsanity.com/paper/1909.08920/) (2019)
- [Optimizing over Serial Dictatorships](https://mlsanity.com/paper/2202.08097/) (2022)

## Abstract (arXiv)

When allocating indivisible items to agents, it is known that the only strategyproof mechanisms that satisfy a set of rather mild conditions are constrained serial dictatorships: given a fixed order over agents, at each step the designated agent chooses a given number of items (depending on her position in the sequence). Agents who come earlier in the sequence have a larger choice of items; however, this advantage can be compensated by a higher number of items received by those who come later. How to balance priority in the sequence and number of items received is a nontrivial question. We use a previous model, parameterized by a mapping from ranks to scores, a social welfare functional, and a distribution over preference profiles. For several meaningful choices of parameters, we show that the optimal sequence can be computed exactly in polynomial time or approximated using sampling. Our results hold for several probabilistic models on preference profiles, with an emphasis on the Plackett-Luce model. We conclude with experimental results showing how the optimal sequence is impacted by various parameters.