Kalai-Smorodinsky solution

The Kalai-Smorodinsky solution is a cooperative negotiated solution that was presented in 1975 by Ehud Kalai and Meir Smorodinsky . The Bargaining Theory (Engl. Bargaining problem ) is a branch of cooperative game theory , may meet in the subscriber agreements, to maximize their own benefit.

As a result of the critical discussion of the property of independence from irrelevant alternatives of the older Nash solution (see below), Kalai and Smorodinsky developed an alternative solution concept that makes use of monotonic properties. This is why the Kalai-Smorodinsky solution is sometimes only called the monotonous negotiated solution .

introduction

Pareto optimality

symmetry

The points out are irrelevant alternatives ${\displaystyle {\tilde {B}}\setminus B}$

A negotiation situation is a couple with the following characteristics: ${\displaystyle (B,d)}$

• ${\displaystyle B\subset {\mathbb {R} }^{2}}$ convex and compact,
• ${\displaystyle d\in B}$,
• applies to all components , ${\displaystyle x\in B}$ ${\displaystyle d\leq x}$
• there is a with and . ${\displaystyle (x_{1},x_{2})\in B}$ ${\displaystyle d_{1}<x_{1}}$ ${\displaystyle d_{2}<x_{2}}$

The underlying idea is that two actors (players) can agree on a point through negotiations , the first component , such as an amount of money of this amount, goes to player 1, the second component goes to player 2. If there is no agreement, the point is paid out, i.e. the player receives . These payouts to players should be understood more generally as benefits . The last of the four characteristics mentioned above says that there is something to negotiate for every player, i.e. every player could receive a payout that is above the status quo with a suitable agreement . A negotiated solution is a map that assigns a point to each negotiation situation that is accepted as the result of the negotiation. In order to arrive at meaningful images here, one will make certain, natural demands on such an image that make acceptance plausible. ${\displaystyle (b_{1},b_{2})\in B}$ ${\displaystyle b_{1}}$ ${\displaystyle b_{2}}$ ${\displaystyle d}$ ${\displaystyle i}$ ${\displaystyle d_{i}}$ ${\displaystyle d_{i}}$ ${\displaystyle \varphi }$ ${\displaystyle (B,d)}$ ${\displaystyle \varphi (B,d)\in B}$

So there should be no point with components, because otherwise both actors could improve instead of just by agreeing . This is the requirement for Pareto optimality . If the negotiation situation is symmetrical with regard to the diagonals through the first quadrant, then this will also be required of the solution, because if the players are exchanged, both will find exactly the same negotiation situation again. We speak of independence from positive, linear transformations when the following always applies to every mapping with and every negotiation situation, i.e. a change in the scale of the negotiation situation changes the solution to the same extent. ${\displaystyle x\in B}$ ${\displaystyle \varphi (B,d)<x}$ ${\displaystyle x}$ ${\displaystyle \varphi (B,d)}$ ${\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})}$ ${\displaystyle a_{1}>0,a_{2}>0}$ ${\displaystyle (B,d)}$ ${\displaystyle \varphi (T(d),T(B))=T(\varphi (B,d))}$

A negotiated solution is independent of irrelevant alternatives if for every two negotiation situations with always applies, that is, if the negotiated solution that has been found in the larger amount, even in the smaller amount is still valid, as long as it is contained in the smaller yet . In 1950, John Nash had shown that there is exactly one negotiated solution that is Pareto-optimal, symmetrical, independent of positive linear transformations and independent of irrelevant alternatives. This is called the Nash negotiation solution. ${\displaystyle (B,d),({\tilde {B}},d)}$ ${\displaystyle \varphi ({\tilde {B}},d)\in B\subset {\tilde {B}}}$ ${\displaystyle \varphi ({\tilde {B}},d)=\varphi (B,d)}$ ${\displaystyle \varphi _{N}}$

Critique of Nash's negotiated solution

Irrelevant alternatives

