Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.14825 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912000478543872 |
|---|---|
| author | Hummel, Halvard Igarashi, Ayumi |
| author_facet | Hummel, Halvard Igarashi, Ayumi |
| contents | We study the problem of allocating indivisible resources under the connectivity constraints of a graph $G$. This model, initially introduced by Bouveret et al. (published in IJCAI, 2017), effectively encompasses a diverse array of scenarios characterized by spatial or temporal limitations, including the division of land plots and the allocation of time plots. In this paper, we introduce a novel fairness concept that integrates local comparisons within the social network formed by a connected allocation of the item graph. Our particular focus is to achieve pairwise-maximin fair share (PMMS) among the "neighbors" within this network. For any underlying graph structure, we show that a connected allocation that maximizes Nash welfare guarantees a $(1/2)$-PMMS fairness. Moreover, for two agents, we establish that a $(3/4)$-PMMS allocation can be efficiently computed. Additionally, we demonstrate that for three agents and the items aligned on a path, a PMMS allocation is always attainable and can be computed in polynomial time. Lastly, when agents have identical additive utilities, we present a pseudo-polynomial-time algorithm for a $(3/4)$-PMMS allocation, irrespective of the underlying graph $G$. Furthermore, we provide a polynomial-time algorithm for obtaining a PMMS allocation when $G$ is a tree. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_14825 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Keeping the Harmony Between Neighbors: Local Fairness in Graph Fair Division Hummel, Halvard Igarashi, Ayumi Computer Science and Game Theory Data Structures and Algorithms Multiagent Systems 91B32 We study the problem of allocating indivisible resources under the connectivity constraints of a graph $G$. This model, initially introduced by Bouveret et al. (published in IJCAI, 2017), effectively encompasses a diverse array of scenarios characterized by spatial or temporal limitations, including the division of land plots and the allocation of time plots. In this paper, we introduce a novel fairness concept that integrates local comparisons within the social network formed by a connected allocation of the item graph. Our particular focus is to achieve pairwise-maximin fair share (PMMS) among the "neighbors" within this network. For any underlying graph structure, we show that a connected allocation that maximizes Nash welfare guarantees a $(1/2)$-PMMS fairness. Moreover, for two agents, we establish that a $(3/4)$-PMMS allocation can be efficiently computed. Additionally, we demonstrate that for three agents and the items aligned on a path, a PMMS allocation is always attainable and can be computed in polynomial time. Lastly, when agents have identical additive utilities, we present a pseudo-polynomial-time algorithm for a $(3/4)$-PMMS allocation, irrespective of the underlying graph $G$. Furthermore, we provide a polynomial-time algorithm for obtaining a PMMS allocation when $G$ is a tree. |
| title | Keeping the Harmony Between Neighbors: Local Fairness in Graph Fair Division |
| topic | Computer Science and Game Theory Data Structures and Algorithms Multiagent Systems 91B32 |
| url | https://arxiv.org/abs/2401.14825 |