Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2013-14 > VCG Auction Mechanism Cost Expectations and Variances
How to contact us


LSE 10 logo master_6

Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE


Enquiries: dom.events@lse.ac.uk 


Follow us online



VCG Auction Mechanism Cost Expectations and Variances

Wednesday 26 February 2014, 4.30pm - 5.30pm
5.21, New Academic Building, LSE

Greg Sorkin

Chair of Management Science and Mathematics, Department of Management, LSE  

Personal Profile


We consider Vickrey--Clarke--Groves (VCG) auctions for a very general combinatorial structure, in an average-case setting where item costs are independent, identically distributed uniform random variables. We prove that the expected VCG cost is at least double the expected nominal cost, and exactly double when the desired structure is a basis of a bridgeless matroid. In the matroid case we further show that, conditioned upon the VCG cost, the expectation of the nominal cost is exactly half the VCG cost, and we show several results on variances and covariances among the nominal cost, the VCG cost, and related quantities.  We provide examples showing that our results cannot be strengthened in some natural ways.

Our methods allow calculation of the VCG cost variance in some cases, including (asymptotically) for a minimum spanning tree in a complete graph with random edge costs.

This is joint work with Svante Janson (Uppsala).



 Greg Sorkin