The demand for the independence of irrelevant alternatives has been criticized in the textbook given below by Duncan Luce and Howard Raiffa . There the negotiation situations and are considered, whereby the triangle defined by the dots is created from the cutting off at level 50. Nash's negotiated solution delivers, and after independence from irrelevant alternatives, this must also be the solution for . The solution in the first negotiation situation seems fair, because each player receives half of what would be possible for him at all. In the second negotiation situation this no longer applies, here player 2 receives the maximum amount possible for him, while player 1 has to be satisfied with half. A further psychological objection to independence from irrelevant alternatives arises when one imagines that the actors were able to get through to a negotiation result in the situation and then learn that it is actually about the negotiation situation . Player 2 could now be of the opinion that, in principle, larger amounts would have been negotiable for him and would want to renegotiate, that is, he would see the added alternatives as advantageous for him and not accept their irrelevance. ${\displaystyle (B_{1},0)}$ ${\displaystyle (B_{2},0)}$ ${\displaystyle B_{1}}$ ${\displaystyle (0,0),(10,0),(0,100)}$ ${\displaystyle B_{2}}$ ${\displaystyle B_{1}}$ ${\displaystyle \varphi _{N}(B_{1},0)=(5,50)}$ ${\displaystyle (B_{2},0)}$ ${\displaystyle (B_{2},0)}$ ${\displaystyle (B_{1},0)}$

Monotony and the Kalai-Smorodinsky solution

The situation improves for both players in the larger number of negotiations.

Ehud Kalai and Meir Smorodinsky also refer to the above criticism in their original work from 1975 and present an alternative negotiated solution. Instead of independence from irrelevant alternatives , the likewise natural demand for monotony is made, which Nash's negotiated solution does not meet. For a negotiation situation is the maximum payout that would be possible for the i-th player. A negotiated solution is monotone if for negotiation situations and with and for i = 1,2 always componentwise applies. ${\displaystyle (B,d)}$ ${\displaystyle m_{i}(B):=\sup\{x_{i};(x_{1},x_{2})\in B\}}$ ${\displaystyle \varphi }$ ${\displaystyle (B,0)}$ ${\displaystyle ({\tilde {B}},0)}$ ${\displaystyle m_{i}(B)=m_{i}({\tilde {B}})=1}$ ${\displaystyle B\subset {\tilde {B}}}$ ${\displaystyle \varphi (B,0)\leq \varphi ({\tilde {B}},0)}$

So if both players can only secure the amount 0 and both can achieve a maximum payout of 1, the situation for each player should only improve if one moves from a smaller negotiated amount to a larger one while maintaining these conditions, because that in the Negotiation results that can be achieved in a smaller amount can also be negotiated in the larger amount, but possibly even more. Note that the numbers 0 and 1 normalize the situation here, more on this in the examples below.

Kalai and Smorodinsky have now shown that there is exactly one negotiated solution that is Pareto-optimal, symmetrical, independent of positive, linear transformations, and monotonic. This is the so-called monotonous negotiated solution or Kalai-Smorodinsky solution. ${\displaystyle \varphi _{m}}$

Determination of the monotonous negotiated solution

To determine the monotonous negotiation solution, a positive, linear transformation T is determined for a given negotiation situation, so that and . On the straight line there is a point that is largest in terms of component order . The desired monotonous negotiation result is then . ${\displaystyle (B,d)}$ ${\displaystyle T(d)=0}$ ${\displaystyle m_{1}(T(B))=m_{2}(T(B))=1}$ ${\displaystyle \{(x,x);x\in {\mathbb {R} }\}}$ ${\displaystyle (x^{*},x^{*})\in T(B)}$ ${\displaystyle \varphi _{m}(B,d)=T^{-1}(x^{*},x^{*})}$

Alternatively, one constructs the rectangle with the smallest area that includes. The diagonal running from the bottom left to the top right has a point with maximum components. This point is the monotonous negotiated solution. This procedure is followed in the examples below. ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle (x_{1}^{*},x_{2}^{*})}$

Nash's negotiated solution results in a similar geometrical view. Determine first ${\displaystyle B}$

