Complexity of Problems in Cooperative Game Theory

The central objective of this project is to make further progress in the theory of hedonic games that have recently developed rapidly and have yielded many interesting results, but also a number of important questions and problems.

On the one hand, we seek to make a conceptual contribution by introducing the novel concept of  an “alturistic” hedocnic game and studying it in detail. Specifically, we will formally model various degrees of alturism in hedonic games, study the properties of the resulting preference relations and stbility concepts in alturistic hedonic games, determine the algorithmic efficiency and commplexity of the corresponding verification and existing problems, to consider restrictions (i.e. special graph classes) and extensions (i.e. normalization) of the model and  to investigate problems of strategic influence in alturistic hedonic games.

On the other hand, we intend to  make a number of technical contributions by solving specific open problems, in particular regarding “wonderfully stable partitions” and “strictly core-stable coalition sturctures” in hedocnic 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 as well as bribery in so-clled path disruption games.