Abstract
We give an explanation to the relative lack of power of computationally efficient truthful mechanisms: only "simple" social choice functions can be implemented by a truthful mechanism with low communication complexity. This is done by showing that the well-known taxation principle entails a severe communication bottleneck.
Specifically, the taxation principle asserts that any truthful mechanism can be interpreted as follows: every player is presented with a menu that consists of a price for each bundle (the prices depend only on the valuations of the other players). The player is allocated a bundle that maximizes his profit according to this menu. Define the menu complexity of a truthful mechanism M to be the maximal number of menus that may be presented to some player. We show that under some mild conditions low communication complexity implies low menu complexity.
Our approach yields several promising implications, including strengthening the solution concept with low communication overhead, fast computation of prices, and hardness of approximation by computationally efficient truthful mechanisms. We will discuss some of them if time permits.