${\displaystyle {\overline {B}}:=\{x\in \mathbb {R} ^{2}|\,d\leq x{\text{ und }}x\leq b{\text{ für ein }}b\in B\}}$,

that is, you add all points above the status quo that are dominated by components from at least one point . Nash's solution is the upper right corner of a rectangle with the maximum area contained in. ${\displaystyle B}$ ${\displaystyle {\overline {B}}}$

Examples

Construction of the solutions

Poor man and rich man

To illustrate the solution concepts, let us consider the example of the poor and rich man. It is about dividing 100 monetary units in the event of an agreement, otherwise there is nothing. The poorer player, who himself only owns 100, regards the relative change in his wealth as his benefit of a negotiated payout , i.e. the benefit is assumed to be (proportional to) the logarithm of the amount, more precisely he is interested in . In the case of the rich man, the relative increase is irrelevant; here we take the payout itself as a benefit. Assuming utility maximization, the area to be negotiated is the area enclosed by the curve and the axes. The guarantee point is . ${\displaystyle x}$ ${\displaystyle \textstyle \log(1+{\frac {x}{100}})}$ ${\displaystyle B}$ ${\displaystyle \textstyle y=\log(2-{\frac {x}{100}})}$ ${\displaystyle d=0}$

This area already coincides with the extended area . The rectangle of maximum area contained therein has an area of . Maximizing this expression yields approximately and thus as a Nash's negotiated solution, that is . ${\displaystyle B}$ ${\displaystyle {\overline {B}}}$ ${\displaystyle x\cdot y=x\cdot \log(2-{\frac {x}{100}})}$ ${\displaystyle x^{*}=54{,}46}$ ${\displaystyle y^{*}=45{,}54}$ ${\displaystyle \varphi _{N}(B,0)\approx (54{,}46;45{,}54)}$

To determine the Kalai-Smorodinsky solution, we consider the smallest comprehensive rectangle, which apparently has the upper right corner, the diagonal then satisfies the equation and the solution sought is the point on this diagonal that intersects the boundary line . This leads to the equation , for which the solution is obtained approximately and thus as a Kalai-Smorodinsky solution, that is . ${\displaystyle {\overline {B}}}$ ${\displaystyle (100,\log 2)}$ ${\displaystyle \textstyle y={\frac {\log 2}{100}}x}$ ${\displaystyle (x^{*},y^{*})}$ ${\displaystyle \textstyle y=\log(2-{\frac {x}{100}})}$ ${\displaystyle \textstyle {\frac {\log 2}{100}}x=\log(2-{\frac {x}{100}})}$ ${\displaystyle x^{*}=54{,}30}$ ${\displaystyle y^{*}=45{,}70}$ ${\displaystyle \varphi _{m}(B,0)\approx (54{,}30;45{,}70)}$

Both solution concepts therefore lead to similar solutions despite different approaches. Both solutions show that the poorer is inferior in the negotiation, because the rich, who is not so dependent on money, has a stronger negotiating position. This was modeled here through the different utility functions of the players involved.

Construction of the solution

The examples from the above review

We consider the examples and from the above criticism. In the first example, both solution concepts agree, that is, it is because this example can be converted into a symmetrical negotiation situation by stretching the first component by a factor of 10, and both solution concepts meet the requirement for symmetry. The second example looks different. It is because Nash's negotiated solution is independent of irrelevant alternatives. To determine the Kalai-Smorodinsky solution, construct the diagonal in the smallest comprehensive rectangle and determine the point of intersection with the boundary of the area, which is the point of intersection of the straight lines (diagonal) and (boundary), and after a short calculation you get . ${\displaystyle (B_{1},0)}$ ${\displaystyle (B_{2},0)}$ ${\displaystyle \varphi _{N}(B_{1},0)=\varphi _{m}(B_{2},0)=(5{,}50)}$ ${\displaystyle \varphi _{N}(B_{1},0)=(5{,}50)}$ ${\displaystyle B_{2}}$ ${\displaystyle y=5x}$ ${\displaystyle y=100-10x}$ ${\displaystyle \varphi _{m}(B_{2},0)=\textstyle (6{\frac {2}{3}};33{\frac {1}{3}})}$

