Opening Analysis of Boolean Functions: Applications in Social Choice
Analysis of Boolean Functions: Applications in Social Choice
- Length
- 14 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 3: Applications to social choice
Fourier analysis of Boolean functions models voting rules in two-candidate elections and evaluates voter influence. The lecture defines the Banzhaf power index as the probability of casting a pivotal vote and expresses it through Fourier coefficients. It builds on this framework to examine Arrow's Impossibility Theorem, the probability of Condorcet's paradox, and the KKL theorem on voter dictatorships. Finally, it outlines a generalization of Hoeffding's bound for higher-degree polynomials using hypercontractivity.

Your comment is kept while you sign up.Sign in
Expresses a voter's Banzhaf power as a sum of squared Fourier coefficients, then reaches Arrow and KKL.
Fourier analysis of Boolean functions models voting rules in two-candidate elections and evaluates voter influence. The lecture defines the Banzhaf power index as the probability of casting a pivotal vote and expresses it through Fourier coefficients. It builds on this framework to examine Arrow's Impossibility Theorem, the probability of Condorcet's paradox, and the KKL theorem on voter dictatorships. Finally, it outlines a generalization of Hoeffding's bound for higher-degree polynomials using hypercontractivity.
This lecture
Lecture 23 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.