Graphenspiele

Graphenspiele ist ein Formalismus aus der Spieltheorie. Bei Graphenspielen ist jeder Spieler ein Knoten eines Graphen. Die Knoten des Graphen alias Spieler haben Verbindungen zu anderen Knoten. Jeder Spieler hat wie bei Spielen in Normalform eine Menge an Strategien. Die Auszahlung eines Spielers hängt über eine Funktion von seiner Strategie und der Strategie der mit ihm verbundenen Spieler ab. Allgemein kann man jedes Spiel in Normalform in ein Graphenspiel umwandeln. Die Größe des Graphenspiels ist nur bei bestimmten Spielen kleiner als die des strategischen. Besonders bei 2-Personen-Spielen bringt die graphische Form keinen Vorteil. Generell ist das Finden von Nash-Gleichgewichten in Graphenspielen NP-schwer. Vorteile d. h. weniger Verbindungen entstehen dann, wenn Auszahlungen der Spieler nicht von Strategien aller Spieler abhängig sind. Es existiert sogar ein Lösungsalgorithmus in polynomieller Zeit bei Graphen, die aus einem einzigen Pfad oder einer einzigen Schleife bestehen.

• E. Elkind, L. A. Goldberg, P. W. Goldberg: Nash equilibria in graphical games on trees revisited. ACM Conference on Electronic Commerce, 2006, S. 100–109.
• M. Kearns, M. Littman, S. Singh: Graphical models for game theory. Proceedings of UAI, 2001.