Sequential deliberation for social choice

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Fain, B; Goel, A; Munagala, K; Sakshuwong, S

Published Date

  • January 1, 2017

Published In

Volume / Issue

  • 10660 LNCS /

Start / End Page

  • 177 - 190

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 13 (ISBN-13)

  • 9783319719238

Digital Object Identifier (DOI)

  • 10.1007/978-3-319-71924-5_13

Citation Source

  • Scopus