权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Complexity of Problems in Cooperative Game Theory

合作博弈论问题的复杂性

基本信息

批准号：
201252895
负责人：
Professor Dr. Jörg-Matthias Rothe
金额：
--
依托单位：
Arbeitsgruppe Computational Complexity and Cryptology
依托单位国家：
德国
项目类别：
Research Grants
财政年份：
2011
资助国家：
德国
起止时间：
2010-12-31 至 2020-12-31
项目状态：
已结题

来源：
https://gepris.dfg.de/gepris/projekt/201252895?language=en
关键词：
Complexity Problems 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.)

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