Informational overhead of incentive compatibility

In the presence of self-interested parties, mechanism designers typically aim to achieve their goals (or socialchoice functions) in an equilibrium. In this paper, we study the cost of such equilibrium requirements in terms of communication, a problem that was recently raised by Fadel and Segal [14]. While a certain amount of information x needs to be communicated just for computing the outcome of a certain social-choice function, an additional amount of communication may be required for computing the equilibrium-supporting prices (even if such prices are known to exist). Our main result shows that the total communication needed for this task can be greater than x by a factor linear in the number of players n, i.e., n · x. This is the first known lower bound for this problem. In fact, we show that this result holds even in single-parameter domains (under the common assumption that losing players pay zero). On the positive side, we show that certain classic economic objectives, namely, single-item auctions and public-good mechanisms, only entail a small overhead. Finally, we explore the communication overhead in welfare-maximization domains, and initiate the study of the overhead of computing payments that lie in the core of coalitional games.