The Communication Requirements of of Social Choice Rules and Supporting Budget Sets

The paper examines the communication requirements of social choice rules when the (sincere) agents privately know their preferences. It shows that for a large class of choice rules, any communication verifying that an alternative is in the rule must reveal supporting budget sets for the agents such that the optimality of the proposed alternative to all agents within their respective budget set in itself verifies the alternative. We characterize the budget equilibria that are the minimally informative messages verifying a given choice rule. This characterization is used to identify the communication burden of choice rules, measured with the number of transmitted bits or real variables. Applications include efficiency in convex economies, exact or approximate surplus maximization in combinatorial auctions, the core in indivisible good economies, and stable many-to-one matchings.