Welfare Approximation in Additively Separable Hedonic Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909531700723712 |
|---|---|
| author | Bullinger, Martin Chatziafratis, Vaggos Shahkar, Parnian |
| author_facet | Bullinger, Martin Chatziafratis, Vaggos Shahkar, Parnian |
| contents | Partitioning a set of $n$ items or agents while maximizing the value of the partition is a fundamental algorithmic task. We study this problem in the specific setting of maximizing social welfare in additively separable hedonic games. Unfortunately, this task faces strong computational boundaries: Extending previous results, we show that approximating welfare by a factor of $n^{1-ε}$ is NP-hard, even for severely restricted weights. However, we can obtain a randomized $\log n$-approximation on instances for which the sum of input valuations is nonnegative. Finally, we study two stochastic models of aversion-to-enemies games, where the weights are derived from Erdős-Rényi or multipartite graphs. We obtain constant-factor and logarithmic-factor approximations with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_06017 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Welfare Approximation in Additively Separable Hedonic Games Bullinger, Martin Chatziafratis, Vaggos Shahkar, Parnian Computer Science and Game Theory Data Structures and Algorithms Partitioning a set of $n$ items or agents while maximizing the value of the partition is a fundamental algorithmic task. We study this problem in the specific setting of maximizing social welfare in additively separable hedonic games. Unfortunately, this task faces strong computational boundaries: Extending previous results, we show that approximating welfare by a factor of $n^{1-ε}$ is NP-hard, even for severely restricted weights. However, we can obtain a randomized $\log n$-approximation on instances for which the sum of input valuations is nonnegative. Finally, we study two stochastic models of aversion-to-enemies games, where the weights are derived from Erdős-Rényi or multipartite graphs. We obtain constant-factor and logarithmic-factor approximations with high probability. |
| title | Welfare Approximation in Additively Separable Hedonic Games |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.06017 |