Kalai-Smorodinsky Solution to Bargaining Problems

1. Desired Properties

• invariant to coordinate-wise affine transformation
• symmetry-preserving
• efficient
• monotone

2. Problem Statement
We consider a two-person bargaining problem formulated as follows

• $(a, S)$: to every two-person game we associated a pair $(a,S)$, where $a$ is a point in the plane and $S$ is a subset of the plane. 
• The pair $(a,S)$ has the following intuitive interpretation: $a = (a_1, a_2)$ where $a_i$ is the level of utility that player $i$ receives if the two players do not cooperate with each other.
• Every point $x = (x_1, x_2) \in S$ represents the level of utility for players 1 and 2 that can be reached by an outcome of the game which is feasible for the two players when they do cooperate. 

3. Assumption

• Assumption 1: There is at least one point $x \in S$ such that $x^i > a_i, for i = 1,2$. In other words, bargaining may prove worthwhile for both players.
• Assumption 2: $S$ is convex. This is justified under the assumption if two outcomes of the game give raise to points $x$ and $y$ in $S$, then randomization of these two outcomes give raise to all convex combinations of $x$ and $y$. 
• Assumption 3: $S$ is compact. 
• Assumption 4: $a \leq x$ for every $x \in S$. If this is not the case, we can disregard all the points of $S$ that fail to satisfy this condition because it is impossible that both players will agree to such a solution.

4. Axioms
We let $U$ denote the set of pairs $(a,S)$ that satisfying these four conditions, and we call an element in $U$ a bargaining pair.

• Axiom 1: Pareto Optimality
• For every $(a,S) \in U$ there is no $y \in S$ such that $y \geq f(a,S)$ and $y \neq f(a,S)$. 
• Axiom 2: Symmetry
• We let $T: R^2 \rightarrow R^2$ be defined by $T((x_1, x_2)) = (x_2, x_1)$ and we require that for every $(a,S) \in U$, $f(T(a), T(S)) = T(f(a,s))$.
• Axiom 3: Invariance with Respect to Affine Transformation of Utility
• A is an afine transformation of utility if $A = (A_1, A_2): R^2 \rightarrow R^2$, $A((x_1, x_2)) = (A(x_1), A(x_2))$, and the maps $A_i(x)$ are of the form $cx_i + d_i$ for some positive constant $c_i$ and some constant $d_i$. We require that for such a transformation $A$, $f(A(a), A(S)) = A(f(a,S))$.

In addition to the above three axioms, Nash introduced the following

• Axiom of Independence of Irrelavant Alternatives
• If $(a,S)$ and $(a, T)$ are bargaining pairs such that $S \subset T$ and $f(a,T) \in S$, then $f(a,T) = f(a,S)$. 
• Interpretation: given a bargaining pair $(a,S)$, for every point $x = (x_1, x_2) \in S$, consider the product $(x_1 - a_1) (x_2 - a_2)$. Then $\eta(a,S)$ is the unique point in $S$ that maximizes this product.
• Many objectives are raised to Nash's axiom of independence of irrelevant alternatives.  

We define some notations, 

• $b_1 (s) = sup \{x \in R; \mbox{ for some } y \in R (x,y) \in S\}$
• $b_2 (s) = sup \{y \in R; \mbox { for some } x \in R (x,y) \in S\}$
• Let $g_s(x)$ be a function defined for $x \leq b_1(s)$ in the following way
• $g_s(x) = y$ if $(x,y)$ is the Pareto of $(a,s)$. 
• $g_s(x) = b_s(S)$ if there is no such $y$.
• thus $g_s(x)$ is the maximum player 2 can get if player 1 get at least x. 
• By assumption 1 in the definition of a bargaining pair $b_i(S) > a_i$. 
• By the compactness of $S$, $b_1(S)$ and $b_2(S)$ are finite and are attained by points in $S$. 
• A pair $(a,S)$ will be called normalized if $a = 0 = (0,0)$ and $b(S) = (1,1)$. Clearly every game can be normalized by a unique affine transformation of the utilities. 

Example objective to Nash's Solution: consider the following two normalized pair $(0,S_1)$ and $(0,S_2)$ where

• $S_1$ = convex hull, ${(0,1), (1,0), (0.75, 0.75)}$ and 
• $S_2$ = convex hull, ${(0,1), (1,0), (1, 0.7)}$
• Nash's solution for $(0,S_1)$ is $(0.75, 0.75)$, and $(1, 0.7)$ for $(0,S_2)$. 
• Limitations pf Nash's solution: Player 2 has good reasons to demand that he get more in the bargaining pair $(0,S_2)$ than he does in $(0,S_1)$. 

In order to overcome this limitation, Kalai suggests the following alternative axiom.

Axiom of Monotonicity: If $(a,S_2)$ and $(a, S_1)$ are bargaining pairs such that $b_1(S_1) = b_1(S_2)$ and $g_{s_1} = g_{s_2}$, then $f_2(a,S_1) = f_2(a,S_2)$ (where $f(a,S) = (f_1(a,S), f_2(a,S))$. 

• This axiom states that 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. 

Theorem: There is one and only one solution, $\mu$, satisfying the axioms of monotonicity. The function $\mu$ has the following simple representation. For a pair $(a,S) \in U$ consider the line joining a to be $b(S)$, $L(a,b(S))$. The maximal element (with partial order of $R^2$) of $S$ on this line is $\mu(a,S)$. 

5. How does it work

• to normalize the utility function of each agent in such a way that it is worth zero at the status quo and one at this agent's best outcome -- given that all others get at least their status quo utility level
• to sharing equally the benefits of cooperation. In other words, this solution equalizes the relative benefit from status quo or equivalently the relative frustration until the shadow optimum. 

6. Solution

• Independence of irrelevant alternatives can be substituted with a monotonicity condition. It is the point which maintains the ratios of maximal gains. In other words, if player 1 could receive a maximum of $g_1$ with player 2's help (and vice versa for $g_2$), then the bargaining solution would yield the point $\phi$ on the Pareto frontier such that $\phi_1 / \phi_2 = g_1/ g_2$.

References
[1] Bargaining problem, wiki
[2] Other solutions to Nash's bargaining problem, by Ehud Kalai, Meir Smorodinsky, in STOR 1975