Komplexität von Problemen der kooperativen Spieltheorie

Das zentrale Ziel dieses Projekts ist die Weiterentwicklung der Theorie der hedonischen Spiele, die sich in jüngster Zeit rasant entwickelt und viele interessante Ergebnisse, aber auch wichtige offene Fragen hervorgebracht hat. Dabei wird zum einen ein konzeptueller Beitrag angestrebt, bei dem der neue Begriff der „altruistischen“ hedonistischen Spiele eingeführt und detailliert untersucht wird.

Konkret werden mehrere Grade von Altruismus in hedonischen Spielen formal modelliert, die Eigenschaften der resultierenden Präferenzrelationen und Stabilitätskonzepte in altruistischen hedonischen Spielen untersucht, die algorithmische Effizienz und Komplexität der entsprechenden Verifikations- und Existenzprobleme bestimmt und Einschränkungen (auf spezielle Graphen) und Erweiterungen (z.B. Normalisierung) des Modells sowie Probleme der strategischen Einflussnahme in altruistischen hedonischen Spielen untersucht.

Andererseits sollen eine Reihe von technischen Beiträgen geleistet werden, indem spezielle offene Fragen aus der Literatur gelöst werden, insbesondere zu „wundervoll stabilen Zerlegungen“ und „strikt kernstabilen Koalitionsstrukturen“ in hedonischen Spielen und zur Darstellung hedonischer Spiele mit ordinalen Präferenzen und Schwellenwerten.

Darüber hinaus wird weiter versucht, einige offene Fragen zur Manipulation von Machtindizes durch Vereinigung und Teilung von Spielern und zur Bestechung in sogenannten path-disruption games zu lösen.