Speaker: Yuval Flimus (Technion)


Title: Oligarchy testing

Abstract:
Arrow's impossibility theorem states that the only voting rule satisfying certain natural requirements is a dictatorship.
Gil Kalai showed that even if we relax some of these requirements so that they only hold with high probability, we are not getting genuine new voting rules.
Arrow's theorem is just one of many paradoxes in social choice theory.
Another example, from judgment aggregation, states that the only voting rules satisfying the equation

     f(x and y) = f(x) and f(y),     x,y in {0,1}^n

are oligarchies (ANDs).
Ilan Nehama asked whether relaxing this requirement so that it only holds with high probability can help.
He proved that the answer is negative - voting rules satisfying the relaxed condition must be close to an AND.
However, his result degrades with n, the number of voters.
We prove a similar result which is independent of n.
Our result can also be seen as the analog of linearity testing when changing + to *.

Joint work with Noam Lifshitz (HUJI), Dor Minzer (IAS) and Elchanan Mossel (MIT).