The Communication Requirements of Social Choice Rules and Supporting Budget Sets

by Ilya Segal
Journal of Economic Theory 2007

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 minimally informative way to verify that a given alternative is
in the choice rule is by verifying a ìbudget equilibriumî, i.e., that the alternative is
optimal to each agent within a ìbudget setî given to him. Therefore, any communi-
cation mechanism realizing the choice rule must Önd a supporting budget equilibrium.
We characterize the class of choice rules that have this property. Furthermore, for
any rule from the class, we characterize the minimally informative messages (bud-
get equilibria) verifying it. This characterization is used to identify the amount of
communication needed to realize a choice rules, measured with the number of trans-
mitted bits or real variables. Applications include e¢ ciency in convex economies,
exact or approximate surplus maximization in combinatorial auctions, the core in
indivisible-good economies, and stable many-to-one matchings.