EFX and PO Allocation Exists for Two Types of Goods
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914237911138304 |
|---|---|
| author | Davidiuk, Vladimir Dementiev, Yuriy Ignatiev, Artur Sagunov, Danil |
| author_facet | Davidiuk, Vladimir Dementiev, Yuriy Ignatiev, Artur Sagunov, Danil |
| contents | We study the problem of fairly and efficiently allocating indivisible goods among agents with additive valuations. We focus on envy-freeness up to any good (EFX) -- an important fairness notion in fair division of indivisible goods. A central open question in this field is whether EFX allocations always exist for any number of agents. While prior work has established EFX existence for settings with at most three distinct valuations (Prakash HV et al. 2025) and for two types of goods (Gorantla, Marwaha, and Velusamy 2023), the general case remains unresolved.
In this paper, we extend the existent knowledge by proving that EFX allocations satisfying Pareto optimality (PO) always exist and can be computed in quasiliniear time when there are two types of goods, given that the valuations are positive. This result strengthens the existing work of (Gorantla, Marwaha, and Velusamy 2023), which only guarantees the existence of EFX allocations without ensuring Pareto optimality. Our findings demonstrate a fairly simple and efficient algorithm constructing an EFX+PO allocation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_03438 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | EFX and PO Allocation Exists for Two Types of Goods Davidiuk, Vladimir Dementiev, Yuriy Ignatiev, Artur Sagunov, Danil Computer Science and Game Theory We study the problem of fairly and efficiently allocating indivisible goods among agents with additive valuations. We focus on envy-freeness up to any good (EFX) -- an important fairness notion in fair division of indivisible goods. A central open question in this field is whether EFX allocations always exist for any number of agents. While prior work has established EFX existence for settings with at most three distinct valuations (Prakash HV et al. 2025) and for two types of goods (Gorantla, Marwaha, and Velusamy 2023), the general case remains unresolved. In this paper, we extend the existent knowledge by proving that EFX allocations satisfying Pareto optimality (PO) always exist and can be computed in quasiliniear time when there are two types of goods, given that the valuations are positive. This result strengthens the existing work of (Gorantla, Marwaha, and Velusamy 2023), which only guarantees the existence of EFX allocations without ensuring Pareto optimality. Our findings demonstrate a fairly simple and efficient algorithm constructing an EFX+PO allocation. |
| title | EFX and PO Allocation Exists for Two Types of Goods |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2601.03438 |