Optimal VCG mechanisms to assign multiple bads

For the problem of assigning economic “bads” (for example, costly tasks or undesirable objects), Vickrey-Clarke-Groves (VCG) mechanisms achieve efficient allocations via money transfers. However, they can produce arbitrarily large budget surpluses or deficits. We construct a performance index for a VCG mechanism to measure its budget surplus and deficit in the worst-case. Using this index, we develop mechanisms whose surpluses or deficits vanish as the number of participants increases, for both cases of bads and goods. We find that individual rationality creates an asymmetry between surplus and deficit, particularly in the case of bads. When the number of agents is large enough, a minute amount of deficit can replace unit surplus to achieve a budget balance. For the case of economic goods, unit surplus can only be replaced with unit deficit, regardless of individual rationality. This result shows that the model with bads differs fundamentally from the model with goods.