Trembling-hand-perfektes Gleichgewicht

Das trembling-hand-perfekte Gleichgewicht bzw. perfekte Gleichgewicht der zitternden Hand stellt in der Spieltheorie eine Möglichkeit der Selektion von Nash-Gleichgewichten dar. Entwickelt wurde es von Reinhard Selten, der die Idee 1975 unter dem Namen „A Model of Slight Mistakes“ im „International Journal of Game Theory“ veröffentlichte. Hierbei geht es darum festzustellen, wie anfällig ein Gleichgewicht gegenüber Fehlern eines Spielers ist. Nach Selten gibt es keine Fehler, wenn die Spieler absolut rational handeln. In der Realität muss man allerdings mit falschen Entscheidungen des Gegenspielers rechnen. Um dies spieltheoretisch darzustellen, wurde das Trembling-hand-perfekte Gleichgewicht entwickelt.

Einfache Darstellung des Ansatzes

Reinhard Selten (2001)

Einfach ausgedrückt bedeutet die Idee des trembling-hand-perfekten Gleichgewichts: Angenommen Spieler A geht davon aus, dass Spieler B immer die Strategie ${\begin{aligned}b_{1}\end{aligned}}$ spielt und die beste Antwort von Spieler A auf ${\begin{aligned}b_{1}\end{aligned}}$ ist seine Strategie ${\begin{aligned}a_{1}\end{aligned}}$. Ist dann immer Strategie ${\begin{aligned}a_{1}\end{aligned}}$ zu spielen auch dann noch die optimale Wahl, wenn Spieler B aus Versehen, sprich mit einer geringen Fehlerwahrscheinlichkeit von $(\epsilon )$, ${\begin{aligned}b_{2}\end{aligned}}$ spielt? Wenn unter diesen Umständen ${\begin{aligned}a_{1}\end{aligned}}$ noch immer die beste Strategie von Spieler A ist, so handelt es sich um eine Trembling-hand-perfekte Strategie.

Trembling-hand-perfektes Gleichgewicht in Normalformspielen

Durch das folgende Normalformspiel, wird der Ansatz des Trembling-hand-perfekten Gleichgewichts anhand folgender Auszahlungsmatrix sehr einfach verdeutlicht:

Spieler A/Spieler B	(${\begin{aligned}b_{1}\end{aligned}}$)	(${\begin{aligned}b_{2}\end{aligned}}$)
(${\begin{aligned}a_{1}\end{aligned}}$)	(3, 3)	(5, 0)
(${\begin{aligned}a_{2}\end{aligned}}$)	(-2, -2)	(5, 0)

Die beiden Nash-Gleichgewichte sind in diesem Beispiel bei ${\begin{aligned}(a_{1},b_{1})\end{aligned}}$ und ${\begin{aligned}(a_{2},b_{2})\end{aligned}}$. Nun soll ermittelt werden, ob eines der beiden Gleichgewichte (oder auch beide), Trembling-hand-perfekte Gleichgewichte sind. Angenommen Spieler A möchte seine Strategie ${\begin{aligned}a_{1}\end{aligned}}$ spielen und geht davon aus, dass Spieler B seine Strategie ${\begin{aligned}b_{1}\end{aligned}}$ spielen wird, da beide dann eine Auszahlung von 3 bekämen. Spieler A ist sich allerdings nicht vollkommen sicher, ob Spieler B nicht doch mit einer geringen Fehlerwahrscheinlichkeit seine Strategie ${\begin{aligned}b_{2}\end{aligned}}$ spielt. Um herauszufinden, ob ${\begin{aligned}a_{1}\end{aligned}}$ trotz dieser Fehlerwahrscheinlichkeit von Spieler B noch immer die beste Wahl von Spieler A und somit Trembling-hand-perfekt ist, muss folgendes überprüft werden: Die erwartete Auszahlung von Spieler A wenn er ${\begin{aligned}a_{1}\end{aligned}}$ wählt muss mindestens so groß sein, wie die erwartete Auszahlung für die Wahl von ${\begin{aligned}a_{2}\end{aligned}}$.

