Solving Woeginger's Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games
Rattachement africain : ch, de, nl, it. Niveau de preuve : code pays fourni par la source.
Le résumé fourni par la source
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.
Ce résumé expose les affirmations des auteurs. BNTIC ne l’interprète pas comme une validation indépendante des résultats.
Le contrôle bibliographique ouvert
Où se fait cette recherche
-
ETH Zurich pays non établi dans la noticeUniversité ou école supérieure
-
Hasso Plattner Institute pays non établi dans la noticeStructure de recherche
-
University of Potsdam Hasso Plattner Institute pays non établi dans la noticeUniversité ou école supérieure
-
University of Amsterdam pays non établi dans la noticeUniversité ou école supérieure
-
University of Bremen pays non établi dans la noticeUniversité ou école supérieure
-
University of Calabria pays non établi dans la noticeUniversité ou école supérieure
ETH Zurich, Hasso Plattner Institute et Hasso Plattner Institute — University of Potsdam, avec 3 autres affiliations.
Une affiliation ne permet pas de déduire la nationalité d’un auteur.