Random Dictators with a Random Referee: Constant Sample Complexity Mechanisms for Social Choice

Brandon Fain, Ashish Goel, Kamesh Munagala +1

We study social choice mechanisms in an implicit utilitarian framework with a metric constraint, where the goal is to minimize \textit{Distortion}, the worst case social cost of an…