Mechanisms with Money
Definition
-
Finite set of alternatives A={a,b,c,…} Set I of n players
-
The preference is expressed by a valuation function
Single Item Auction (拍卖)
Description of the Game
-
Strategy Set: The players bid bi (probably ≠ vi)
-
Allocation Algorithm: Who is going to get the object?
- xi = xi(b) ({0, 1}) // xi(b) 属于 0 或 1
-
Payment Scheme: At what price?
-
player i wants to maximize his utility ui=xi(vi-p)
-
No Payment
-
p = 0€
-
b2 > 100€
-
First Price Auction
-
p=100 €
-
p=70+ε €
-
==> b1 > 70+ε €
Vickrey Auction
Incentive Compatible Mechanisms
-
choose alternative + charge payment
-
vi: A -> R for vi belong to Vi
-
set of valuations for player i Vi is a truth subset of R_A (R_A 是 Vi 的真子集)

-
A (direct revelation) mechanism is a social choice function f:V1×⋅⋅⋅×Vn→A and a vector of payment functions p1,…,pn, where pi:V1×⋅⋅⋅×Vn→R
-
A mechanism (f, p1,…,pn) is incentive compatible (or strategy proof) if for every player i, every v=(v1,…,vn) and every v’i vi(f(vi,v-i))-pi(vi,v-i) ≥ vi(f(v’i,v-i))-pi(v’i,v-i)
-
Example1:
|
|
f(vi,v-i)=a |
f(v’i,v-i)=b |
pi(vi,v-i)=3 |
pi(v’i,v-i)=5 |
vi(f(vi,v-i))=6 |
vi(f(vi,v-i))=7 |
|
|
f(vi,v-i)=a |
f(v’i,v-i)=b |
pi(vi,v-i)=3 |
pi(v’i,v-i)=5 |
vi(f(vi,v-i))=vi(a)=6 |
vi(f(v’i,v-i))=vi(b)=7 |
vi(f(vi,v-i))-p(vi,v-i) =3 |
vi(f(v’i,v-i))-p(v’i,v-i)=2 |
|
|
f(vi,v-i)=a |
f(v’i,v-i)=b |
pi(vi,v-i)=3 |
pi(v’i,v-i)=3 |
vi(f(vi,v-i))=vi(a)=6 |
vi(f(v’i,v-i))=vi(b)=7 |
vi(f(vi,v-i))-p(vi,v-i)=3 |
vi(f(v’i,v-i))-p(v’i,v-i)=4 |
Vickrey-Clarke-Groves (VCG) Mechanisms
A mechanism (f,p1,…,pn) is called VCG mechanism if

VCG Payments
- A mechanism is ex-post individually rational if players get non-negative utility.
vi(f(vi,v-i))-pi(vi,v-i) ≥ 0
- A mechanism has no positive transfers if no player is ever paid money.
pi(vi,v-i) ≥ 0