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

Summary of Nash Bargaining

1. Bargaining problems Scenarios
Bargaining problems represent situations in which

• There is a conflict of interest about agreements.
• Individual have the possibility of concluding a mutually beneficial agreements.
• No agreement may be imposed on any individual without his approval

2. Bargaining problem Definition
Example: Suppose 2 players must split one unit of good. If no agreement is reached, then players do not receive anything. We define the following notations.

• $X$: the set of possible agreements
• X = {$x_1$, $x_2$)| $x_1 + x_2 = 1$, $x_i \geq 0$}
• $D$: the disagreement outcome
• D = (0,0)
• $u_i$: each player i has preferences, represented by a utility function $u_i$ over $X \cup {D}$

Definition: a bargaining problem is then defined as a pair of $(U,d)$ where $U \in R^2$ and $d \in U$. We assume that

• $U$ is a convex and compact set
• There exists some $v \in U$ such that $v > d$ (i.e., $v_i > d_i$ for some i)

3. Axioms

• Pareto Efficiency
• A bargaining solution $f(U,d)$ is Pareto efficient if there does not exist a $(v_1, v_2) \in U$ such that $v \geq f(U,d)$ and $v_i > f_i(U,d)$ for some $i$. 
• An inefficient outcome is unlikely, since it leaves space for renegotiation.
• Symmetry
• Let $(U,d)$ be such that $(v_1, v_2) \in U$ if and only if $(v_2, v_1) \in U$ and $d_1 = d_2$. Then $f_1(U,d) = f_2 (U,d)$.
• If the players are indistinguishable, the agreement should not discriminate between them.
• Invariance to Equivalent Payoff Representations
• Given a bargaining problem $(U,d)$, consider a different bargaining problem $(U', d')$, for some $\alpha >0, \beta$.
• $U' = \{(\alpha_1 v_1 + \beta_1, \alpha_2 v_2 + \beta_2)| (v_1, v_2 \in U\}$
• $d' = (\alpha_1 d_1 + \beta_1, \alpha_2 d_2 + \beta_2)$
• Then $f_i(U', d') = \alpha_i f_i (U,d) + \beta_i$
• Utility functions are only representation of preferences over outcomes. A transformation of the utility function that maintaining the same ordering over preferences (such as linear transformation) should not alter the outcome of bargaining process.
• Independence of Irrelevant Alternatives
• Let $(U,d)$ and $(U', d)$ be two bargaining problems such that $U' \subset U$, if $f(U,d) \in U'$, then $f(U', d) = f(U,d)$.

4. Nash Bargaining Solution
Definition: We say  that a pair of payoffs $(v^*_1, v^*_2)$ is a Nash bargaining solution if it solves the following optimization problem

• $\max_{v_1, v_2} (v_1 - d_1)(v_2-d_2)$
• subject to 
• $(v_1, v_2) \in U$
• $(v_1, v_2) \geq (d_1, d_2)$

We use $f^N(U,d)$ to denote the Nash Bargaining Solution

Remarks: 

• Existence of an optimal solution: since the set $U$ is compact and the objective function of the problem is continuous, there exists an optimal solution for the problem
• Uniqueness of the optimal solution: the objective function of the problem is strictly quasi-concave. Therefore, the problem has a unique solution.

Proposition: Nash bargaining solution $f^N(U,d)$ is the unique bargaining solution that satisfies the 4 axioms.




Reference
[1] Game Theory with Engineering Applications: Nash Bargaining Solution, by Asu Ozdaglar, MIT 2010