Theory Seminar

Impossibility Theorems and the Universal Algebraic Toolkit

Yixin XuPhD studentRutgers University

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.

Joint with Mario Szegedy
Yixin Xu is a PhD student in the Computer Science department at Rutgers University under the supervision of Mario Szegedy. His main interests are the algebraic theory of constant satisfaction
problems and quantum computing. He has received the best student paper award in the 8th International Computer Science Symposium in Russia,
CSR 2013.

Sponsored by