Seminar: Games Played on Graphs

Seminar im Sommersemester 2022 an der Westfälischen Wilhelms-Universität Münster

Veranstalter: Prof. Dr. Markus Müller-Olm, Jens Gutsfeld, Christoph Ohrem

Eintrag für diese Veranstaltung im HIS/LSF

Hinweise

Ort und Zeit

Die Vorträge finden im Semester montags 14:15-15:45 Uhr statt.

Der Ort sowie die genauen Termine der einzelnen Vorträge werden zu gegebener Zeit bekannt gegeben.

Thema und Zielgruppe

Reaktive Systeme sind Systeme die Ihre Umgebung kontinuierlich mithilfe von Sensoren beobachten und mit Aktoren auf beobachtete Änderungen reagieren und damit Ihre Umgebung steuern und kontrollieren. Derartige Systeme sind in der Praxis weiterverbreitet, insbesondere im Bereich eingebetteter Systeme. Ein wichtiger Ansatz zur Synthese reaktiver Systeme sind Spiele auf Graphen. Dabei modelliert man das System und seine Umgebung durch zwei antagonistische Spieler. Die möglichen Ausführungsituationen werden durch die Knoten eines Spielgraphen modelliert, in denen jeweils einer dieser Spieler einen Nachfolgeknoten wählen kann. Der insgesamt in einem Spielverlauf gewählte Pfad im Graphen entspricht dann einer prinzipiell möglichen Interaktion des Systems mit seiner Umgebung. Die Gewinnbedingungen für die beiden Spieler werden dabei so gewählt, dass der Spieler, der das System modelliert, genau dann gewinnt, wenn das Gesamtverhalten alle wünschenswerten Eigenschaften, d.h. die Spezifikation des Systems, erfüllt. Der Spieler, der die Umgebung modelliert, gewinnt demgegenüber dann, wenn die Spezifikation verletzt wird. Damit kann das Syntheseproblem für ein reaktives System formal als das Problem der Synthese einer Gewinnstrategie für den Spieler, der das System modelliert, aufgefasst und behandelt werden. 

Um verschiedene Arten von Spezifikationen ausdrücken zu können, werden die Spielgraphen an den Knoten und Kanten mit Zusatzinformationen angereichert und verschiedenste Arten von Gewinnbedingungen untersucht. Neben dem oben skizzierten Szenario von Zweipersonenspielen mit antagonistischen Spielern (Nullsummenspielen) werden in der Literatur auch Spiele auf Graphen mit mehr als zwei Spielern und Nichtnullsummenspiele mit (teilweise) gemeinsamen Spielzielen untersucht. Überdies interessiert man sich nicht nur für die Synthese von Gewinnstrategien sondern auch für andere Qualitätskriterien für gute Wahlen von Strategien wie z.B. sogenannte Nash-Equilibira oder Subgame-Perfect Equilibria.

In diesem Seminar wollen wir uns mit ausgewählten Originalartikeln aus dem Bereich der Spiele auf Graphen auseinandersetzen, die durch Anwendungen in der Informatik motiviert sind. Vorkenntnisse aus der Spieltheorie oder aus dem Gebiet der Spiele auf Graphen sind für die Teilnahme am Seminar nicht erforderlich, wohl aber das Interesse und die Bereitschaft sich mit anspruchsvollen informatisch/mathematischen Fragestellungen auseinanderzusetzen.

Das Seminar richtet sich an Masterstudierende im Fach Informatik oder im Fach Mathematik mit Nebenfach Informatik. In den M.Sc. Studiengängen kann es für das Modul „Informatikseminar“ angerechnet werden, im M.Sc. Informatik auch für das Modul "Seminar Formale Methoden". Im M.Ed. kann es für eines der Seminarmodule im Fach Informatik gewählt werden.