Algorithmische Strategien in Mehrpersonen-Spielen - Konzepte und Methoden für kooperationsfähige Systeme

• Antragsteller: Professor Dr. Erich Grädel
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2011
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 40219435

Ziel dieses Vorhabens ist die Erforschung theoretischer Grundlagen und algorithmischer Methoden zur Bestimmung des optimalen Verhaltens interaktiver, nicht-terminierender Systeme. Im Mittelpunkt des Interesses stehen zustandsbasierte Systeme, welche durch Mehrpersonen-Spiele auf Graphen modelliert werden können. Die Informatik-Forschung hat sich in dieser Fragestellung bisher hauptsächlich auf die Analyse reiner Konfliktsituationen zwischen zwei Agenten (z.B. System und Umgebung) konzentriert und für das entsprechende Modell der Zweipersonen- Nullsummen-Spiele eine ausgereifte Theorie mit bedeutenden Anwendungen geschaffen. Darauf aufbauend soll hier eine Theorie entwickelt werden, welche dem Kooperationspotential Rechnung trägt, das sich in der Interaktion von zwei oder mehreren Agenten ergibt, deren Zielvorgaben sich nicht notwendigerweise gegenseitig ausschließen. Das für diese Fragestellung grundlegende Modell der Nicht-Nullsummen-Spiele ist für endliche Abläufe in der klassischen (mathematischen und ökonomischen) Spieltheorie wohl etabliert. Im Hinblick auf die Erfassung nicht-terminierender, also unendlicher, Abläufe sollen fundamentale Lösungskonzepte ausgebaut und algorithmisch zugänglich gemacht werden. Neben Spielen mit perfekter Information werden dabei Effekte von Informationsunschärfe in verschiedenen Graden untersucht. Ein besonderer Schwerpunkt liegt in der Integration logisch-algebraischer Ansätze mit Methoden der Künstlichen Intelligenz zur praktikablen Umsetzung der algorithmischenLösungen.

• DFG-Verfahren: Sachbeihilfen