Introduction
- VCG can maximize the social welfare given the individuals are all “selfish”
Model
- Players
- There are
game players,
- Actions
- The actions of the players are denoted as
- Payoff
- Real demand
- Cost
for its action
- Utility
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
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.
Incentive Compatible
- 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
.
![Rendered by QuickLaTeX.com sum^n_{i=1} v_i](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-f89bbf60603606f0515695d54000bb0c_l3.png)
![Rendered by QuickLaTeX.com argmax_{a in A} sum^n_{i=1} v_i](http://mytechroad.com/wp-content/ql-cache/quicklatex.com-03bf708ca098278644a77aa49e4282a3_l3.png)
The VCG mechanism and the rule to design VCG mechanisms are defined as follows.
VCG Mechanism
- 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?
Clarke Pivot Rule
- 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.