Solving Woeginger’s Hiking Problem: Wonderful Partitions in Anonymous Hedonic Games
Date Issued
2024
Author(s)
Abstract
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⁵) 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.
We resolve the open problem in the affirmative by presenting an O(n⁵) 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.
Subjects
Algorithmic Game Theory
;
Dynamic Programming
;
Anonymous Hedonic Games
;
Single-Peaked Preferences
;
Social Optimum
;
Wonderful Partitions
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Institution
Type
conference paper
Journal/Edited collection
51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) = Leibniz International Proceedings in Informatics (LIPIcs), Band 297
Start page
48:1
End page
48:18
Secondary publication
Yes
Document version
Published Version
Language
English
File(s)![Thumbnail Image]()
Loading...
Name
Constantinescu et al_Solving Woegingers Hiking Problem_2024_published-version.pdf
Size
1.45 MB
Format
Adobe PDF
Checksum
(MD5):aa25921e9b744882619cfb6c22a41478