Komplexität von Problemen der kooperativen Spieltheorie

• Antragsteller: Professor Dr. Jörg-Matthias Rothe
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 201252895

Das zentrale Ziel dieses Fortsetzungantrags ist die Weiterentwicklung der Theorie der hedonischen Spiele, die sich in jüngster Zeit ganz rasant entwickelt und viele höchst interessante Ergebnisse, aber auch sehr wichtige offene Fragen hervorgebracht hat. Dabei streben wir einerseits einen konzeptuellen Beitrag an, indem wir den neuen Begriff der 'altruistischen' hedonischen Spiele einführen und im Detail untersuchen. Konkret werden wir mehrere Grade von Altruismus in hedonischen Spielen formal modellieren, die Eigenschaften der resultierenden Präferenzrelationen und Stabilitätskonzepte in altruistischen hedonischen Spielen untersuchen (und, wenn möglich, charakterisieren), die algorithmische Effizienz und Komplexität der entsprechenden Verifikations- und Existenzprobleme bestimmen und Einschränkungen (auf spezielle Graphen) und Erweiterungen (z. B. Normalisierung) des Modells sowie Probleme der strategischen Einflussnahme in altruistischen hedonischen Spielen untersuchen. Andererseits wollen wir eine Reihe von technischen Beiträgen leisten, indem wir spezielle offene Fragen aus der Literatur lösen, 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 werden wir weiter versuchen, einige aus dem ursprünglichen Antrag offen gebliebene schwierige Fragen zur Manipulation von Macht-Indizes durch Vereinigung und Teilung von Spielern und zur Bestechung in path-disruption games zu lösen. (Die meisten Ziele aus dem ursprünglichen Antrag konnten erreicht werden; darüber hinaus konnten Resultate zu hedonischen Spielen erzielt werden.)

• DFG-Verfahren: Sachbeihilfen