Kalai-Smorodinsky-Lösung

Die Kalai-Smorodinsky-Lösung ist eine kooperative Verhandlungslösung die 1975 von Ehud Kalai und Meir Smorodinsky vorgestellt wurde. Die Verhandlungstheorie (engl. bargaining problem) ist ein Teilgebiet der kooperativen Spieltheorie, in der Teilnehmer Absprachen treffen dürfen, um ihren eigenen Nutzen zu maximieren.

Infolge der kritischen Diskussion der Eigenschaft der Unabhängigkeit von irrelevanten Alternativen der älteren Nash-Lösung (siehe unten) entwickelten Kalai und Smorodinsky ein alternatives Lösungskonzept, das auf Monotonie-Eigenschaften zurückgreift. Daher wird die Kalai-Smorodinsky-Lösung auch manchmal nur die monotone Verhandlungslösung genannt.

Einführung

Pareto-Optimalität

Symmetrie

Die Punkte aus $\tilde{B}\setminus B$ sind irrelevante Alternativen

Unter einer Verhandlungssituation versteht man ein Paar $(B,d)$ mit folgenden Eigenschaften:

• $B\subset {ℝ}^2$ konvex und kompakt,
• $d\in B$,
• für alle $x\in B$ gilt komponentenweise $d\le x$,
• es gibt ein $(x_1,x_2)\in B$ mit $d_1<x_1$ und $d_2<x_2$.

Die dem zugrunde liegende Vorstellung ist, dass zwei Akteure (Spieler) sich durch Verhandlungen auf einen Punkt $(b_1,b_2)\in B$ einigen können, die erste Komponente $b_1$, etwa ein Geldbetrag dieser Höhe, geht an Spieler 1, die zweite Komponente $b_2$ fällt Spieler 2 zu. Kommt es zu keiner Einigung, so kommt der Punkt $d$ zur Auszahlung, das heißt Spieler $i$ erhält $d_i$. Diese Auszahlungen an die Spieler sollten allgemeiner als Nutzen verstanden werden. Die letzte der oben genannten vier Eigenschaften sagt aus, dass es für jeden Spieler etwas zu verhandeln gibt, das heißt jeder Spieler könnte bei geeigneter Einigung eine über dem Status quo $d_i$ liegende Auszahlung erhalten. Eine Verhandlungslösung ist eine Abbildung $\phi$, die jeder Verhandlungssituation $(B,d)$ einen Punkt $\phi (B,d)\in B$ zuordnet, der als Verhandlungsergebnis akzeptiert wird. Um hier zu sinnvollen Abbildungen zu kommen, wird man gewisse, natürliche Forderungen an eine solche Abbildung stellen, die eine Akzeptanz plausibel machen.

So sollte es keinen Punkt $x\in B$ mit $\phi (B,d)<x$ komponentenweise geben, denn anderenfalls könnten sich beide Akteure bei Einigung auf $x$ an Stelle von $\phi (B,d)$ nur verbessern. Dies ist die Forderung nach Pareto-Optimalität. Ist die Verhandlungssituation symmetrisch bzgl. der Diagonalen durch den ersten Quadranten, so wird man das auch von der Lösung verlangen, denn bei Austausch der Spieler finden beide wieder genau dieselbe Verhandlungssituation vor. Man spricht von Unabhängigkeit gegenüber positiven, linearen Transformationen, wenn für jede Abbildung $T:{ℝ}^2\to {ℝ}^2,T(x_1,x_2)=(a_1{x}_1+b_1,a_2{x}_2+b_2)$ mit $a_1>0,a_2>0$ und jede Verhandlungssituation $(B,d)$ stets $\phi (T(d),T(B))=T(\phi (B,d))$ gilt, das heißt, dass eine Skalenveränderung der Verhandlungssituation die Lösung in gleichem Maße verändert.

Eine Verhandlungslösung heißt unabhängig von irrelevanten Alternativen, falls für je zwei Verhandlungssituationen $(B,d),(\tilde{B},d)$ mit $\phi (\tilde{B},d)\in B\subset \tilde{B}$ stets $\phi (\tilde{B},d)=\phi (B,d)$ gilt, das heißt, wenn sich die Verhandlungslösung, die in der größeren Menge gefunden wurde, auch in der kleineren Menge noch Gültigkeit hat, solange sie in der kleineren noch enthalten ist. John Nash hatte 1950 gezeigt, dass es genau eine Verhandlungslösung ${\phi }_N$ gibt, die Pareto-optimal, symmetrisch, unabhängig von positiven linearen Transformationen und unabhängig von irrelevanten Alternativen ist. Diese nennt man die Nash'sche Verhandlungslösung.

