The Semi-Random Possibilities of Social Choice

Lirong Xia
Rensselaer Polytechnic Institute

Time: 2021-12-03, 11 AM - 12 PM ET
Location: Zoom Only

Abstract Social choice studies how to aggregate agents’ preferences to make a collective decision. It plays a critical role in many group decision making scenarios in human society as well as in multi-agent systems. The difficulty of designing desirable social choice mechanisms has been widely acknowledged, partly due to the wide presence of worst-case paradoxes and impossibility theorems. While there is a large body of literature on using average-case analysis to circumvent the impossibilities, the models in previous work were criticized for being unrealistic, and technical tools to go beyond a few voting rules and a few distributions are lacking.

We take a worst average-case approach by proposing a natural, general, and more realistic semi-random model that resembles the celebrated smoothed analysis. We characterize the conditions and rates for the semi-random likelihood of Condorcet’s paradox, the ANR impossibility theorem, and the Gibbard-Satterthwaite theorem to vanish, by representing them as unions of polyhedra and characterizing the semi-random likelihood for a Poisson Multinomial Variable to be in the polyhedra. Straightforward applications of our theorems to the Impartial Culture distribution address long-standing open questions. Our results illustrate the semi-random possibilities of social choice, and help build a more realistic foundation of social choice that goes beyond worst cases.

Bio Lirong Xia is an associate professor in the Department of Computer Science at Rensselaer Polytechnic Institute (RPI). Prior to joining RPI in 2013, he was a CRCS fellow and NSF CI Fellow at the Center for Research on Computation and Society at Harvard University. He received his Ph.D. in Computer Science and M.A. in Economics from Duke University. His research focuses on the intersection of computer science and microeconomics. He is the recipient of an NSF CAREER award, a Simons-Berkeley Research Fellowship, the 2018 Rensselaer James M. Tien’66 Early Career Award, and was named as one of “AI’s 10 to watch” by IEEE Intelligent Systems.

Note: this talk will also be recorded