Envy-freeness in 3D Hedonic Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909278459133952 |
|---|---|
| author | McKay, Michael Cseh, Ágnes Manlove, David |
| author_facet | McKay, Michael Cseh, Ágnes Manlove, David |
| contents | We study the problem of partitioning a set of agents into coalitions based on the agents' additively separable preferences, which can also be viewed as a hedonic game. We apply three successively weaker solution concepts, namely envy-freeness, weakly justified envy-freeness, and justified envy-freeness.
In a model in which coalitions may have any size, trivial solutions exist for these concepts, which provides a strong motivation for placing restrictions on coalition size. In this paper, we require feasible coalitions to have size three. We study the existence of partitions that are envy-free, weakly justified envy-free, and justified envy-free, and the computational complexity of finding such partitions, if they exist.
We present a comprehensive complexity classification, in terms of the restrictions placed on the agents' preferences. From this, we identify a general trend that for the three successively weaker solution concepts, existence and polynomial-time solvability hold under successively weaker restrictions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_07440 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Envy-freeness in 3D Hedonic Games McKay, Michael Cseh, Ágnes Manlove, David Computer Science and Game Theory Data Structures and Algorithms We study the problem of partitioning a set of agents into coalitions based on the agents' additively separable preferences, which can also be viewed as a hedonic game. We apply three successively weaker solution concepts, namely envy-freeness, weakly justified envy-freeness, and justified envy-freeness. In a model in which coalitions may have any size, trivial solutions exist for these concepts, which provides a strong motivation for placing restrictions on coalition size. In this paper, we require feasible coalitions to have size three. We study the existence of partitions that are envy-free, weakly justified envy-free, and justified envy-free, and the computational complexity of finding such partitions, if they exist. We present a comprehensive complexity classification, in terms of the restrictions placed on the agents' preferences. From this, we identify a general trend that for the three successively weaker solution concepts, existence and polynomial-time solvability hold under successively weaker restrictions. |
| title | Envy-freeness in 3D Hedonic Games |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2209.07440 |