Date:
Location:
Lirong Xia (RPI) will be speaking over Zoom on:
The Smoothed and Semi-Random Possibilities of Social Choice
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. A prominent challenge in designing desirable social choice mechanisms is 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 for going beyond a few voting rules and a few distributions are lacking.
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 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 smoothedand semi-random possibilities of social choice, and help build a more realistic foundation of social choice that goes beyond worst cases.
The talk is based on the following papers:
https://arxiv.org/abs/2006.06875