Bad News for Couples: Tight Lower Bounds for Fair Division of Indivisible Items

preprint2026arXivOpen access

Abstract

We consider the problem of fairly allocating indivisible goods to couples, where each couple consists of two agents with distinct additive valuations. We show that there exist instances of allocating indivisible items to nn couples for which envy-freeness up to Ω(n)Ω(\sqrt{n}) items cannot be guaranteed. This closes the gap by matching the upper bound of Manurangsi and Suksompong, which applies to arbitrary instances with nn agents in total. This result is somewhat surprising, as that upper bound was conjectured not to be tight for instances consisting only of small groups.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.