Complexity of Problems in Cooperative Game Theory
The central aim of this project was to further develop the theory of hedonic games, which has developed rapidly in recent times and has produced many interesting results, but also important open questions. On the one hand, a conceptual contribution was sought, in which the new concept of “altruistic” hedonic games was introduced and examined in detail.
Specifically, several degrees of altruism in hedonic games were formally modeled, the properties of the resulting preference relations and stability concepts in altruistic hedonic games were investigated, the algorithmic efficiency and complexity of the corresponding verification and existence problems were determined, and restrictions (to specific graphs) and extensions (e.g., normalization) of the model as well as problems of strategic influence in altruistic hedonic games were investigated.
On the other hand, a number of technical contributions were made by solving specific open questions from the literature, in particular on “wonderfully stable decompositions” and “strictly core-stable coalitional structures” in hedonic games and on the representation of hedonic games with ordinal preferences and thresholds.
In addition, it further attempted to solve some open questions on the manipulation of power indices through union and division of players and on bribery in so-called path-disruption games.
The project has been funded by the DFG since July 2020 and was completed in June 2022.