monotony

In the monotony requirement on which the Kalai-Smorodinsky solution is based, the guarantee point and the maximum benefits are normalized to 0 and 1, respectively. The question therefore arises whether a monotony independent of this is also fulfilled, i.e. whether it always applies to negotiation situations and always with components . One can show that the demand is so strong that there is no negotiated solution that is Pareto-optimal, symmetrical, independent of positive, linear transformations and strongly monotonic in this sense. ${\displaystyle (B,d)}$ ${\displaystyle ({\tilde {B}},d)}$ ${\displaystyle B\subset {\tilde {B}}}$ ${\displaystyle \varphi _{m}(B,d)\leq \varphi _{m}({\tilde {B}},d)}$

Construction of the solution

Let us consider a specific example that violating this strong demand for monotony violates. In both cases, the guarantee point is the origin of the coordinates.

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

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

Since omitting a condition results from , must be. The quantities are limited by the coordinate axes and the straight lines or . ${\displaystyle {\tilde {B}}}$ ${\displaystyle B}$ ${\displaystyle B\subset {\tilde {B}}}$ ${\displaystyle \textstyle y=1-{\frac {4}{7}}x}$ ${\displaystyle y=4-4x}$

The Kalai-Smorodinsky solution of the negotiation situation lies on the straight line and the boundary of , is therefore the intersection of the straight line and , that is, applies to and therefore , overall . ${\displaystyle (B,0)}$ ${\displaystyle y=x}$ ${\displaystyle B}$ ${\displaystyle y=x}$ ${\displaystyle \textstyle y=1-{\frac {4}{7}}x}$ ${\displaystyle x}$ ${\displaystyle \textstyle x=y=1-{\frac {4}{7}}x}$ ${\displaystyle \textstyle x={\frac {7}{11}}}$ ${\displaystyle \varphi _{m}(B,0)=\textstyle ({\frac {7}{11}};{\frac {7}{11}})}$

The solution point of is accordingly the intersection of the straight lines and , which immediately follows. ${\displaystyle ({\tilde {B}},0)}$ ${\displaystyle \textstyle y={\frac {4}{7}}x}$ ${\displaystyle \textstyle y=1-{\frac {4}{7}}x}$ ${\displaystyle \varphi _{m}({\tilde {B}},0)=\textstyle ({\frac {7}{8}},{\frac {1}{2}})}$

The strong demand for monotony would mean that the components would be below , which is not the case because of . There is of course no violation of the monotony property of the Kalai-Smorodinsky solution, because the utility of the first player in is not normalized to 1. ${\displaystyle \varphi _{m}(B,0)}$ ${\displaystyle \varphi _{m}({\tilde {B}},0)}$ ${\displaystyle \textstyle {\frac {7}{11}}>{\frac {1}{2}}}$ ${\displaystyle ({\tilde {B}},0)}$

literature

• Berninghaus, SK, KM Erhart, and W. Güth. "Strategic Games: An Introduction to Game Theory, 2nd, revised and expanded" Ed., Berlin et al. O (2010). Chapter 4.1.2.

Individual evidence

1. ^ D. Luce, H. Raiffa: Games and Decisions , John Wiley & Sons (1957), Chapter 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, pp. 513-518. JSTOR 1914 280
3. ^ Burkhard Rauhut , Norbert Schmitz , Ernst-Wilhelm Zachow: Game Theory , Teubner, Stuttgart 1979, ISBN 3-519-02351-2 , example (4.31)
4. ^ Burkhard Rauhut, Norbert Schmitz, Ernst-Wilhelm Zachow: Game theory , Teubner, Stuttgart 1979, ISBN 3-519-02351-2 , corollary (4.24)
5. ↑ Burkhard Rauhut, Norbert Schmitz, Ernst-Wilhelm Zachow: Game Theory , Teubner, Stuttgart 1979, ISBN 3-519-02351-2 , note (4.29) and example (4.23)