Bargaining

From Theory

Scribe: Aaron Elliott

Notes for CS 8803 - Game Theory and Computer Science. Spring 2008

The Nash Bargaining Problem was introduced by John Nash in 1950. The game addresses the manner in which a fair portion of some good is divided between players. (For simplicity this discussion will be limited to 2 players.) For example selling a car - the car and the payment both represent some pair of utility for both players.

Working in $\R^2$ we have the following assumptions:

- Disagreement Point $\theta \in \R^2$

- For this presentation, $θ = 0$

- Convex and Compact set $S \subseteq\R^2$

- $\exists$ $u\in S$ s.t. $u > θ$

GOAL: Find a Fair Function $f(s)\in S$ where $f$ is a "fair" allocation function.

(* Note: The set in the figure should be convex. *)

1 Nash's Axioms
2 Theorem
3 Alternative axioms
4 Computer Science Related Bargaining

[edit]

Nash's Axioms

1.Individual Rationality

$f (s) > 0$

2. Pareto Optimality Any fair agreement should be better off than the disagreement point.

$\forall u\in S$ $u \geq f(s)$ and $u = f (s)$

3. Independence of Irrelevant Alternatives

The presence of irrelevant alternatives in S should not influence the bargaining solution.

$\forall s^'\subseteq S,$ $s'$ is compact and convex, Then $f(s)\in s^', f(s^')=f(s)$

4. Scale and Variance

$\forall c_1, c_2 > 0$ , $T (x) = (c 1 x 1, c 2 x 2)$ , $f (T (s)) = T (f (s))$ where $f (T (s))$ is the set of transferred points

5. Symmetry

Symmetry says that symmetric utility functions should ensure symmetric payoffs. Payoff should not discriminate between the identities of the players. It should only depend on their payoff functions.

If $\forall$ $(u_1, u_2)\in S$ and $(u_2, u_1)\in S$ , then $f (s) = (a, a)$ for some $a\in R$

[edit]

Theorem

The unique $f$ satisfying Axion 1-5 is:

Proof: A unique maximum is achieved when maximizing a concave function in a convex set. The point in the set where a maximum is found exists from compactness. Convexity makes it unique.

Uniqueness of $a r g m a x$ (by strict concavity). Fix $s$ , Take $s^' =\lbrace(\frac{1}{c_1} x_1, \frac{1}{c_2} x_2)|(x_1,x_2) \in S\rbrace$