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.