Complexity of Problems in Cooperative Game Theory

• Applicant: Professor Dr. Jörg-Matthias Rothe
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 201252895

• Final Report Year: 2021

Final Report Abstract

Inhaltlich sind die wichtigsten Ergebnisse (“highlights”) dieses Projekts die folgenden: • Wir initiierten eine systematische, umfassende Untersuchung zu verschiedenen Modellen des Altruismus in hedonischen Spielen und, allgemeiner, in Koalitionsbildungsspielen. • Wir erzielten Fortschritte bei der Bestimmung der Komplexität des Existenz- und Verifikationsproblems für „wondefully stable partitions“ und „strictly core stable coalition structures“, indem wir z. B. die DP-Härte des Existenzproblems zeigen konnten, und wir untersuchten verwandte Stabilitätsprobleme für wichtige Graphparameter, wo uns sogar der Nachweis von Θp2-Vollständigkeit gelang. Wir schlossen die Arbeit zu unserem Begriff cost of stability ab. Außerdem stellten wir Beziehungen zwischen hedonischen Spielen und dem Gebiet Fair Division her, führten lokale Fairness-Begriffe für hedonische Spiele ein und untersuchten ihr Verhältnis untereinander und zu anderen Lösungskonzepten für hedonische Spiele. Auch modellierten wir das Problem der Allokation von Flüchtlingen als ein hedonisches Spiel. • Wir führten eine neue kompakte Repräsentation für FEN-hedonische Spiele ein und untersuchten sie umfassend, insbesondere die Komplexität der POSSIBLE- und NECESSARY-Varianten des Existenz- und des Verifikationsproblems bezüglich der üblichen Stabilitätsbegriffe. • Wir untersuchten die Manipulation von Macht-Indizes durch Vereinigung bzw. Teilung von Spielern in gewichteten Wahlspielen sowie die strukturelle Kontrolle von WVGs durch das Hinzufügen oder Löschen von Spielern. Hier zeigten wir u. a. PP-Vollständigkeit der entsprechenden Probleme. • Wir untersuchten Bestechung in path-disruption games, zeigten NP- und ∑p2-Vollstandigkeit, und stellten Beziehungen zur cost of stability her. In diesem Projekt sind zahlreiche Publikationen in renommierten Zeitschriften und führenden Konferenzen der Gebiete Künstliche Intelligenz, Theoretische Informatik und Ökonomie sowie in internationalen, referierten Workshops entstanden.

Publications

• False-Name Manipulation in Weighted Voting Games is Hard for Probabilistic Polynomial Time, Journal of Artificial Intelligence Research, vol. 50, pp. 573–601, Juli 2014
  A. Rey und J. Rothe
  (See online at https://doi.org/10.1613/jair.4293)
• Cooperative Game Theory. In: Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, J. Rothe (Herausgeber). Springer Texts in Business and Economics, Springer-Verlag, Berlin, Heidelberg, 2015
  E. Elkind & J. Rothe
  (See online at https://doi.org/10.1007/978-3-662-47904-9_3)
• Altruistic Hedonic Games, 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’16), IFAAMAS, pp. 251–259. Singapore, 2016
  N. Nguyen, A. Rey, L. Rey, J. Rothe und L. Schend
  
• Path-Disruption Games: Bribery and a Probabilistic Model, Theory of Computing Systems, vol. 60, no. 2, pp. 222–252, Februar 2017
  A. Rey, J. Rothe und A. Marple
  (See online at https://doi.org/10.1007/s00224-016-9669-1)
• Borda-Induced Hedonic Games with Friends, Enemies, and Neutral Players, Mathematical Social Sciences, vol. 96, pp. 21–36, November 2018
  J. Rothe, H. Schadrack und L. Schend
  (See online at https://doi.org/10.1016/j.mathsocsci.2018.08.003)
• Bounds on the Cost of Stabilizing a Cooperative Game, Journal of Artificial Intelligence Research, vol. 63, pp. 987–1023, Dezember 2018
  Y. Bachrach, E. Elkind, E. Malizia, R. Meir, D. Pasechnik, J. Rosenschein, J. Rothe und M. Zuckerm
  (See online at https://doi.org/10.1613/jair.1.11270)
• Complexity of Stability, 31st International Symposium on Algorithms and Computation (ISAAC’20), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, LIPIcs, vol. 181, pp. 19:1–19:14. 2020
  F. Frei, E. Hemaspaandra und J. Rothe
  
• Hedonic Games with Ordinal Preferences and Thresholds, Journal of Artificial Intelligence Research, vol. 67, pp. 705–756, April 2020
  A. Kerkmann, J. Lang, A. Rey, J. Rothe, H. Schadrack und L. Schend
  (See online at https://doi.org/10.1613/jair.1.11531)
• Stability in Minimization-Based Altruistic Hedonic Games, 9th European Starting AI Researcher Symposium (STAIRS’20), vol. 2655, paper 3. Santiago de Compostela, Spain, 2020
  A. Wiechers und J. Rothe
  
• Altruism in Coalition Formation Games, 29th International Joint Conference on Artificial Intelligence (IJCAI’20), pp. 347–353. Yokohama, Japan, 2021
  A. Kerkmann und J. Rothe
  (See online at https://doi.org/10.24963/ijcai.2020/49)
• Local Fairness in Hedonic Games via Individual Threshold Coalitions, Theoretical Computer Scienc
  A. Kerkmann, N. Nguyen und J. Rothe
  (See online at https://doi.org/10.1016/j.tcs.2021.03.027)
• Thou Shalt Love Thy Neighbor as Thyself When Thou Playest: Altruism in Game Theory, 35th AAAI Conference on Artificial Intelligence (AAAI’21), AAAI Press. 2021
  J. Rothe