The Communication Requirements of Social Choice Rules and Supporting Budget Sets
Ilya Segal
Department of Economics
Stanford University
Wednesday, May 11, 2005
4:30 - 5:45 PM
Terman Engineering Center, Room 453
Abstract:
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 communication mechanism realizing the choice rule
must find 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
(budget equilibria) verifying it. This characterization is used to
identify the amount of communication needed to realize a choice rule,
measured with the number of trans mitted 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.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html