Kritik der Nash'schen Verhandlungslösung

Irrelevante Alternativen

Die Forderung nach Unabhängigkeit irrelevanter Alternativen ist im unten angegebenen Lehrbuch von Duncan Luce und Howard Raiffa kritisiert worden. Dort wird die Verhandlungssituationen $(B_1,0)$ und $(B_2,0)$ betrachtet, wobei $B_1$ das durch die Punkte $(0,0),(10,0),(0,100)$ bestimmte Dreieck ist und $B_2$ aus $B_1$ dadurch Abschneiden auf Höhe 50 entsteht. Die Nash'sche Verhandlungslösung liefert ${\phi }_N(B_1,0)=(5,50)$ und nach der Unabhängigkeit von irrelevanten Alternativen muss das auch die Lösung für $(B_2,0)$ sein. Die Lösung in der ersten Verhandlungssituation scheint fair, denn jeder Spieler erhält die Hälfte von dem, was maximal überhaupt für ihn möglich wäre. In der zweiten Verhandlungssituation gilt das nicht mehr, hier erhält Spieler 2 den maximal für ihn möglichen Betrag, während sich Spieler 1 mit der Hälfte zufriedengeben muss. Ein weiterer psychologischer Einwand gegen die Unabhängigkeit von irrelevanten Alternativen entsteht, wenn man sich vorstellt, die Akteure hätten sich zunächst zu einem Verhandlungsergebnis in der Situation $(B_2,0)$ durchringen können und erführen dann, dass es aber eigentlich um die Verhandlungssituation $(B_1,0)$ ginge. Spieler 2 könnte nun der Meinung sein, dass für ihn ja prinzipiell größere Beträge verhandelbar gewesen wären, und nachverhandeln wollen, das heißt, er würde die hinzugekommenen Alternativen als für ihn vorteilhaft sehen und deren Irrelevanz nicht akzeptieren.

Monotonie und die Kalai-Smorodinsky-Lösung

In der größeren Verhandlungsmenge verbessert sich die Situation für beide Spieler.

Auf die oben genannte Kritik verweisen auch Ehud Kalai und Meir Smorodinsky in ihrer Originalarbeit aus dem Jahre 1975 und stellen eine alternative Verhandlungslösung vor. Statt der Unabhängigkeit von irrelevanten Alternativen wird die ebenfalls natürliche Forderung nach Monotonie gestellt, die von der Nash'schen Verhandlungslösung nicht erfüllt wird. Für eine Verhandlungssituation $(B,d)$ sei $m_i(B):=\sup \{x_i;(x_1,x_2)\in B\}$ die maximale Auszahlung, die für den i-ten Spieler überhaupt möglich wäre. Eine Verhandlungslösung $\phi$ heißt monoton, falls für Verhandlungssituationen $(B,0)$ und $(\tilde{B},0)$ mit $m_i(B)=m_i(\tilde{B})=1$ für i=1,2 und $B\subset \tilde{B}$ stets komponentenweise $\phi (B,0)\le \phi (\tilde{B},0)$ gilt.

Wenn sich also beide Spieler nur den Betrag 0 sichern können und beide maximal die Auszahlung 1 erzielen können, so sollte sich die Situation für jeden Spieler nur verbessern, wenn man unter Beibehaltung dieser Bedingungen von einer kleineren Verhandlungsmenge zu einer größeren übergeht, denn das in der kleineren Menge erzielbare Verhandlungsergebnis kann man in der größeren ja auch aushandeln, möglicherweise aber sogar mehr. Man beachte, dass durch die Zahlen 0 und 1 hier eine Normierung der Situation vorliegt, dazu mehr in den unten folgenden Beispielen.

Kalai und Smorodinsky haben nun gezeigt, dass es genau eine Verhandlungslösung ${\phi }_m$ gibt, die Pareto-optimal, symmetrisch, unabhängig von positiven, linearen Transformationen und monoton ist. Das ist die sogenannte monotone Verhandlungslösung oder Kalai-Smorodinsky-Lösung.

Ermittlung der monotonen Verhandlungslösung

