April | 2015 | Lisa Tech Blog

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

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

Lisa Tech Blog

My security road

Monthly Archives: April 2015

Kalai-Smorodinsky Solution to Bargaining Problems

Summary of Nash Bargaining