Thursday, 3.7.2008, 14:30
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.