Category Archives: Game-Theory

Vickrey-Clarke-Groves (VCG) Mechanism

Posted on by
Reply

Introduction

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

Model

  • Players
    • There are n game players, P_1, P_2, cdots, P_n
  • Actions
    • The actions of the players are denoted as X = (x_1, x_2, cdots, x_n)
  • Payoff
    • v_i(X)
  • Real demand
    • v_i
  • Cost
    • p_i for its action
  • Utility
    • u_i = v_i - p_i

Definition

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

Mechanism

  • Given a set of n players, and a set of outcomes, A, let v_i be the set of possible valuation functions of the form v_i(a) which player i could have for an outcome a in A. A mechanism is a function f: V_1 cdot V_2 cdot cdots cdot V_n rightarrow A. Given the evaluations claimed by the players, f selects an outcome, and n payment functions, p_1, p_2, cdots, p_n, where p_i = V_1 cdot V_2 cdot cdots V_n rightarrow R.

The above defines Action and Reward.

    Incentive Compatible

    • For every player i, every v_1 in V_1, v_2 in V_2, cdots, v_n in V_n, and every v'_i in V_i, where a = f(v_i, v_{-i}) and a' = f(v'_i, v_{-i}), then
      • v_i(a) - p_i(v_i, v_{-i}) geq v_i(a') - p_i(v'_i, v_{-i}), 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 sum^n_{i=1} v_i. So the goal function of VCG is argmax_{a in A} sum^n_{i=1} v_i. 
    The VCG mechanism and the rule to design VCG mechanisms are defined as follows.

    VCG Mechanism

    • A mechanism, consisting of payment functions p_1, p_2, cdots, p_n and a function f, for a game with outcome set A, is a Vickrey-Clarke-Groves mechanism if f(v_1, v_2, cdots, v_n) = argmax_{a in A} sum^n_{i=1} v_i(a) ( f maximizes the social walfare) for some functions h_1, h_2, cdots, h_n, where h_i : V_{-i} rightarrow R (h_i does not depend on v_i)
      • forall v_i in V, p_i(v_i) = h(v_{-i}) - sum_{j neq i} v_j.

    My understanding

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

    Clarke Pivot Rule

    • The choice h_i(v_{-i}) = max_{b in A} sum_{j neq i} v_i(b) is called the Clark pivot payment. Under this rule the payment of player i is
      • p_i(v_1, v_2, cdots, v_n) = max_{b} sum_{j neq i} v_i(b) - sum_{j neq i} v_i(a) where a= f(v_1, v_2, cdots, v_n).

    My understanding

    • I didn’t understand it yet.

    Kalai-Smorodinsky Solution to Bargaining Problems

    Posted on by
    Reply

    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

    Summary of Nash Bargaining

    Posted on by
    Reply

    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