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

edit

A two-person bargain problem consists of a pair  :

  • A feasible agreements set  . This is a closed convex subset of  . Each element of   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   is convex makes sense, for example, when it is possible to combine agreements by randomization.
  • A disagreement point  , where   and   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   are better for both parties than the disagreement.

A bargaining solution is a function   that takes a bargaining problem   and returns a point in its feasible agreements set,  .

Requirements from bargaining solutions

edit

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   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.

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

The monotonicity requirement says that, if   and   are two bargaining problems such that:

  •  
  • For every u,  

Then, the solution f must satisfy:

  •  

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

edit

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

Let   be the point of best utilities  . Draw a line   from   (the point of disagreement) to   (the point of best utilities).

By the non-triviality assumption, the line   has a positive slope. By the convexity of  , the intersection of   with the set   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   on the Pareto frontier of  , such that:

 

Examples

edit

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:  . Hence, the set   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:

 

The maximum is attained when   and   and   (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:

 

Here, the maximum is attained when   and   and  . 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   and   and  , which gives a utility-gain of only $15 to Alice and $35 to George.

See also

edit

References

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