Item Bidding for Combinatorial Public Projects

We present and analyze a mechanism for the Combinatorial Public Project Problem (CPPP). The problem asks to select k out of m available items, so as to maximize the social welfare for autonomous agents with combinatorial preferences (valuation functions) over subsets of items. The CPPP constitutes an abstract model for decision making by autonomous agents and has been shown to present severe computational hardness, in the design of truthful approximation mechanisms. We study a non-truthful mechanism that is, however, practically relevant to multi-agent environments, by virtue of its natural simplicity. It employs an Item Bidding interface, wherein every agent issues a separate bid for the inclusion of each distinct item in the outcome; the k items with the highest sums of bids are chosen and agents are charged according to a VCG-based payment rule. For fairly expressive classes of the agents' valuation functions, we establish existence of socially optimal pure Nash and strong equilibria, that are resilient to coordinated deviations of subsets of agents. Subsequently we derive tight worst-case bounds on the approximation of the optimum social welfare achieved in equilibrium. We show that the mechanism's performance improves with the number of agents that can coordinate, and reaches half of the optimum welfare at strong equilibrium