$(\epsilon )$ sei die Fehlerwahrscheinlichkeit von Spieler B, die als sehr klein angenommen wird. Das heißt, $(1-\epsilon )$ ist die damit verbundene Gegenwahrscheinlichkeit. Mit $0<(\epsilon )<<1$

Die erwartete Auszahlung von Spieler A für die Wahl von ${\begin{aligned}a_{1}\end{aligned}}$ ist also:

$\mathrm {E} [u(a_{1})]=(1-\epsilon )[u(a_{1},b_{1})]+(\epsilon )[u(a_{1},b_{2})]$

= $(1-\epsilon )\cdot 3$ + $(\epsilon )\cdot 5$

Im Vergleich dazu die erwartete Auszahlung der Strategie ${\begin{aligned}a_{2}\end{aligned}}$:

$\mathrm {E} [u(a_{2})]=(1-\epsilon )[u(a_{2},b_{1})]+(\epsilon )[u(a_{2},b_{2})]$

= $(1-\epsilon )\cdot (-2)$ + $(\epsilon )\cdot 5$

Es ist unschwer zu erkennen, dass:

$(1-\epsilon )\cdot 3$ + $(\epsilon )\cdot 5$ > $(1-\epsilon )\cdot (-2)$ + $(\epsilon )\cdot 5$

Auch wenn Spieler B mit einer geringen Fehlerwahrscheinlichkeit ${\begin{aligned}b_{2}\end{aligned}}$ spielt, ist ${\begin{aligned}a_{1}\end{aligned}}$ für Spieler A die bestmögliche Wahl. Also ist die Strategie ${\begin{aligned}a_{1}\end{aligned}}$ Trembling-hand-perfekt. Ein Trembling-hand-perfektes Gleichgewicht besteht allerdings aus einer Kombination zweier Trembling-hand-perfekten Strategien. Um also zu prüfen, ob es sich bei der Strategiekombination ${\begin{aligned}(a_{1},b_{1})\end{aligned}}$ um ein solches handelt, muss auch ${\begin{aligned}b_{1}\end{aligned}}$ von Spieler B getestet werden. Analog zur Strategie ${\begin{aligned}a_{1}\end{aligned}}$ sieht dies folgendermaßen aus:

Die erwartete Auszahlung von Spieler B für die Wahl von ${\begin{aligned}b_{1}\end{aligned}}$ beträgt:

$\mathrm {E} [u(b_{1})]=(1-\epsilon )[u(a_{1},b_{1})]+(\epsilon )[u(a_{2},b_{1})]$

= $(1-\epsilon )\cdot 3$ + $(\epsilon )\cdot (-2)$

Im Vergleich dazu die erwartete Auszahlung der Strategie ${\begin{aligned}b_{2}\end{aligned}}$:

$\mathrm {E} [u(b_{2})]=(1-\epsilon )[u(a_{1},b_{2})]+(\epsilon )[u(a_{2},b_{2})]$

= $(1-\epsilon )\cdot 0$ + $(\epsilon )\cdot 0$

Und wiederum ist eindeutig zu erkennen, dass:

$0<(1-\epsilon )\cdot 3+(\epsilon )\cdot (-2)=3-(5\cdot \epsilon )$

Damit ist auch die Strategie ${\begin{aligned}b_{1}\end{aligned}}$ Trembling-hand-perfekt und es handelt sich beim Nash-Gleichgewicht ${\begin{aligned}(a_{1},b_{1})\end{aligned}}$ um ein Trembling-hand-perfektes Gleichgewicht.

Formale Definition mithilfe eines perturbierten Spiels

Einfache Definition eines perturbierten Spiels

Ein perturbiertes Spiel, ist eine Kopie des zugrundeliegenden Spiels, mit der Einschränkung, dass jeder Spieler alle reinen Strategien mit einer positiven Wahrscheinlichkeit spielen muss. Das heißt, im normalen Spiel ist es Spieler A möglich seine Strategien $0\leq \epsilon _{a}\leq 1$ zu spielen. Im perturbierten Spiel muss $\epsilon >0$ sein.

Formale Definition

Ausgangspunkt sei ein Spiel in strategischer Form:

${\begin{aligned}G=(I,(M_{i}),(P_{i}))\end{aligned}}$, und ${\begin{aligned}(i\in I)\end{aligned}}$

Wobei ${\begin{aligned}I\end{aligned}}$ die Menge der Spieler darstellt, ${\begin{aligned}M_{i}\end{aligned}}$ das Set an gemischten Strategien ist, welches auf der möglichen Verteilung der reinen Strategien ${\begin{aligned}S_{i}\end{aligned}}$ basiert und es sich bei ${\begin{aligned}P_{i}\end{aligned}}$ um die erwartete Auszahlung von Spieler ${\begin{aligned}i\end{aligned}}$ handelt. Die Zentrale Idee, um mögliche Fehler der Spieler abzubilden, ist es anzunehmen, dass keine reine Strategie mit einer Wahrscheinlichkeit von null gespielt werden kann. In einem solchen perturbierten Spiel gilt:

Für jeden Spieler ${\begin{aligned}(i\in I)\end{aligned}}$ mit ${\begin{aligned}n_{i}\end{aligned}}$ reinen Strategien, ist ${\begin{aligned}\epsilon _{i}=(\epsilon _{i}^{1},\epsilon _{i}^{2},...,\epsilon _{i}^{n})\end{aligned}}$ die Menge an positiven Wahrscheinlichkeiten, für die gilt:

${\begin{aligned}\epsilon _{i}\gg 0\end{aligned}}$ und $\sum \nolimits _{j=1}^{n_{i}}\epsilon _{i}^{j}<1$.

Die Menge an gemischten Strategien im perturbierten Spiel ist also:

${\begin{aligned}M_{i}^{\epsilon }=(m_{i}\in {M_{i}}|m_{i}^{k}\geq \epsilon _{i}^{k})\end{aligned}}$, für ${\begin{aligned}k=(1...n_{i})\end{aligned}}$.

Das heißt, dass Spieler ${\begin{aligned}i\end{aligned}}$, ${\begin{aligned}(i\in I)\end{aligned}}$, jede seiner reinen Strategien der Anzahl ${\begin{aligned}k\end{aligned}}$, mindestens mit der Wahrscheinlichkeit ${\begin{aligned}\epsilon _{i}^{k}\end{aligned}}$ spielen muss. Daraus folgt das perturbierte Spiel:

${\begin{aligned}G(\epsilon )=(I,(M_{i}^{\epsilon }),(P_{i}))\end{aligned}}$, und ${\begin{aligned}(i\in I)\end{aligned}}$

Ein Nash-Gleichgewicht im perturbierten Spiel sei ${\begin{aligned}m^{*}(\epsilon )\end{aligned}}$ und ein Nash-Gleichgewicht im Ausgangsspiel sei: ${\begin{aligned}m^{*}\end{aligned}}$. Wenn man die Fehlerwahrscheinlichkeit ${\begin{aligned}\epsilon \end{aligned}}$ im perturbierten Spiel gegen null gehen lässt und dadurch das Gleichgewicht des perturbierten Spiels zum Gleichen wird wie im normalen Spiel, spricht man von einem trembling-hand-perfekten Gleichgewicht. Formal ausgedrückt heißt das, wenn

${\begin{aligned}\lim _{\epsilon \to 0}m^{*}(\epsilon )=m^{*}\end{aligned}}$,

handelt es sich um ein trembling-hand-perfektes Gleichgewicht.

Beispiel

Als Ausgangsspiel wird ein Normalformspiel mit folgender Auszahlungsmatrix betrachtet:

Spieler A/Spieler B	(${\begin{aligned}b_{1}\end{aligned}}$)	(${\begin{aligned}b_{2}\end{aligned}}$)
(${\begin{aligned}a_{1}\end{aligned}}$)	(3, 3)	(0, 0)
(${\begin{aligned}a_{2}\end{aligned}}$)	(0, 0)	(0, 0)

Im normalen Spiel gibt es zwei Nash-Gleichgewichte, die sich aus den Strategiekombinationen ${\begin{aligned}(a_{1}/b_{1})\end{aligned}}$ und ${\begin{aligned}(a_{2}/b_{2})\end{aligned}}$ ergeben. Es kommt für die beiden Spieler bei der Wahl ihrer jeweils besten Antwort darauf an, welche Strategie der jeweilige Gegenspieler wählt.

