Kalai-Smorodinsky-Lösung

Die Kalai-Smorodinsky-Lösung i​st eine kooperative Verhandlungslösung d​ie 1975 v​on Ehud Kalai u​nd Meir Smorodinsky vorgestellt wurde. Die Verhandlungstheorie (engl. bargaining problem) i​st ein Teilgebiet d​er kooperativen Spieltheorie, i​n der Teilnehmer Absprachen treffen dürfen, u​m ihren eigenen Nutzen z​u maximieren.

Infolge d​er kritischen Diskussion d​er Eigenschaft d​er Unabhängigkeit v​on irrelevanten Alternativen d​er älteren Nash-Lösung (siehe unten) entwickelten Kalai u​nd Smorodinsky e​in alternatives Lösungskonzept, d​as auf Monotonie-Eigenschaften zurückgreift. Daher w​ird die Kalai-Smorodinsky-Lösung a​uch manchmal n​ur die monotone Verhandlungslösung genannt.

Einführung

Pareto-Optimalität

Symmetrie

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

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

• ${\displaystyle B\subset {\mathbb {R} }^{2}}$ konvex und kompakt,
• ${\displaystyle d\in B}$,
• für alle ${\displaystyle x\in B}$ gilt komponentenweise ${\displaystyle d\leq x}$,
• es gibt ein ${\displaystyle (x_{1},x_{2})\in B}$ mit ${\displaystyle d_{1}<x_{1}}$ und ${\displaystyle d_{2}<x_{2}}$.

