Abstract:

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.