Zur Ermittlung der monotonen Verhandlungslösung bestimmt man zu einer gegebenen Verhandlungssituation $(B,d)$ eine positive, lineare Transformation T, so dass $T(d)=0$ und $m_1(T(B))=m_2(T(B))=1$. Auf der Geraden $\{(x,x);x\in ℝ\}$ gibt es einen bzgl. der komponentenweisen Ordnung größten Punkt $(x^{*},x^{*})\in T(B)$. Das gesuchte monotone Verhandlungsergebnis ist dann ${\phi }_m(B,d)=T^{-1}(x^{*},x^{*})$.

Alternativ konstruiert man das Rechteck kleinsten Flächeninhalts, das $B$ umfasst. Die von unten links nach oben rechts verlaufende Diagonale hat einen in $B$ liegenden Punkt $(x_1^{*},x_2^{*})$ mit maximalen Komponenten. Dieser Punkt ist die monotone Verhandlungslösung. Dieses Verfahren wird in den Beispielen unten ausgeführt.

Eine ähnliche geometrische Sichtweise ergibt die Nash'sche Verhandlungslösung. Man bestimme zu $B$ zunächst

$\bar{B}:=\{x\in {ℝ}^2|d\le x\text{ und }x\le b\text{ für ein }b\in B\}$,

das heißt man nimmt alle oberhalb des Status quo liegenden Punkte hinzu, die komponentenweise von mindestens einem Punkt aus $B$ dominiert werden. Die Nash'sche Lösung ist die obere rechte Ecke eines in $\bar{B}$ enthaltenen Rechtecks maximalen Flächeninhalts.

Beispiele

Konstruktion der Lösungen

Armer Mann und reicher Mann

Zur Verdeutlichung der Lösungskonzepte betrachten wir das Beispiel vom armen und reichen Mann. Es geht um die Aufteilung von 100 Geldeinheiten bei Einigung, anderenfalls gibt es nichts. Der ärmere Spieler, der selbst nur 100 besitze, betrachtet als seinen Nutzen einer verhandelten Auszahlung $x$ die relative Änderung seines Vermögens, das heißt der Nutzen wird als (proportional zum) Logarithmus des Betrages angenommen, genauer interessiert er sich für $\log (1+\frac{x}{100})$. Beim reichen Mann fällt der relative Zuwachs nicht ins Gewicht, hier nehmen wir die Auszahlung selbst als Nutzen an. Bei unterstellter Nutzenmaximierung haben wir als zu verhandelnden Bereich $B$ die von der Kurve $y=\log (2-\frac{x}{100})$ und den Achsen eingeschlossene Fläche. Der Garantiepunkt ist $d=0$.

Dieser Bereich $B$ stimmt bereits mit dem erweiterten Bereich $\bar{B}$ überein. Das darin enthaltene Rechteck maximalen Flächeninhaltes hat eine Fläche von $x\cdot y=x\cdot \log (2-\frac{x}{100})$. Maximierung dieses Ausdruck liefert näherungsweise $x^{*}=54,46$ und damit $y^{*}=45,54$ als Nash'sche Verhandlungslösung, das heißt ${\phi }_N(B,0)\approx (54,46;45,54)$.

Zur Ermittlung der Kalai-Smorodinsky-Lösung betrachten wir das kleinste $\bar{B}$ umfassende Rechteck, welches offenbar $(100,\log 2)$ als obere rechte Ecke hat, die Diagonale genügt dann der Gleichung $y=\frac{\log 2}{100}x$ und die gesuchte Lösung $(x^{*},y^{*})$ ist derjenige Punkte auf dieser Diagonalen, der die Begrenzungslinie $y=\log (2-\frac{x}{100})$ schneidet. Das führt zur Gleichung $\frac{\log 2}{100}x=\log (2-\frac{x}{100})$, für die man näherungsweise die Lösung $x^{*}=54,30$ und damit $y^{*}=45,70$ als Kalai-Smorodinsky-Lösung erhält, das heißt ${\phi }_m(B,0)\approx (54,30;45,70)$.

Beide Lösungskonzepte führen also trotz unterschiedlicher Ansätze auf ähnliche Lösungen. Beide Lösungen zeigen, dass der Ärmere in der Verhandlung unterlegen ist, denn der Reiche, der nicht so sehr auf das Geld angewiesen ist, hat eine stärkere Verhandlungsposition. Das wurde hier durch die unterschiedlichen Nutzenfunktionen der beteiligten Spieler modelliert.

