Hedonic Seat Arrangement Problems
Publication date
2020
Authors
Bodlaender, H.L.
Hanaka, Tesshu
Jaffke, Lars
Ono, Hirotaka
Otachi, Yota
Zanden, Tom C. van der
Editors
Seghrouchni, Amal El Fallah
Sukthankar, Gita
An, Bo
Yorke-Smith, Neil
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
In this paper, we study a variant of hedonic games, called Seat Arrangement. The model is defined by a bijection from agents with preferences to vertices in a graph. The utility of an agent depends on the neighbors in the graph. In this paper, we study the price of stability and fairness in Seat Arrangement, and the computational complexity and the parameterized complexity of finding certain "good'' seat arrangements, say Maximum Welfare Arrangement, Maximin Utility Arrangement, Stable Arrangement, and Envy-free Arrangement.
Keywords
Taverne
Citation
Bodlaender, H L, Hanaka, T, Jaffke, L, Ono, H, Otachi, Y & Zanden, T C V D 2020, Hedonic Seat Arrangement Problems. in A E F Seghrouchni, G Sukthankar, B An & N Yorke-Smith (eds), AAMAS '20: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, pp. 1777-1779. https://doi.org/10.5555/3398761.3398979