Im perturbierten Spiel ist dies nicht der Fall. Denn wenn es auch nur eine winzige Wahrscheinlichkeit gibt, dass Spieler B seine Strategie ${\begin{aligned}b_{1}\end{aligned}}$ wählt, dann ist die beste Antwort von Spieler A darauf ${\begin{aligned}a_{1}=1\end{aligned}}$ zu spielen. Da diese Wahrscheinlichkeit im perturbierten Spiel per Definition existiert, würde Spieler A immer ${\begin{aligned}a_{1}=1\end{aligned}}$ spielen. Aber auch Spieler A muss im perturbierten Spiel seine Strategie ${\begin{aligned}a_{2}\end{aligned}}$ mit einer positiven Wahrscheinlichkeit spielen. Deshalb ist seine beste Antwort, die gemischte Strategie ${\begin{aligned}a_{2}=a_{2}^{min}\end{aligned}}$zu spielen – also die kleinstmögliche Wahrscheinlichkeit für ${\begin{aligned}a_{2}\end{aligned}}$.

Aufgrund der Symmetrie des Spiels ist die beste Strategie für Spieler B dementsprechend: ${\begin{aligned}b_{2}=b_{2}^{min}\end{aligned}}$

Das Gleichgewicht im perturbierten Spiel ist also:

${\begin{aligned}(1-a_{2}^{min},a_{2}^{min}),(1-b_{2}^{min},b_{2}^{min})\end{aligned}}$

Wenn man jetzt ${\begin{aligned}a_{2}^{min}\end{aligned}}$ und ${\begin{aligned}b_{2}^{min}\end{aligned}}$ gegen ${\begin{aligned}0\end{aligned}}$ gehen lässt, dann wird aus dem perturbierten Spiel fast wieder das Normale, denn:

$\lim _{a_{2}^{min},b_{2}^{min}\to 0}[(1-a_{2}^{min},a_{2}^{min}),(1-b_{2}^{min},b_{2}^{min})]=[(1,0),(1,0)]=(a_{1},b_{1})$

Wenn man die Fehlerwahrscheinlichkeit gegen Null gehen lässt und sich das Gleichgewicht des perturbierten Spiels dadurch auf ein Nash-Gleichgewicht des zugrundeliegenden Spiels zubewegt, dann handelt es sich bei diesem Gleichgewicht um ein Trembling-hand-perfektes.

In diesem Beispiel bewegt sich das perturbierte Spiel gegen das Gleichgewicht ${\begin{aligned}(a_{1}/b_{1})\end{aligned}}$ und ist somit Trembling-hand-perfekt.

${\begin{aligned}(1-a_{2}^{min},a_{2}^{min}),(1-b_{2}^{min},b_{2}^{min})\end{aligned}}$

Trembling-hand-perfektes Gleichgewicht in Sequentiellen Spielen

Auch für Sequentielle Spiele ist das Konzept des Trembling-hand-perfekten Gleichgewichtes anwendbar. Ähnlich wie bei den Normalformspielen, ist es hierbei für die Selektion von Teilspielperfekten Gleichgewichten von Nutzen, um festzustellen, ob ein solches Gleichgewicht auch bei einer geringen Fehlerwahrscheinlichkeit bestehen bleibt.

Beispiel

Spielbaum eines Extensivformspiels zweier Spieler

Im auf der rechten Seite gibt es vier Teilspielperfekte Gleichgewichte:

${\begin{aligned}(A,(X|A,X|B))\end{aligned}}$, also Spieler 1 spielt seine Strategie ${\begin{aligned}A\end{aligned}}$ und Spieler 2 spielt ${\begin{aligned}X\end{aligned}}$, für den Fall, dass Spieler 1 ${\begin{aligned}A\end{aligned}}$ gewählt hat und auch ${\begin{aligned}X\end{aligned}}$ für den Fall, dass Spieler 1 ${\begin{aligned}B\end{aligned}}$ gewählt hat. ${\begin{aligned}(A,(Y|A,X|B)),(B,(X|A,X|B)),(B,(Y|A,X|B))\end{aligned}}$ sind die anderen drei Teilspielperfekten Gleichgewichte.

