Complexity of Problems in Cooperative Game Theory

这一延长提案的中心目标是进一步发展享乐博弈理论，这一理论最近发展迅速，产生了许多非常有趣的结果，但也有一些非常重要的开放问题。一方面，我们试图通过引入“利他主义”享乐游戏的新概念并对其进行详细研究，从而在概念上做出贡献。具体来说，我们将正式建模享乐博弈中不同程度的利他主义，研究利他享乐博弈中由此产生的偏好关系和稳定性概念的性质（如果可能的话，提供表征），确定相应验证和存在问题的算法效率和复杂性，考虑模型的限制（对特殊图类）和扩展（例如，规范化），探讨利他主义享乐博弈中的策略影响问题。另一方面，我们打算通过解决文献中的特定开放问题做出一些技术贡献，特别是关于享乐游戏中的“非常稳定的分区”和“严格核心稳定的联盟结构”，以及用顺序偏好和阈值表示它们。此外，我们将继续尝试解决一些棘手的问题，如通过合并和分裂玩家来操纵权力指数，以及路径破坏游戏中的贿赂。（最初提议的大部分目标都已实现，其范围可以根据享乐游戏的结果而扩大。）

The central objective of this prolongation proposal is to make further progress in the theory of hedonic games that has rapidly developed recently and has yielded many highly interesting results, but also some very important open problems. On the one hand, we seek to make a conceptual contribution by introducing the novel concept of 'altruistic' hedonic game and by studying it in detail. Specifically, we will formally model various degrees of altruism in hedonic games, study the properties of the resulting preference relations and stability concepts in altruistic hedonic games (providing, if possible, characterizations), determine the algorithmic efficiency and complexity of the corresponding verification and existence problems, consider restrictions (to special graph classes) and extensions (e.g., normalization) of the model, and investigate problems of strategic influence in altruistic hedonic games. On the other hand, we intend to make a number of technical contributions by solving specific open problems from the literature, in particular regarding 'wonderfully stable partitions' and 'strictly core-stable coalition structures' in hedonic games as well as representing them with ordinal preferences and thresholds. Furthermore, we will keep trying to solve some of the hard questions on manipulating power indices by merging and splitting of players and on bribery in path-disruption games. (Most of the goals from the original proposal have been solved; its scope could be extended by results on hedonic games.)