Graphical Hedonic Games of Bounded Treewidth
Graphical Hedonic Games of Bounded Treewidth
复制标题
有界树宽的图形享乐游戏
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Dominik Peters
中科院分区：
文献类型：
--
作者：
Dominik Peters
享乐博弈是一个研究得很好的联盟形成模型，其中自私的代理人被划分为不相交的集合，代理人关心他们最终加入的联盟的组成。寻找稳定、最优或公平结果的计算问题，即使在享乐博弈的严格限制的情况下，也往往是计算上难以解决的。我们介绍了图形享乐游戏的概念，并表明，相比之下，在类的图形享乐游戏，其基础图形的有界树宽和程度，这样的问题变得容易。特别是，可以通过量化代理，联盟和（连接）分区指定的问题可以在线性时间内决定。证明是通过减少到一元二阶逻辑。我们还提供了更快的算法在特殊情况下，并表明度界的额外条件不能被丢弃。最后，我们注意到，分配不可分割的商品的问题可以建模为一个享乐游戏，使我们的研究结果意味着在适当限制的情况下找到公平和有效的分配的易处理性。
Hedonic games are a well-studied model of coalition formation, in which selfish agents are partitioned into disjoint sets and agents care about the make-up of the coalition they end up in. The computational problems of finding stable, optimal, or fair outcomes tend to be computationally intractable in even severely restricted instances of hedonic games. We introduce the notion of a graphical hedonic game and show that, in contrast, on classes of graphical hedonic games whose underlying graphs are of bounded treewidth and degree, such problems become easy. In particular, problems that can be specified through quantification over agents, coalitions, and (connected) partitions can be decided in linear time. The proof is by reduction to monadic second order logic. We also provide faster algorithms in special cases, and show that the extra condition of the degree bound cannot be dropped. Finally, we note that the problem of allocating indivisible goods can be modelled as a hedonic game, so that our results imply tractability of finding fair and efficient allocations on appropriately restricted instances.
分数享乐游戏
DOI：
10.1145/3327970
发表时间：
2019
期刊：
ACM Transactions on Economics and Computation (TEAC)
影响因子：
--
作者：
Brandl;Florian;Brandt;Harrenstein;Martin;Peters;Dominik
通讯作者：
Dominik