Allerdings sind nur die beiden Gleichgewichte, in denen Spieler 1 seine Strategie ${\begin{aligned}A\end{aligned}}$ wählt Trembling-hand-perfekt. Denn auch wenn es nur eine winzige Wahrscheinlichkeit gibt, dass Spieler 2 seine Strategie ${\begin{aligned}Y\end{aligned}}$ spielt, ist es für Spieler 1 besser immer ${\begin{aligned}A\end{aligned}}$ zu spielen, da er hier immer eine Auszahlung von 2 bekommt und er sich durch die Strategie ${\begin{aligned}B\end{aligned}}$ nie besser stellen kann, als durch die Strategie ${\begin{aligned}A\end{aligned}}$.

Die beiden Trembling-hand-perfekten Gleichgewichte sind also: ${\begin{aligned}(A,(X|A,X|B)),(A,(Y|A,X|B))\end{aligned}}$.

Trembling-hand-perfektes Gleichgewicht in extensiven Spielen mit der Agentennormalform

Elon Kohlbergs Dalekspiel in extensiver Form

Das vom Spieltheoretiker Elon Kohlberg entwickelte, und hier leicht abgewandelte Dalekspiel, ist ein Beispiel für eine weitere Anwendung des Trembling-hand-perfekten Gleichgewichtes. Die 1953 von Harold W. Kuhn entwickelte Agentennormalform wird angewendet, um den Informationsverlust bei einer Reduktion eines Extensivspiels auf die Normalform, auszugleichen. Wie im Dalekspiel auf der rechten Seite zu sehen, wird Spieler 1 in zwei Agenten aufgeteilt, um an jedem Entscheidungsknoten unkorrelierte Entscheidungen mathematisch abbilden zu können.

Spieler 1/Spieler 2	(L)	(R)
(gl)	(2, 5)	(2, 5)
(gr)	(2, 5)	(2, 5)
(ul)	(4, 1)	(0, 0)
(ur)	(0, 0)	(1, 4)

In der Normalform kann man sehr leicht erkennen, dass es drei Nash-Gleichgewichte in reinen Strategien gibt: ${\begin{aligned}(gl,R),(gr,R),(ul,L)\end{aligned}}$ . Um diese Gleichgewichte nun auf ihre Trembling-hand-Perfektheit zu untersuchen, muss man sicherstellen, dass die Fehlerwahrscheinlichkeiten, die Spieler 1 an seinen beiden Entscheidungsknoten hat, nicht miteinander korrelieren. Das heißt, dass ein Fehler am ersten Entscheidungsknoten nicht dazu führen darf, dass die Wahrscheinlichkeit für einen weiteren Fehler steigt oder sinkt. Um dies sicherzustellen, wird Spieler 1 wie bereits oben beschrieben in zwei Agenten aufgeteilt, die unabhängig voneinander ihre Entscheidungen treffen.

Nun nehmen wir an, dass der erste Agent (Sp1A) mit einer geringen Wahrscheinlichkeit von $\epsilon$ einen Fehler begeht und ${\begin{aligned}u\end{aligned}}$ anstatt von ${\begin{aligned}g\end{aligned}}$ spielt.

Dementsprechend begeht der zweite Agent (Sp1B) mit der Wahrscheinlichkeit von ${\begin{aligned}\delta \end{aligned}}$ einen Fehler und spielt ${\begin{aligned}l\end{aligned}}$ anstatt von ${\begin{aligned}r\end{aligned}}$.

Spieler 2 begeht schließlich mit einer Wahrscheinlichkeit von ${\begin{aligned}\lambda \end{aligned}}$ einen Fehler und spielt ${\begin{aligned}L\end{aligned}}$ anstatt von ${\begin{aligned}R\end{aligned}}$.

Mit den Eingetragenen Wahrscheinlichkeiten sieht die Normalform von oben wie folgt aus:

Spieler 1/Spieler 2	(L)	(R)	Wahrscheinlichkeit
(gl)	(2, 5)	(2, 5)	$(1-\epsilon )\cdot \delta$
(gr)	(2, 5)	(2, 5)	$(1-\epsilon )\cdot (1-\delta )$
(ul)	(4, 1)	(0, 0)	$\epsilon \cdot \delta$
(ur)	(0, 0)	(1, 4)	$\epsilon \cdot (1-\delta )$
Wahrscheinlichkeit	${\begin{aligned}\lambda \end{aligned}}$	${\begin{aligned}(1-\lambda )\end{aligned}}$

Nun kann man leicht erkennen, dass die Strategien ${\begin{aligned}(gr)\end{aligned}}$ und ${\begin{aligned}(gl)\end{aligned}}$ für Spieler 1 für kleine ${\begin{aligned}\lambda \end{aligned}}$ Trembling-hand-perfekte Strategien sind. Denn er erhält eine sichere Auszahlung von 2 egal wie sich Spieler 2 entscheidet. Bei der einzigen besseren Auszahlung von 4 bei der Wahl von ${\begin{aligned}(ul)\end{aligned}}$ erhält er aufgrund der Wahrscheinlichkeiten im Erwartungswert die Auszahlung:

${\begin{aligned}\mathrm {E} [u(ul)]=(1-\lambda )\cdot 0+(\lambda )\cdot 4\end{aligned}}$ und für ${\begin{aligned}\lambda >0,5\end{aligned}}$ ist dieser Erwartungswert schlechter als bei ${\begin{aligned}(gr)\end{aligned}}$ und ${\begin{aligned}(gl)\end{aligned}}$.

Auch für Spieler 2 ist die Strategie ${\begin{aligned}(R)\end{aligned}}$ Trembling-hand-perfekt, weil die einzige Strategiekombination, bei der Spieler 2 eine größere Auszahlung für ${\begin{aligned}(L)\end{aligned}}$ als für ${\begin{aligned}(R)\end{aligned}}$ bekommt ist ${\begin{aligned}(ul,L)\end{aligned}}$ im Gegensatz zu ${\begin{aligned}(ul,R)\end{aligned}}$. Da ${\begin{aligned}(ul)\end{aligned}}$ aber nur eintritt, wenn beide Agenten von Spieler 1 einen Fehler machen, hat ${\begin{aligned}(ul)\end{aligned}}$ die geringste Wahrscheinlichkeit ($\epsilon \cdot \delta$).

Damit sind die beiden Gleichgewichte ${\begin{aligned}(gr,R)\end{aligned}}$ und ${\begin{aligned}(gl,R)\end{aligned}}$ Trembling-hand-perfekt. Das Gleichgewicht ${\begin{aligned}(ul,L)\end{aligned}}$ ist es nicht, weil die Strategie ${\begin{aligned}(ul)\end{aligned}}$, wie gerade gezeigt keine Trembling-hand-perfekte Strategie ist.

Literatur

• Reinhard Selten: A reexamination of the perfectness concept for equilibrium points in extensive games, in: International Journal of Game Theorie. Physica-Verlag, Vienna 1975, S. 25–55. 
• Harold William Kuhn: Extensive Games and the Problem of Informations. In: Contribution to the Theorie of Games. Vol. 2. Princeton Univ. Press, Princeton 1953, S. 193–216. 
• Elon Kohlberg, Jean-Francois Mertens: On the Strategic Stability of Equilibria. Econometrica, 1986, S. 1003–1037. 
• Robert Gibbons: A Primer in Game Theory. Financial Times, Harlow 1992. 
• Thomas Riechmann: Spieltheorie. 3. Auflage. Vahlen, München 2010. 
• Christian Rieck: Spieltheorie. 8. Auflage. Rieck, Eschborn 2008. 
• Alexander Mehlmann: Strategische Spiele für Einsteiger. Friedr. Vieweg & Sohn Verlag, Wiesbaden 2007. 
• Ken Binmore: Fun and Games. 1. Auflage. Heath, Lexington 1992. 
• Jürgen Eichberger: Game Theorie for Economists. 1. Auflage. Emerald, Bingley 2007. 

Weblinks

• Projekt der Uni München, als Enzyklopädie zur Spieltheorie