Kalai–Smorodinsky bargaining solution

The Kalai–Smorodinsky (KS) bargaining solution is a solution to the Bargaining problem. It was suggested by Ehud Kalai and Meir Smorodinsky,^[1] as an alternative to Nash's bargaining solution suggested 25 years earlier. The main difference between the two solutions is that the Nash solution satisfies independence of irrelevant alternatives, while the KS solution instead satisfies resource monotonicity.

Setting

A two-person bargain problem consists of a pair $(F,d)$ :

A feasible agreements set $F$ . This is a closed convex subset of $\mathbb {R} ^{2}$ . Each element of $F$ represents a possible agreement between the players. The coordinates of an agreement are the utilities of the players if this agreement is implemented. The assumption that $F$ is convex makes sense, for example, when it is possible to combine agreements by randomization.
A disagreement point $d=(d_{1},d_{2})$ , where $d_{1}$ and $d_{2}$ are the respective payoffs to player 1 and player 2 when the bargaining terminates without an agreement.

It is assumed that the problem is nontrivial, i.e., the agreements in $F$ are better for both parties than the disagreement.

A bargaining solution is a function $f$ that takes a bargaining problem $(F,d)$ and returns a point in its feasible agreements set, $f(F,d)\in F$ .

Requirements from bargaining solutions

The Nash and KS solutions both agree on the following three requirements:

Pareto optimality is a necessary condition. For every bargaining problem, the returned agreement $f(F,d)$ must be Pareto-efficient.

Symmetry is also necessary. The names of the players should not matter: if player 1 and player 2 switch their utilities, then the agreement should be switched accordingly.

Invariant to positive affine transformations also seems like a necessary condition: if the utility function of one or more players is transformed by a linear function, then the agreement should also be transformed by the same linear function. This makes sense if we assume that the utility functions are only representations of a preference relation, and do not have a real numeric meaning.

In addition to these requirements, Nash requires Independence of irrelevant alternatives (IIA). This means that, if the set of possible agreements grows (more agreements become possible), but the bargaining solution picks an agreement that was contained in the smaller set, then this agreement must be the same as the agreement reached when only the smaller set was available, since the new agreements are irrelevant. For example, suppose that in Sunday we can agree on option A or option B, and we pick option A. Then, in Monday we can agree on option A or B or C, but we do not pick option C. Then, Nash says that we must pick option A. The new option C is irrelevant since we do not select it anyway.

Kalai and Smorodinsky differ from Nash on this issue. They claim that the entire set of alternatives must affect the agreement reached. In the above example, suppose the preference relation of player 2 is: C>>B>A (C is much better than B, which is somewhat better than A) while the preference relation of 1 is reversed: A>>B>>C. The fact that option C becomes available allows player 2 to say: "if I give up my best option - C, I have a right to demand that at least my second-best option will be chosen".

Therefore, KS remove the IIA requirement. Instead, they add a monotonicity requirement. This requirement says that, for each player, if the utility attainable by this player for each utility of the other player is weakly larger, then the utility this player gets in the selected agreement should also be weakly larger. In other words, a player with better options should get a weakly-better agreement.

The formal definition of monotonicity is based on the following definitions.

$Best_{i}(F)$ - the best value that player i can expect to get in a feasible agreement.
$Best_{i}(F,u)$ - the best value that player i can expect to get in a feasible agreement in which the utility of the other player is $u$ (if the other player can never receive a utility of $u$ , then $Best_{i}(F,u)$ is defined to be $Best_{i}(F)$ ).

The monotonicity requirement says that, if $(F,d)$ and $(F',d)$ are two bargaining problems such that:

$Best_{1}(F)=Best_{1}(F')$
For every u, $Best_{2}(F,u)\leq Best_{2}(F',u)$

Then, the solution f must satisfy:

$f_{2}(F,d)\leq f_{2}(F',d)$

In the words of KS:

"If, for every utility level that player 1 may demand, the maximum feasible utility level that player 2 can simultaneously reach is increased, then the utility level assigned to player 2 according to the solution should also be increased".

By symmetry, the same requirement holds if we switch the roles of players 1 and 2.

The KS solution

The KS solution can be calculated geometrically in the following way.

Let $b(F)$ be the point of best utilities $(Best_{1}(F),Best_{2}(F))$ . Draw a line $L$ from $d$ (the point of disagreement) to $b$ (the point of best utilities).

By the non-triviality assumption, the line $L$ has a positive slope. By the convexity of $F$ , the intersection of $L$ with the set $F$ is an interval. The KS solution is the top-right point of this interval.

Mathematically, the KS solution is the maximal point which maintains the ratios of gains. I.e, it is a point $\mu$ on the Pareto frontier of $F$ , such that:

{\mu _{1}-d_{1} \over \mu _{2}-d_{2}}={Best_{1}(F)-d_{1} \over Best_{2}(F)-d_{2}}

Examples

Alice and George have to choose between three options, that give them the following amounts of money:.^[2]^: 88–92 Assume for the purposes of the example that utility is linear in money, and that money cannot be transferred from one party to the other.

	a	b	c
Alice	60	50	30
George	80	110	150

They can also mix these options in arbitrary fractions. E.g., they can choose option a for a fraction x of the time, option b for fraction y, and option c for fraction z, such that: $x+y+z=1$ . Hence, the set $F$ of feasible agreements is the convex hull of a(60,80) and b(50,110) and c(30,150).

The disagreement point is defined as the point of minimal utility: this is 30 for Alice and 80 for George, so d=(30,80).

For both Nash and KS solutions, we have to normalize the agents' utilities by subtracting the disagreement values, since we are only interested in the gains that the players can receive above this disagreement point. Hence, the normalized values are:

	a	b	c
Alice	30	20	0
George	0	30	70

The Nash bargaining solution maximizes the product of normalized utilities:

\max log(30x+20y)+log(30y+70z)

The maximum is attained when $x=0$ and $y=7/8$ and $z=1/8$ (i.e., option b is used 87.5% of the time and option c is used in the remaining time). The utility-gain of Alice is $17.5 and of George $35.

The KS bargaining solution equalizes the relative gains - the gain of each player relative to its maximum possible gain - and maximizes this equal value:

\max {30x+20y \over 30}={30y+70z \over 70}

Here, the maximum is attained when $x=0$ and $y=21/26$ and $z=5/26$ . The utility-gain of Alice is $16.1 and of George $37.7.

Note that both solutions are Pareto-superior to the "random-dictatorial" solution - the solution that selects a dictator at random and lets him/her selects his/her best option. This solution is equivalent to letting $x=1/2$ and $y=0$ and $z=1/2$ , which gives a utility-gain of only $15 to Alice and $35 to George.

References

^ Kalai, Ehud & Smorodinsky, Meir (1975). "Other solutions to Nash's bargaining problem". Econometrica. 43 (3): 513–518. doi:10.2307/1914280. JSTOR 1914280.
^ Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.

[1] Kalai, Ehud & Smorodinsky, Meir (1975). "Other solutions to Nash's bargaining problem". Econometrica. 43 (3): 513–518. doi:10.2307/1914280. JSTOR 1914280.

[moulin-2] Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.

[1]

[2]