Competitive VCG redistribution mechanism for public project problem

Abstract

The VCG mechanism has many nice properties, and can be applied to a wide range of social decision problems. One problem of the VCG mechanism is that even though it is efficient, its social welfare (agents' total utility considering payments) can be low due to high VCG payments. VCG redistribution mechanisms aim to resolve this by redistributing the VCG payments back to the agents. Competitive VCG redistribution mechanisms have been found for various resource allocation settings. However, there has been almost no success outside of the scope of allocation problems. This paper focuses on another fundamental model - the public project problem. In Naroditskiy et al. 2012, it was conjectured that competitive VCG redistribution mechanisms exist for the public project problem, and one competitive mechanism was proposed for the case of three agents (unfortunately, both the mechanism and the techniques behind it do not generalize to cases with more agents). In this paper, we propose a competitive mechanism for general numbers of agents, relying on new techniques.