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.