Equilibrium in Combinatorial Public Projects

Abstract. We study simple item bidding mechanisms for the combina-torial public project problem and explore their eciency guarantees in various well-known solution concepts. We rst study sequential mech-anisms where each agent, in sequence, reports her valuation for every item in a predened order on the agents determined by the mechanism. We show that if agents ' valuations are unit-demand any subgame per-fect equilibrium of a sequential mechanism achieves the optimal social welfare. For the simultaneous bidding equivalent of the above auction we show that for any class of bidder valuations, all Strong Nash Equi-libria achieve at least a O(logn) factor of the optimal social welfare. For Pure Nash Equilibria we show that the worst-case loss in eciency is proportional to the number of agents. For public projects in which only one item is selected we show constructively that there always ex-ists a Pure Nash Equilibrium that guarantees at least 1 2 (1 1 n) of the optimum. We also show eciency bounds for Correlated Equilibria and Bayes-Nash Equilibria, via the recently introduced smooth mechanism framework [26].