TY - UNPB

T1 - Hedonic Seat Arrangement Problems

AU - Bodlaender, Hans L.

AU - Hanaka, Tesshu

AU - Jaffke, Lars

AU - Ono, Hirotaka

AU - Otachi, Yota

AU - Zanden, Tom C. van der

PY - 2020/2

Y1 - 2020/2

N2 - In this paper, we study a variant of hedonic games, called \textsc{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 assigned in the graph. More precisely, it is the sum over all neighbors of the preferences that the agent has towards the agent assigned to the neighbor. We first consider the price of stability and fairness for different classes of preferences. In particular, we show that there is an instance such that the price of fairness ({\sf PoF}) is unbounded in general. Moreover, we show an upper bound d̃ (G) and an almost tight lower bound d̃ (G)−1/4 of {\sf PoF}, where d̃ (G) is the average degree of an input graph. Then we investigate the computational complexity of problems to find certain ``good'' seat arrangements, say Maximum Welfare Arrangement, Maximin Utility Arrangement, Stable Arrangement, and Envy-free Arrangement. We give dichotomies of computational complexity of four Seat Arrangement problems from the perspective of the maximum order of connected components in an input graph. For the parameterized complexity, Maximum Welfare Arrangement can be solved in time n^O(γ), while it cannot be solved in time f(γ)^o(γ) under ETH, where γ is the vertex cover number of an input graph. Moreover, we show that Maximin Utility Arrangement and Envy-free Arrangement are weakly NP-hard even on graphs of bounded vertex cover number. Finally, we prove that determining whether a stable arrangement can be obtained from a given arrangement by k swaps is W[1]-hard when parameterized by k+γ, whereas it can be solved in time n^O(k).

AB - In this paper, we study a variant of hedonic games, called \textsc{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 assigned in the graph. More precisely, it is the sum over all neighbors of the preferences that the agent has towards the agent assigned to the neighbor. We first consider the price of stability and fairness for different classes of preferences. In particular, we show that there is an instance such that the price of fairness ({\sf PoF}) is unbounded in general. Moreover, we show an upper bound d̃ (G) and an almost tight lower bound d̃ (G)−1/4 of {\sf PoF}, where d̃ (G) is the average degree of an input graph. Then we investigate the computational complexity of problems to find certain ``good'' seat arrangements, say Maximum Welfare Arrangement, Maximin Utility Arrangement, Stable Arrangement, and Envy-free Arrangement. We give dichotomies of computational complexity of four Seat Arrangement problems from the perspective of the maximum order of connected components in an input graph. For the parameterized complexity, Maximum Welfare Arrangement can be solved in time n^O(γ), while it cannot be solved in time f(γ)^o(γ) under ETH, where γ is the vertex cover number of an input graph. Moreover, we show that Maximin Utility Arrangement and Envy-free Arrangement are weakly NP-hard even on graphs of bounded vertex cover number. Finally, we prove that determining whether a stable arrangement can be obtained from a given arrangement by k swaps is W[1]-hard when parameterized by k+γ, whereas it can be solved in time n^O(k).

U2 - 10.48550/arXiv.2002.10898

DO - 10.48550/arXiv.2002.10898

M3 - Preprint

BT - Hedonic Seat Arrangement Problems

PB - arXiv

ER -