Skip to content Skip to navigation
Pre-Defense
5/27/2014 11:30 am
CoRE B(Room 305)

Impossibility Theorems and the Universal Algebraic Toolkit

Yixin Xu, Rutgers University

Defense Committee: Prof. Mario Szegedy (Chair), Prof. Eric Allender and Prof. Michael Saks

Abstract

We elucidate a close connection between the Theory of Judgment Aggregation and a relatively young but rapidly growing field of universal algebra, that was primarily developed to investigate constraint satisfaction problems. We show that theorems in the above field translate (often directly) to impossibility, classification and robustness theorems in social choice theory. We refine the classification of E. Dokow, R. Holzman of binary evaluations, complete their classification theorem for non-binary evaluations, give a new classification theorem for the majoritarian aggregator and show how Sen's well known theorem follows from it, define new aggregator classes and also prove theorems about them. We also give upper bounds on the complexity of computing if a domain is impossible or not.