# Hedonic Seat Arrangement Problems

arXiv: https://arxiv.org/abs/2002.10898 · HTML: https://mlsanity.com/paper/2002.10898/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Feb 2020.

## Built on by (most cited first, 1 of 1)

- [Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence](https://mlsanity.com/paper/2511.09174/) (2025)

## Abstract (arXiv)

In this paper, we study a variant of hedonic games, called textscSeat Arrangement. The model is defined by a bijection from agents with preferences for each other to vertices in a graph G. 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 tilded(G) and an almost tight lower bound tilded(G)-1/4 of sf PoF, where tilded(G) is the average degree of an input graph. Then we investigate the computational complexity of problems to find certain ``good'' seat arrangements, say textscUtilitarian Arrangement, textscEgalitarian Arrangement, textscStable Arrangement, and textscEnvy-free Arrangement. We give dichotomies of computational complexity of four textscSeat Arrangement problems from the perspective of the maximum order of connected components in an input graph. For the parameterized complexity, textscUtilitarian Arrangement can be solved in time nO(γ), while it cannot be solved in time f(γ)no(γ) under ETH, where n is the number of agents and γ is the vertex cover number of an input graph. Moreover, we show that textscEgalitarian Arrangement and textscEnvy-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 nO(k).