Vickrey-Clarke-Groves (VCG) Mechanism

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.

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    *