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

Leave a Reply