Bad News for Couples: Tight Lower Bounds for Fair Division of Indivisible Items
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917181084663808 |
|---|---|
| author | la Tour, Max Dupré |
| author_facet | la Tour, Max Dupré |
| contents | 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 $n$ couples for which envy-freeness up to $Ω(\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 $n$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_01012 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Bad News for Couples: Tight Lower Bounds for Fair Division of Indivisible Items la Tour, Max Dupré Computer Science and Game Theory 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 $n$ couples for which envy-freeness up to $Ω(\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 $n$ 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. |
| title | Bad News for Couples: Tight Lower Bounds for Fair Division of Indivisible Items |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2601.01012 |