Solving Woeginger's Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911886511964160 |
|---|---|
| author | Constantinescu, Andrei Lenzner, Pascal Reiffenhäuser, Rebecca Schmand, Daniel Varricchio, Giovanna |
| author_facet | Constantinescu, Andrei Lenzner, Pascal Reiffenhäuser, Rebecca Schmand, Daniel Varricchio, Giovanna |
| contents | A decade ago, Gerhard Woeginger posed an open problem that became well-known as "Woeginger's Hiking Problem": Consider a group of $n$ people that want to go hiking; everyone expresses preferences over the size of their hiking group in the form of an interval between $1$ and $n$. Is it possible to efficiently assign the $n$ people to a set of hiking subgroups so that every person approves the size of their assigned subgroup? The problem is also known as efficiently deciding if an instance of an anonymous Hedonic Game with interval approval preferences admits a wonderful partition.
We resolve the open problem in the affirmative by presenting an $O(n^5)$ time algorithm for Woeginger's Hiking Problem. Our solution is based on employing a dynamic programming approach for a specific rectangle stabbing problem from computational geometry. Moreover, we propose natural, more demanding extensions of the problem, e.g., maximizing the number of satisfied participants and variants with single-peaked preferences, and show that they are also efficiently solvable. Last but not least, we employ our solution to efficiently compute a partition that maximizes the egalitarian welfare for anonymous single-peaked Hedonic Games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_02067 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Solving Woeginger's Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games Constantinescu, Andrei Lenzner, Pascal Reiffenhäuser, Rebecca Schmand, Daniel Varricchio, Giovanna Computer Science and Game Theory Data Structures and Algorithms A decade ago, Gerhard Woeginger posed an open problem that became well-known as "Woeginger's Hiking Problem": Consider a group of $n$ people that want to go hiking; everyone expresses preferences over the size of their hiking group in the form of an interval between $1$ and $n$. Is it possible to efficiently assign the $n$ people to a set of hiking subgroups so that every person approves the size of their assigned subgroup? The problem is also known as efficiently deciding if an instance of an anonymous Hedonic Game with interval approval preferences admits a wonderful partition. We resolve the open problem in the affirmative by presenting an $O(n^5)$ time algorithm for Woeginger's Hiking Problem. Our solution is based on employing a dynamic programming approach for a specific rectangle stabbing problem from computational geometry. Moreover, we propose natural, more demanding extensions of the problem, e.g., maximizing the number of satisfied participants and variants with single-peaked preferences, and show that they are also efficiently solvable. Last but not least, we employ our solution to efficiently compute a partition that maximizes the egalitarian welfare for anonymous single-peaked Hedonic Games. |
| title | Solving Woeginger's Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2311.02067 |