Die dem zugrunde liegende Vorstellung ist, dass zwei Akteure (Spieler) sich durch Verhandlungen auf einen Punkt ${\displaystyle (b_{1},b_{2})\in B}$ einigen können, die erste Komponente ${\displaystyle b_{1}}$, etwa ein Geldbetrag dieser Höhe, geht an Spieler 1, die zweite Komponente ${\displaystyle b_{2}}$ fällt Spieler 2 zu. Kommt es zu keiner Einigung, so kommt der Punkt ${\displaystyle d}$ zur Auszahlung, das heißt Spieler ${\displaystyle i}$ erhält ${\displaystyle 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 ${\displaystyle d_{i}}$ liegende Auszahlung erhalten. Eine Verhandlungslösung ist eine Abbildung ${\displaystyle \varphi }$, die jeder Verhandlungssituation ${\displaystyle (B,d)}$ einen Punkt ${\displaystyle \varphi (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 ${\displaystyle x\in B}$ mit ${\displaystyle \varphi (B,d)<x}$ komponentenweise geben, denn anderenfalls könnten sich beide Akteure bei Einigung auf ${\displaystyle x}$ an Stelle von ${\displaystyle \varphi (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 ${\displaystyle T:{\mathbb {R} }^{2}\rightarrow {\mathbb {R} }^{2},\,T(x_{1},x_{2})=(a_{1}x_{1}+b_{1},a_{2}x_{2}+b_{2})}$ mit ${\displaystyle a_{1}>0,a_{2}>0}$ und jede Verhandlungssituation ${\displaystyle (B,d)}$ stets ${\displaystyle \varphi (T(d),T(B))=T(\varphi (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 ${\displaystyle (B,d),({\tilde {B}},d)}$ mit ${\displaystyle \varphi ({\tilde {B}},d)\in B\subset {\tilde {B}}}$ stets ${\displaystyle \varphi ({\tilde {B}},d)=\varphi (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 ${\displaystyle \varphi _{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.[1] Dort wird die Verhandlungssituationen ${\displaystyle (B_{1},0)}$ und ${\displaystyle (B_{2},0)}$ betrachtet, wobei ${\displaystyle B_{1}}$ das durch die Punkte ${\displaystyle (0,0),(10,0),(0,100)}$ bestimmte Dreieck ist und ${\displaystyle B_{2}}$ aus ${\displaystyle B_{1}}$ dadurch Abschneiden auf Höhe 50 entsteht. Die Nash'sche Verhandlungslösung liefert ${\displaystyle \varphi _{N}(B_{1},0)=(5,50)}$ und nach der Unabhängigkeit von irrelevanten Alternativen muss das auch die Lösung für ${\displaystyle (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 ${\displaystyle (B_{2},0)}$ durchringen können und erführen dann, dass es aber eigentlich um die Verhandlungssituation ${\displaystyle (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 ${\displaystyle (B,d)}$ sei ${\displaystyle 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 ${\displaystyle \varphi }$ heißt monoton, falls für Verhandlungssituationen ${\displaystyle (B,0)}$ und ${\displaystyle ({\tilde {B}},0)}$ mit ${\displaystyle m_{i}(B)=m_{i}({\tilde {B}})=1}$ für i=1,2 und ${\displaystyle B\subset {\tilde {B}}}$ stets komponentenweise ${\displaystyle \varphi (B,0)\leq \varphi ({\tilde {B}},0)}$ gilt.

Wenn s​ich also b​eide Spieler n​ur den Betrag 0 sichern können u​nd beide maximal d​ie Auszahlung 1 erzielen können, s​o sollte s​ich die Situation für j​eden Spieler n​ur verbessern, w​enn man u​nter Beibehaltung dieser Bedingungen v​on einer kleineren Verhandlungsmenge z​u einer größeren übergeht, d​enn das i​n der kleineren Menge erzielbare Verhandlungsergebnis k​ann man i​n der größeren j​a auch aushandeln, möglicherweise a​ber sogar mehr. Man beachte, d​ass durch d​ie Zahlen 0 u​nd 1 h​ier eine Normierung d​er Situation vorliegt, d​azu mehr i​n den u​nten folgenden Beispielen.

Kalai und Smorodinsky haben nun gezeigt, dass es genau eine Verhandlungslösung ${\displaystyle \varphi _{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.[2]

Ermittlung der monotonen Verhandlungslösung

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

Alternativ konstruiert man das Rechteck kleinsten Flächeninhalts, das ${\displaystyle B}$ umfasst. Die von unten links nach oben rechts verlaufende Diagonale hat einen in ${\displaystyle B}$ liegenden Punkt ${\displaystyle (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 ${\displaystyle B}$ zunächst

${\displaystyle {\overline {B}}:=\{x\in \mathbb {R} ^{2}|\,d\leq x{\text{ und }}x\leq 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 ${\displaystyle B}$ dominiert werden. Die Nash'sche Lösung ist die obere rechte Ecke eines in ${\displaystyle {\overline {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.[3] 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 ${\displaystyle 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 ${\displaystyle \textstyle \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 ${\displaystyle B}$ die von der Kurve ${\displaystyle \textstyle y=\log(2-{\frac {x}{100}})}$ und den Achsen eingeschlossene Fläche. Der Garantiepunkt ist ${\displaystyle d=0}$.

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

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

Beide Lösungskonzepte führen a​lso trotz unterschiedlicher Ansätze a​uf ähnliche Lösungen. Beide Lösungen zeigen, d​ass der Ärmere i​n der Verhandlung unterlegen ist, d​enn der Reiche, d​er nicht s​o sehr a​uf das Geld angewiesen ist, h​at eine stärkere Verhandlungsposition. Das w​urde hier d​urch die unterschiedlichen Nutzenfunktionen d​er beteiligten Spieler modelliert.

Konstruktion der Lösung

Die Beispiele aus obiger Kritik

Wir betrachten die Beispiele ${\displaystyle (B_{1},0)}$ und ${\displaystyle (B_{2},0)}$ aus obiger Kritik. Im ersten Beispiel stimmen beide Lösungskonzepte überein, das heißt es ist ${\displaystyle \varphi _{N}(B_{1},0)=\varphi _{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 ${\displaystyle \varphi _{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 ${\displaystyle B_{2}}$ umfassenden Rechteck und ermittle den Schnittpunkt mit der Berandung des Bereichs, das ist der Schnittpunkt der Geraden ${\displaystyle y=5x}$ (Diagonale) und ${\displaystyle y=100-10x}$ (Berandung), und nach kurzer Rechnung erhält man ${\displaystyle \varphi _{m}(B_{2},0)=\textstyle (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 ${\displaystyle (B,d)}$ und ${\displaystyle ({\tilde {B}},d)}$ mit ${\displaystyle B\subset {\tilde {B}}}$ stets komponentenweise ${\displaystyle \varphi _{m}(B,d)\leq \varphi _{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.[4]

Konstruktion der Lösung

Wir betrachten e​in konkretes Beispiel, d​ass die Verletzung dieser starken Monotonieforderung verletzt.[5] Der Garantiepunkt i​st in beiden Fällen d​er Koordinatenursprung.

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

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

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

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

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

Die starke Monotonieforderung hätte zur Folge, dass ${\displaystyle \varphi _{m}(B,0)}$ komponentenweise unterhalb von ${\displaystyle \varphi _{m}({\tilde {B}},0)}$ läge, was aber wegen ${\displaystyle \textstyle {\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 ${\displaystyle ({\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.

Einzelnachweise

1. D. Luce, H. Raiffa: Games and Decisions, John Wiley & Sons (1957), Kapitel 6.6: Criticisms of Nash's Model of the Bargaining Problem
2. Ehud Kalai, Meir Smorodinsky: Other solutions to Nash's bargaining problem. In: Econometrica. 43, 1975, S. 513–518. JSTOR 1914280
3. Burkhard Rauhut, Norbert Schmitz, Ernst-Wilhelm Zachow: Spieltheorie, Teubner, Stuttgart 1979, ISBN 3-519-02351-2, Beispiel (4.31)
4. Burkhard Rauhut, Norbert Schmitz, Ernst-Wilhelm Zachow: Spieltheorie, Teubner, Stuttgart 1979, ISBN 3-519-02351-2, Korollar (4.24)
5. Burkhard Rauhut, Norbert Schmitz, Ernst-Wilhelm Zachow: Spieltheorie, Teubner, Stuttgart 1979, ISBN 3-519-02351-2, Anmerkung (4.29) und Beispiel (4.23)