The Generalized Vickrey Auction (VCG mechanism) Let G be set of all routes, I be set of bidders Agent i submits bids v i * (S) for all bundles S  G Compute allocation S* to maximize sum of reported bids Compute best allocation without each agent i: Allocate each agent Si*, each agent pays V*(I)=max (S1,…,SI)  i v i *(S i ) V*(I\i)=max (S1,…,SI)  j  i v i *(S i ) P(i)=v i *(S i *)-[V*(I)-V*(I\i)]
{}