Approximately Optimal Mechanism Design vs. Revelation Principle

Question

The abstract of the article "Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations" (Dobzinski, Vondrak, 2016) states

A long-standing open question in algorithmic mechanism design is whether there exist computationally efficient truthful mechanisms for combinatorial auctions, with performance guarantees close to those possible without considerations of truthfulness. In this article, we answer this question negatively: the requirement of truthfulness can impact dramatically the ability of a mechanism to achieve a good approximation ratio for combinatorial auctions.

My question is-- given that the revelation principle says we can WLOG restrict our attention to direct-revelation IC mechanisms in mechanism design, how can there be a loss of revenue/lower approximation ratio by restricting the search of approximately optimal (i.e. revenue maximizing) mechanisms to IC ones?

Answer 1

A key part of the paper is that they are interested in

computationally efficient truthful mechanisms

The VCG mechanism is a truthful and efficient direct mechanism, but it is not computationally efficient. In many combinatorial auctions, it is impossible to compute the VCG transfers in a reasonable amount of time using current technology.

In the past, economists have largely ignored the problem of computational efficiency in mechanism design. This problem has been mainly addressed by computer scientists. Read for instance the introduction to Milgrom and Segal (2020) Clock Auctions and Radio Spectrum Reallocation. JPE

Answer 2

If I understand you correctly, there are two questions here.

First, why do computationally efficient IC direct mechanisms perform poorly relative to the optimal IC direct mechanism? The naive answer is simply that the optimal mechanism is really complicated; the paper seems to address this point carefully.

Second, why are there computationally efficient direct mechanisms that well-approximate the optimal IC direct mechanism but fail to be IC? Without being too familiar with algorithmic mechanism design, I suspect that this stems from the fact that the class of direct mechanisms (IC or not) is much larger than the class of IC direct mechanisms. In particular, one can induce any distribution over outcomes if one does not require IC but assumes that agents nevertheless report truthfully.

Note that the WLOG of the Revelation Principle has to be understood in the following way. ''Take an arbitrary mechanism and a distribution over outcomes in one of the mechanism's equilibria. There is an IC direct mechanism which produces the same distribution over outcomes under truthful reporting.'' The Revelation Principle does not claim that every distribution over outcomes is attainable through a suitably chosen IC direct mechanism---this is only true for those distributions that are already induced by some equilibrium of some indirect mechanism. In this sense, there is loss through restricting attention to IC direct mechanisms because some distributions over outcomes are simply never part of an equilibrium.