Master's Defense

Sequential Deliberation for Social Choice

Speaker:Brandon Fain
btfain at cs.duke.edu
Date: Friday, November 3, 2017
Time: 12:00pm - 2:00pm
Location: North 311, Duke

Abstract

I present a randomized social choice mechanism designed to be practical in decision spaces too large for traditional ordinal voting. The protocol, sequential deliberation, is decentralized, simple, scalable, and does not require the mediator to have any knowledge of the decision space. In this iterative method, successive pairs of agents bargain over the decision space using the previous decision as a disagreement alternative. I 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. I also give lower bounds on simpler classes of mechanisms to justify design choices, and finish by discussing generalizations to general metric spaces.
Advisor(s): Kamesh Munagala
Committee: Pankaj Agarwal, Vincent Conitzer, Ashish Goel