Abstract:

We consider the amount of communication required to verify the outcome of the Vickrey-Clarke-Groves (VCG) mechanism: an efficient allocation together with incentivizing VCG payments. We compare this to the communication required to verify the efficient decision rule alone, to assess the overhead imposed by VCG payments. Our characterizations are obtained by leveraging a connection between the VCG outcome and a price equilibrium concept known as universal competitive equilibrium. We consider four related environments within a common framework: the classic single-item setting, the multi-unit setting with decreasing marginal values, the classic assignment problem with unit-demand valuations, and the multi-unit assignment problem with substitutes valuations. We find that the single-unit settings have zero overhead, whereas the multi-unit settings can have significant positive overhead. With multiple units, the naive VCG protocol that runs several efficient protocols in sequence (one with all agents, and ones with an agent removed, for each agent) is asymptotically optimal for several parameter settings of the number of agents, commodities and units.