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.

[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

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

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