“Communication in Economic Mechanisms”, Ilya Segal2006-11 (algorithms, mechanism design)⁠:

This chapter considers the problem of finding allocations that satisfy certain social goals when economic agents have private information about their preferences. While economists have traditionally considered the problem of providing incentives for agents to fully reveal their preferences, such full revelation is often impractical or undesirable, for several reasons: (1) it may require a prohibitive amount of communication as measured in bits or real numbers, (2) it may be costly for agents to evaluate their complete preferences, and (3) the revealed information may be exploited by the designer or other agents. Thus, we consider the question: What is the minimal information that must be elicited from the agents in order to achieve the goals? Note that the question arises even if agents can be counted on to report truthfully.

Segal2007 shows that for a large class of social problems, any minimally informative way to verify that a given alternative is desirable is equivalent to giving each agent a “budget set”—a subset of the social alternatives (which could in general be described by personalized nonlinear prices), and asking each agent to verify that the proposed alternative is optimal to him within his budget set. Therefore, any communication mechanism that yields a solution to the social problem must also yield a supporting price equilibrium.

This result formalizes Hayek’s insight about the role of prices as minimal communication needed to solve the social coordination problems. The class of problems for which price revelation is necessary proves quite large. For example, it includes such social goals as exact or approximate efficiency, voluntary participation, stability to group deviations, and some notions of fairness. For such goals, price revelation is necessary regardless of the preference domain, which allows for nonconvexities or discrete decisions (eg. as in combinatorial auctions or matching problems). On the other hand, the particular form of prices to be used depends on the problem.

Segal2007 suggests an algorithm for deriving the form of price equilibria that verify the solution of a given problem with minimal information revelation. Applied to several well-known social problems, the algorithm generates the price equilibrium concepts that have been proposed for these problems. The necessity of revealing such prices bounds below the communication costs of the problem, measured in bits (“communication complexity”), real numbers (“dimension of message spaces”), evaluation costs, or in other ways. These results indicate which problems can be solved in a practical way and which problems cannot, and what role prices have in mechanisms that solve them.

This chapter outlines the results described above, a substantial body of related work in both economics and computer science, and potential extensions. In particular, it discusses the additional communication cost of providing incentives, the use of distributed communication to reduce individual agents’ communication costs, the role of prices in achieving probabilistic (average-case) social goals, and in problems with interdependent values.