Abstract: Group decision making, a.k.a. social choice or collective decision making, studies how to aggregate agents' preferences to make a collective decision. It is critical in many scenarios in human society and multi-agent systems. The difficulty of designing desirable aggregation 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.

Motivated by AI-powered group decision-making, we take a worst-average-case approach to propose a natural, general, and more realistic semi-random model that resembles the celebrated smoothed analysis under semi-random models. We characterize the conditions and rates for the semi-random likelihood of the impossibility of transitivity, the impossibility of fairness, and the impossibility of strategy-proofness to vanish. Straightforward applications of our theorems address long-standing open questions. Our results illustrate the smoothed and semi-random possibilities of AI-powered group decision-making and help build a more realistic foundation of social choice beyond worst cases.

Bio: Lirong Xia is an associate professor in the Department of Computer Science at Rensselaer Polytechnic Institute (RPI). 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, a Rensselaer James M. Tien'66 Early Career Award, and was named one of AI's 10 to watch by IEEE Intelligent Systems.