Konstruktion der Lösung

Die Beispiele aus obiger Kritik

Wir betrachten die Beispiele $(B_1,0)$ und $(B_2,0)$ aus obiger Kritik. Im ersten Beispiel stimmen beide Lösungskonzepte überein, das heißt es ist ${\phi }_N(B_1,0)={\phi }_m(B_2,0)=(5,50)$, denn dieses Beispiel lässt sich durch Streckung der ersten Komponente mit dem Faktor 10 in eine symmetrische Verhandlungssituation überführen und beide Lösungskonzepte erfüllen die Forderung nach Symmetrie. Beim zweiten Beispiel sieht das anders aus. Es ist ${\phi }_N(B_1,0)=(5,50)$, da die Nash'sche Verhandlungslösung unabhängig von irrelevanten Alternativen ist. Zur Ermittlung der Kalai-Smorodinsky-Lösung konstruiere man die Diagonale im kleinsten $B_2$ umfassenden Rechteck und ermittle den Schnittpunkt mit der Berandung des Bereichs, das ist der Schnittpunkt der Geraden $y=5x$ (Diagonale) und $y=100-10x$ (Berandung), und nach kurzer Rechnung erhält man ${\phi }_m(B_2,0)=(6\frac{2}{3};33\frac{1}{3})$.

Monotonie

In der Monotonie-Forderung, die der Kalai-Smorodinsky-Lösung zugrunde liegt, sind der Garantiepunkt und die maximalen Nutzen auf 0 bzw. 1 normiert. Es stellt sich daher die Frage, ob auch eine davon unabhängige Monotonie erfüllt ist, das heißt, ob für Verhandlungssituationen $(B,d)$ und $(\tilde{B},d)$ mit $B\subset \tilde{B}$ stets komponentenweise ${\phi }_m(B,d)\le {\phi }_m(\tilde{B},d)$ gilt. Man kann zeigen, dass Forderung so stark ist, dass es keine Verhandlungslösung gibt, die Pareto-optimal, symmetrisch, unabhängig von positiven, linearen Transformationen und stark monoton in diesem Sinne ist.

Konstruktion der Lösung

Wir betrachten ein konkretes Beispiel, dass die Verletzung dieser starken Monotonieforderung verletzt. Der Garantiepunkt ist in beiden Fällen der Koordinatenursprung.

$B:=\{(x,y)|4x+7y\le 7\text{ und }4x+y\le 4\}$,

$\tilde{B}:=\{(x,y)|4x+7y\le 7\}$.

Da $\tilde{B}$ durch Fortlassen einer Bedingung aus $B$ hervorgeht, muss $B\subset \tilde{B}$ sein. Die Mengen sind durch die Koordinatenachsen und die Geraden $y=1-\frac{4}{7}x$ bzw. $y=4-4x$ begrenzt.

Die Kalai-Smorodinsky-Lösung der Verhandlungssituation $(B,0)$ liegt auf der Geraden $y=x$ und der Berandung von $B$, ist also der Schnittpunkt der Geraden $y=x$ und $y=1-\frac{4}{7}x$, das heißt für $x$ gilt $x=y=1-\frac{4}{7}x$ und daher $x=\frac{7}{11}$, insgesamt also ${\phi }_m(B,0)=(\frac{7}{11};\frac{7}{11})$.

Der Lösungspunkt von $(\tilde{B},0)$ ist entsprechend der Schnittpunkt der Geraden $y=\frac{4}{7}x$ und $y=1-\frac{4}{7}x$, woraus sich sofort ${\phi }_m(\tilde{B},0)=(\frac{7}{8},\frac{1}{2})$ ergibt.

Die starke Monotonieforderung hätte zur Folge, dass ${\phi }_m(B,0)$ komponentenweise unterhalb von ${\phi }_m(\tilde{B},0)$ läge, was aber wegen $\frac{7}{11}>\frac{1}{2}$ nicht der Fall ist. Es liegt natürlich keine Verstoß gegen die Monotonie-Eigenschaft der Kalai-Smorodinsky-Lösung vor, denn der Nutzen des ersten Spielers in $(\tilde{B},0)$ ist nicht auf 1 normiert.

Literatur

• Berninghaus, S. K., K. M. Erhart, and W. Güth. "Strategische Spiele: Eine Einführung in die Spieltheorie, 2., überarb. und erw." Aufl., Berlin ua O (2010). Kapitel 4.1.2.