The Smoothed and Semi-Random Possibilities of Social Choice

Speaker:              Lirong Xia

Time:                   10:00, Sept. 23rd.

Location:             SIST 1A-200

Host:                    Prof. Dengji Zhao

Abstract:

Social choice studies how to aggregate individuals’ preferences into a collective decision. A recurring obstacle is the prevalence of worst-case paradoxes and impossibility theorems, such as Condorcet cycles, strategic manipulation, and incompatibility of various notions of fairness. Average-case analyses offer a more optimistic alternative, but many commonly-used probabilistic models have been criticized as unrealistic, and general tools that apply across voting rules and distributions are limited.

In this talk, I will talk about a natural semi-random framework, inspired by the smoothed analysis for algorithms, that bridges worst-case and average-case reasoning: an adversary selects a distribution of preference profile (instead of the profile itself). With this model, we characterize conditions and quantitative rates under which the likelihood of three classic barriers vanishes: Condorcet’s paradox; the ANR impossibility (simultaneously satisfying anonymity, neutrality, and resolvability); and Gibbard–Satterthwaite manipulability. Our proofs develop a new polyhedral approach that yields a unified way to analyze these phenomena beyond a few voting rules or distributions, resolving several long-standing open questions in more general settings. The results reveal the smoothed and semi-random possibilities for social choice that are invisible in worst-case analysis.

Bio:

Lirong Xia is a Professor of Computer Science at Rutgers University - New Brunswick and the Deputy Director of DIMACS (the Center for Discrete Mathematics and Theoretical Computer Science). He received his Ph.D. in Computer Science and M.A. in Economics from Duke University, and B.E. in Computer Science and Technology from Tsinghua University. His research focuses on the intersection of computer science and microeconomics.