The Taub Faculty of Computer Science Events and Talks

The central problem in computational mechanism design is the tension between incentive compatibility and computational efficiency. We address this question in the context of a novel mechanism design problem which we call the combinatorial public project problem. We show that, even though this problem is easily solvable from a computational viewpoint, and from an economic perspective, no algorithm which is simultaneously truthful and runs in polynomial-time can obtain any reasonable approximation ratio. We prove our result in both the communication- and computational-complexity models. In particular, we present a novel technique for proving computational lower bounds for the case in which the private information of the agents can be succinctly described. This is one of the first impossibility results connecting mechanism design to computational-complexity theory. We believe that this technique, which involves an application of the Sauer-Shelah Lemma, may be of wider applicability, both within and without mechanism design. Joint work with Christos Papadimitriou and Yaron Singer.