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.)