Algorithmic Game Theory - 14th International Symposium, SAGT 2021, Aarhus, Denmark, September 21-24, 2021, Proceedings
Algorithmic Game Theory - 14th International Symposium, SAGT 2021, Aarhus, Denmark, September 21-24, 2021, Proceedings
复制标题
算法博弈论 - 第 14 届国际研讨会，SAGT 2021，丹麦奥胡斯，2021 年 9 月 21-24 日，会议记录
DOI：
10.1007/978-3-030-85947-3_18
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
McKay M
中科院分区：
文献类型：
--
作者：
McKay M
Stable Roommates问题涉及基于代理的严格顺序偏好列表将一组代理配对。匹配必须是稳定的，这意味着没有两个代理严格地喜欢对方而不是他们分配的合作伙伴。存在许多三维变体，其中代理人被匹配成三元组。原始问题和这些变体也可以被视为享乐游戏。我们正式使用一般加法可分离的偏好，其中每个代理提供一个整数估值的每一个其他代理的三维变体。在这个变体中，我们表明，一个稳定的匹配可能不存在，相关的决策问题是完全的，即使当估值是二进制的。相比之下，我们表明，如果估值是二进制和对称的，那么一个稳定的匹配必须存在，可以在多项式时间内找到。我们还考虑了相关的问题，找到一个稳定的匹配与最大的功利福利时，估值是二元和对称的。我们表明，这个优化问题是困难的，并提出了一种新的2-近似算法。
The Stable Roommates problem involves matching a set of agents into pairs based on the agents’ strict ordinal preference lists. The matching must be stable, meaning that no two agents strictly prefer each other to their assigned partners. A number of three-dimensional variants exist, in which agents are instead matched into triples. Both the original problem and these variants can also be viewed as hedonic games. We formalise a three-dimensional variant using general additively separable preferences, in which each agent provides an integer valuation of every other agent. In this variant, we show that a stable matching may not exist and that the related decision problem is-complete, even when the valuations are binary. In contrast, we show that if the valuations are binary and symmetric then a stable matching must exist and can be found in polynomial time. We also consider the related problem of finding a stable matching with maximum utilitarian welfare when valuations are binary and symmetric. We show that this optimisation problem is-hard and present a novel 2-approximation algorithm.