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$ )