Relationships between centrality measures and VCG mechanism

In this work we show that some recent centrality measures in network analysis are exactly an application of the principles underlying the Vickrey-Clarke-Groves (VCG) mechanism. We then present specific examples of completely different frameworks which highlights how these centrality measures ˆ la VCG can indeed provide valuable information to fairly assess the importance of the analyzed network elements. However, by taking inspiration from the relevant literature on the VCG auction design, we verify that in general cases centrality measures ˆ la VCG can determine a poor estimate of the actual significance of some network elements; therefore, we provide a general approach to effectively improve such estimates, based on applying the VCG rule to suitable groups of elements of the network.