The Smoothed and Semi-Random Possibilities of Social Choice
Jeudi 5 février 2026Horaire : 14 h
Lirong Xia (Rutgers University-New Brunswick)
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, we propose 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. The talk is based on the following papers: https://arxiv.org/abs/2006.06875 https://arxiv.org/abs/2011.03791 https://arxiv.org/abs/2202.06411
Campus Pierre et Marie Curie, salle Jacques Pitrat (25-26/105)