From Theory
Jump to: navigation, search

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 <math>\R^2</math> we have the following assumptions:

- Disagreement Point <math>\theta \in \R^2</math>

- For this presentation, <math>\theta = 0</math>

- Convex and Compact set <math>S \subseteq\R^2</math>

- <math>\exists </math> <math>u\in S</math> s.t. <math>u> \theta</math>

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

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

Nash's Axioms

1.Individual Rationality

<math>f(s) > 0</math>

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

<math>\forall u\in S</math> <math> u \geq f(s)</math> and <math>u=f(s)</math>

3. Independence of Irrelevant Alternatives

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

<math>\forall s^'\subseteq S, </math> <math>s^' </math>is compact and convex, Then <math>f(s)\in s^', f(s^')=f(s)</math>

4. Scale and Variance

<math>\forall c_1, c_2 > 0</math>, <math>T(x)=(c_1 x_1, c_2 x_2)</math>, <math>f(T(s))= T(f(s))</math> where <math>f(T(s))</math> 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 <math>\forall</math> <math>(u_1, u_2)\in S</math> and <math>(u_2, u_1)\in S</math>, then <math>f(s)= (a, a)</math> for some <math>a\in R</math>


The unique <math>f</math> satisfying Axion 1-5 is:

<math>\forall x \in  S</math> <math>f(x)= argmax(x_1 \cdot x_2) = argmax [log(x_1)+ log(x_2)]</math>

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 <math>argmax</math>(by strict concavity). Fix <math>s</math>, Take <math>s^' =\lbrace(\frac{1}{c_1} x_1, \frac{1}{c_2} x_2)|(x_1,x_2) \in S\rbrace</math>

Take <math>(c_1, c_2) \in S</math> to <math>\max (c_1,c_2)</math>

<math>f(s^')=(1,1)</math> by Axiom 4

<math>s^' \subseteq \lbrace(x_1, x_2)| x_1 + x_2 \leq 2\rbrace</math>

Alternative axioms

The alternative axioms discussed in class are highlighted by problem 3 of GTCS Assignment 4.

Computer Science Related Bargaining

Convex Program:

Input: <math>(x_o \in S, M_s: R^n \rightarrow {0, 1}, r, R, \epsilon >0, f: S \rightarrow [0, 1])</math>

Where <math>S </math>is a convex compact subset of <math>R^n</math>

<math> M_s (x)=\begin{cases}1 & \mbox{if }x\in S\\ 0 & \mbox{if }x\notin S\end{cases}</math>.

<math>f</math> is concave

Output: <math>x</math> such that <math>f(x) \geq \max_{y \in S} f(y) - \epsilon</math>

Runtime: polynomial <math>(n, \frac {1}{\epsilon}, \frac {R}{r})</math>