# Pareto optimal coalitions of fixed size

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jan 2019.

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

- [Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivals](https://mlsanity.com/paper/2601.16091/) (2026)
- [Exact Algorithms and Lower Bounds for Forming Coalitions of Constrained Maximum Size](https://mlsanity.com/paper/2505.22384/) (2025)
- [Metric Hedonic Games on the Line](https://mlsanity.com/paper/2602.05888/) (2026)

## Abstract (arXiv)

We tackle the problem of partitioning players into groups of fixed size, such as allocating eligible students to shared dormitory rooms. Each student submits preferences over the other individual students. We study several settings, which differ in the size of the rooms to be filled, the orderedness or completeness of the preferences, and the way of calculating the value of a coalition---based on the best or worst roommate in the coalition. In all cases, we determine the complexity of deciding the existence, and then finding a Pareto optimal assignment, and the complexity of verifying Pareto optimality for a given assignment.