- VCG can maximize the social welfare given the individuals are all “selfish”
- There are game players,
- The actions of the players are denoted as
- Real demand
- for its action
Following Nisan’s work, the terms “mechanisms” and “incentive compatible” are defined as
- 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.
- 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 .
The VCG mechanism and the rule to design VCG mechanisms are defined as follows.
- 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 )
- , .
- 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 .
- I didn’t understand it yet.