Spieltheorie für Agenten

Die Spieltheorie bietet den mathematischen Rahmen zur Analyse strategischer Interaktionen zwischen rationalen Agenten, indem sie vorhersagt, wie sich eigennützige Entscheidungsträger verhalten, wenn das Ergebnis jedes Einzelnen von den Entscheidungen der anderen abhängt.

Definition

Die Spieltheorie untersucht Situationen, in denen mehrere rationale Agenten jeweils Aktionen wählen, deren Auszahlungen von den Entscheidungen aller Agenten abhängen, und charakterisiert stabiles oder rationales gemeinsames Verhalten durch Lösungskonzepte wie Gleichgewichte.

Scope

Dieses Thema behandelt die spieltheoretischen Grundlagen, die in der Multi-Agenten-KI verwendet werden: Spiele in Normalform und Extensivform, dominante Strategien, das Nash-Gleichgewicht und dessen Existenz, gemischte Strategien und Schlüsselbeispiele wie das Gefangenendilemma und Nullsummenspiele; zusammen mit algorithmischen Fragen der Berechnung von Gleichgewichten. Es wird untersucht, wie Agenten über einander nachdenken und welche gemeinsamen Verhaltensweisen stabil sind. Die Entwicklung von Interaktionsregeln wird unter Mechanismusdesign behandelt, und das Erlernen des Spielens von Spielen gehört zum Unterfeld des maschinellen Lernens.

Core questions

• Wie werden strategische Interaktionen als Spiele in Normal- oder Extensivform dargestellt?
• Welche Lösungskonzepte (dominante Strategien, Nash-Gleichgewicht) sagen voraus, wie sich rationale Agenten verhalten?
• Wann ist die Existenz eines Gleichgewichts garantiert, möglicherweise in gemischten Strategien?
• Wie schwierig ist es, Gleichgewichte zu berechnen, und wie beeinflusst dies ihre Verwendung durch Agenten?

Key concepts

• Spiele in Normalform und Extensivform
• Auszahlungen und Strategien
• dominante Strategie
• Nash-Gleichgewicht
• gemischte Strategien
• Nullsummenspiele und Minimax
• Gefangenendilemma
• Gleichgewichtsberechnung

Key theories

Nash-Gleichgewicht

Ein Nash-Gleichgewicht ist ein Strategieprofil, bei dem kein Agent seine Auszahlung durch einseitige Änderung seiner eigenen Strategie verbessern kann; Nash bewies, dass jedes endliche Spiel mindestens ein solches Gleichgewicht besitzt, möglicherweise in gemischten Strategien.

Minimax in Nullsummenspielen

In Zwei-Spieler-Nullsummenspielen garantiert von Neumanns Minimax-Theorem einen Wert und optimale (möglicherweise randomisierte) Strategien für beide Spieler, wodurch die Spieltheorie mit der adversariellen Entscheidungsfindung verbunden wird.

Dominante Strategien und Dilemmata

Die Analyse von Spielen mittels dominanter Strategien erklärt Ergebnisse wie das Gefangenendilemma, bei dem individuell rationale Entscheidungen zu einem kollektiv schlechteren Ergebnis führen, was die Spannung zwischen individueller und Gruppenrationalität verdeutlicht.

Clinical relevance

Die spieltheoretische Analyse beeinflusst das Design von Auktionen und Märkten, Sicherheits- und Patrouillenstrategien, Netzwerk-Routing und -Überlastung sowie automatisierte Verhandlungen, indem sie vorhersagt, wie sich strategische Agenten verhalten werden, und stabile Ergebnisse in Wettbewerbssituationen identifiziert.

History

Die Spieltheorie wurde von von Neumann und Morgenstern (1944) begründet und durch Nashs Gleichgewichtskonzept (1950) erweitert. Sie wurde zentral für die Wirtschaftswissenschaften und ab den 1990er Jahren für die KI und Informatik durch die algorithmische Spieltheorie, die die rechnerische Komplexität von Gleichgewichten und deren Verwendung in Multi-Agenten-Systemen untersucht.

Key figures

• John von Neumann
• Oskar Morgenstern
• John F. Nash
• Yoav Shoham
• Kevin Leyton-Brown

Seminal works

• nash1950
• vonneumann1944
• shoham2009

Frequently asked questions

Was ist ein Nash-Gleichgewicht?

Ein Nash-Gleichgewicht ist eine Kombination von Strategien, eine pro Agent, so dass kein einzelner Agent besser abschneiden kann, indem er nur seine eigene Strategie ändert, während die anderen ihre beibehalten. Es erfasst eine Vorstellung von stabilem, wechselseitig konsistentem rationalem Verhalten.

Warum ist das Gefangenendilemma für KI-Agenten wichtig?

Das Gefangenendilemma zeigt, dass Agenten, die in ihrem eigenen rationalen Eigeninteresse handeln, zu einem Ergebnis gelangen können, das für alle schlechter ist, als wenn sie kooperiert hätten. Es verdeutlicht, warum die Gestaltung von Anreizen und Koordinationsmechanismen wichtig ist, wenn Systeme von eigennützigen Agenten aufgebaut werden.