Sequential deliberation for social choice

Social choice is a normative study of designing protocols for collective decision making. However, in instances where the underlying decision space is too large or complex for ordinal voting, standard voting methods may be impractical. How then can we design a protocol - preferably decentralized, simple, scalable, and not requiring any special knowledge of the decision space - to reach consensus? We propose sequential deliberation as a natural solution to this problem. In this iterative method, successive pairs of agents bargain over the decision space using the previous decision as a disagreement alternative. We show that sequential deliberation finds a 1.208-approximation to the optimal social cost when the space of preferences define a median graph, coming very close to this value with only a small constant number of agents sampled from the population. We also give lower bounds on simpler classes of mechanisms to justify our design choices. We further show that sequential deliberation is ex-post Pareto efficient and has truthful reporting as an equilibrium of the induced extensive form game. Finally, we prove that for general metric spaces, the first and second moment of the distribution of social cost of the outcomes produced by sequential deliberation are also bounded by constants.

Duke Scholars

Author Brandon Fain Computer Science

Author Kamesh Munagala Computer Science