## Definition

## Equilibrium

__Unique Equilibrium__

- If the utility function of each player has concavity, then there exist a unique equilibrium.

Reply

The utility functions of both players sum up to 0

- If the utility function of each player has concavity, then there exist a unique equilibrium.

- VCG can maximize the social welfare given the individuals are all “selfish”

- Players
- There are game players,
- Actions
- The actions of the players are denoted as
- Payoff
- Real demand
- Cost
- for its action
- Utility

Following Nisan’s work, the terms “mechanisms” and “incentive compatible” are defined as

- Given a set of n players, and a set of outcomes, A, let be the set of possible valuation functions of the form which player could have for an outcome . A mechanism is a function . Given the evaluations claimed by the players, f selects an outcome, and n payment functions, , where .

The above defines Action and Reward.

- For every player , every , , , , and every , where and , then
- , then the mechanism is incentive compatible.

Specifically, among those incentive compatible mechanisms, the Vickrey-Clarke-Groves (VCG) mechanism is the mostly used one.

The VCG generally seeks to maximize the social welfare of all players in one game, where the social welfare is calculated as . So the goal function of VCG is .

The VCG mechanism and the rule to design VCG mechanisms are defined as follows.
### VCG Mechanism

### Clarke Pivot Rule

- A mechanism, consisting of payment functions and a function , for a game with outcome set , is a Vickrey-Clarke-Groves mechanism if ( f maximizes the social walfare) for some functions , where (h_i does not depend on )
- , .

My understanding

- For user , its reward is depended on others, and not related to its action
- But why in the payment function, it deducts other users’ true value?

- The choice is called the Clark pivot payment. Under this rule the payment of player is
- where .

My understanding

- I didn’t understand it yet.

**1. Desired Properties**

- invariant to coordinate-wise affine transformation
- symmetry-preserving
- efficient
- monotone

We consider a two-person bargaining problem formulated as follows

- : to every two-person game we associated a pair , where is a point in the plane and is a subset of the plane.
- The pair has the following intuitive interpretation:
*where is the level of utility that player receives if the two players**do not cooperate*with each other. - Every point
*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 such that . In other words, bargaining may prove
*worthwhile for both players*. - Assumption 2:
*is convex*. This is justified under the assumption if two outcomes of the game give raise to points and in , then randomization of these two outcomes give raise to all convex combinations of and . - Assumption 3: is
*compact*. - Assumption 4:
*for every*. If this is not the case, we can disregard all the points of that fail to satisfy this condition because it is impossible that both players will agree to such a solution.

**4. Axioms**

We let denote the set of pairs that satisfying these four conditions, and we call an element in a bargaining pair.

- Axiom 1:
*Pareto Optimality* - For every there is no such that and .
- Axiom 2:
*Symmetry* - We let be defined by and we require that for every , .
- Axiom 3:
*Invariance*with Respect to*Affine Transformation of Utility* - A is an afine transformation of utility if , , and the maps are of the form for some positive constant and some constant . We require that for such a transformation , .

In addition to the above three axioms, Nash introduced the following

- Axiom of
*Independence of Irrelavant Alternatives* - If and are bargaining pairs such that and , then .
- Interpretation: given a bargaining pair , for every point , consider the product . Then is the unique point in that maximizes this product.
- Many objectives are raised to Nash’s axiom of independence of irrelevant alternatives.

We define some notations,

- Let be a function defined for in the following way
- if is the Pareto of .
- if there is no such .
- thus is the maximum player 2 can get if player 1 get at least x.
- By assumption 1 in the definition of a bargaining pair .
- By the compactness of , and are finite and are attained by points in .
- A pair will be called
*normalized*if and . 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 and where

- = convex hull, and
- = convex hull,
- Nash’s solution for is , and for .
- Limitations pf Nash’s solution: Player 2 has good reasons to demand that he get more in the bargaining pair than he does in .

In order to overcome this limitation, Kalai suggests the following alternative axiom.

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

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

- 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 with player 2’s help (and vice versa for ), then the bargaining solution would yield the
*point*on the Pareto frontier such that .

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.

- : the set of possible agreements
- X = {, )| , }
- : the disagreement outcome
- D = (0,0)
- : each player i has preferences, represented by a utility function over

Definition: a bargaining problem is then defined as a pair of where and . We assume that

- is a
*convex*and*compact*set - There exists some such that (i.e.,
*for some i)*

**3. Axioms**

*Pareto Efficiency*- A bargaining solution is Pareto efficient if there does not exist a such that and for some .
- An inefficient outcome is unlikely, since it leaves space for
*renegotiation*. *Symmetry*- Let be such that if and only if and . Then .
- If the players are indistinguishable, the agreement should not discriminate between them.
*Invariance to Equivalent Payoff Representations*- Given a bargaining problem , consider a different bargaining problem , for some .
- Then
- 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 and be two bargaining problems such that , if , then .

**4. Nash Bargaining Solution****Definition: **We say that a pair of payoffs is a Nash bargaining solution if it solves the following optimization problem

- subject to

We use to denote the Nash Bargaining Solution

*Existence*of an optimal solution: since the set 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 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