a truthful randomized mechanism for combinatorial public projects via convex optimization
In Combinatorial Public Projects , there is a set of projects that may be undertaken, and a set of self-interested players with a stake in the set of projects chosen. A public planner must choose a subset of these projects, subject to a resource constraint, with the goal of maximizing social welfare. Combinatorial Public Projects has emerged as one of the paradigmatic problems in Algorithmic Mechanism Design , a field concerned with solving fundamental resource allocation problems in the presence of both selfish behavior and the computational constraint of polynomial time. We design a polynomial-time, truthful-in-expectation, (1-1/e)-approximation mechanism for welfare maximization in a fundamental variant of combinatorial public projects. Our results apply to combinatorial public projects when players have valuations that are matroid rank sums (MRS) , which encompass most concrete examples of submodular functions studied in this context, including coverage functions and matroid weighted-rank functions. Our approximation factor is the best possible, assuming P ? NP. Ours is the first mechanism that achieves a constant factor approximation for a natural NP-hard variant of combinatorial public projects.
combinatorial public projects algorithmic mechanism design