We examine combinatorial public projects, a game in which the goal is to provide a set of items to be shared equally among a group of agents.
One might expect that these games are easier to solve than auctions, as desired items can be shared rather than fought over, but we show that combinatorial public projects are more difficult from computational and game-theoretic perspectives. This difficulty includes the failure of VCG-based mechanism to get any constant approximation factor in the games studied, even for a constant number of players. Our impossibility results even extend to public projects with only a single player, for which all truthful mechanisms are VCG-based.
We also show a few positive results, including some simple truthful mechanisms for highly restricted classes of players that achieve constant approximation factors where VCG-based mechanisms cannot get any constant approximation.
Joint work with Michael Schapira and Yaron Singer