EFX Allocations Exist on Triangle-Free Multi-Graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911339060920320 |
|---|---|
| author | Afshinmehr, Mahyar Ashuri, Arash Mahmoudkhan, Pouria Mehlhorn, Kurt |
| author_facet | Afshinmehr, Mahyar Ashuri, Arash Mahmoudkhan, Pouria Mehlhorn, Kurt |
| contents | We study the fair allocation of indivisible goods among agents, with a focus on limiting envy. A central open question in this area is the existence of EFX allocations-allocations in which any envy of any agent i towards any agent j vanishes upon the removal of any single good from j's bundle. Establishing the existence of such allocations has proven notoriously difficult in general, but progress has been made for restricted valuation classes. Christodoulou et al. [2023] proved existence for graphical valuations, where goods correspond to edges in a graph, agents to nodes, and each agent values only incident edges. The graph was required to be simple, i.e., for any pair of agents, there could be at most one good that both agents value. The problem remained open, however, for multi-graph valuations, where for a pair of agents several goods may have value to both. In this setting, Sgouritsa and Sotiriou [2025] established existence whenever the shortest cycle with non-parallel edges has length at least six, while Afshinmehr et al. [2025] proved existence when the graph contains no odd cycles. In this paper, we strengthen these results by proving that EFX allocations always exist in multi-graphs that contain no cycle of length three. Assuming monotone valuations, we further provide a pseudo-polynomial time algorithm for computing such an allocation, which runs in polynomial time when agents have cancelable valuations, a strict superclass of additive valuation functions. Accordingly, our results stand as one of the only cases where EFX allocations exist for an arbitrary number of agents. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_21644 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | EFX Allocations Exist on Triangle-Free Multi-Graphs Afshinmehr, Mahyar Ashuri, Arash Mahmoudkhan, Pouria Mehlhorn, Kurt Computer Science and Game Theory We study the fair allocation of indivisible goods among agents, with a focus on limiting envy. A central open question in this area is the existence of EFX allocations-allocations in which any envy of any agent i towards any agent j vanishes upon the removal of any single good from j's bundle. Establishing the existence of such allocations has proven notoriously difficult in general, but progress has been made for restricted valuation classes. Christodoulou et al. [2023] proved existence for graphical valuations, where goods correspond to edges in a graph, agents to nodes, and each agent values only incident edges. The graph was required to be simple, i.e., for any pair of agents, there could be at most one good that both agents value. The problem remained open, however, for multi-graph valuations, where for a pair of agents several goods may have value to both. In this setting, Sgouritsa and Sotiriou [2025] established existence whenever the shortest cycle with non-parallel edges has length at least six, while Afshinmehr et al. [2025] proved existence when the graph contains no odd cycles. In this paper, we strengthen these results by proving that EFX allocations always exist in multi-graphs that contain no cycle of length three. Assuming monotone valuations, we further provide a pseudo-polynomial time algorithm for computing such an allocation, which runs in polynomial time when agents have cancelable valuations, a strict superclass of additive valuation functions. Accordingly, our results stand as one of the only cases where EFX allocations exist for an arbitrary number of agents. |
| title | EFX Allocations Exist on Triangle-Free Multi-Graphs |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2512.21644 |