论文标题
享乐主义座位安排问题
Hedonic Seat Arrangement Problems
论文作者
论文摘要
在本文中，我们研究了享乐游戏的变体，称为\ textsc {seat Blangement}。该模型是由代理的双线试验所定义的，这些代理彼此偏爱$ g $中的顶点。代理的效用取决于图中分配的邻居。更确切地说，这是代理商对分配给邻居的代理商拥有的偏好的所有邻居的总和。我们首先考虑不同类别偏好的稳定性和公平性的价格。特别是，我们表明存在一个实例，使得公平性（{\ sf pof}）一般是无限的。此外，我们显示上限$ \ tilde {d}（g）$，几乎紧密的下限$ \ tilde {d}（g）-1/4 $的{\ sf pof}，其中$ \ tilde {d}（g）$是输入图的平均程度。然后，我们研究了问题的计算复杂性，以找到某些``'''''座位安排，例如\ textsc {功利主义安排}，\ textsc {egalitaraniant Archement}，\ textsc {stable Brespement}，和\ textsc {new textsc {Enty sew note-Free-Freebement}。我们从输入图中连接的组件的最大顺序的角度的角度给出了四个\ textsc {seat bengement}的计算复杂性的二分法。对于参数化的复杂性，可以在时间$ n^{o（γ）} $的时间内解决\ textsc {实用性安排}，而在ETH下不能以时间$ f（γ）n^{o（γ）} $求解，其中$ n $是代理的数量，$γ$是vertex copper图的$γ$。此外，我们表明\ textsc {egalitarian安排}和\ textsc {Enty nievy-free-frebement}即使在有界顶点封面编号的图上，NP也很弱。最后，我们证明，当通过$ k+γ$参数化时，确定是否可以通过$ k $掉期从给定的安排获得稳定的安排，而可以在时间$ n^{o（k）} $中解决。
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 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 $\tilde{d}(G)$ and an almost tight lower bound $\tilde{d}(G)-1/4$ of {\sf PoF}, where $\tilde{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 \textsc{Utilitarian Arrangement}, \textsc{Egalitarian Arrangement}, \textsc{Stable Arrangement}, and \textsc{Envy-free Arrangement}. We give dichotomies of computational complexity of four \textsc{Seat Arrangement} problems from the perspective of the maximum order of connected components in an input graph. For the parameterized complexity, \textsc{Utilitarian Arrangement} can be solved in time $n^{O(γ)}$, while it cannot be solved in time $f(γ)n^{o(γ)}$ under ETH, where $n$ is the number of agents and $γ$ is the vertex cover number of an input graph. Moreover, we show that \textsc{Egalitarian Arrangement} and \textsc{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)}$.
