[...]


[...] Recalling the social choice setting of Chapter 2.5, consider a $2$candidate, $n$voter election using a monotone voting rule $f : \{1,1\}^n \to \{1,1\}$. We assume the impartial culture assumption (that the votes are independent and uniformly random), but with a twist: one of the candidates, say $b \in \{1,1\}$, is able to secretly bribe $k$ [...] Perhaps the most common generalized domain in analysis of boolean functions is the case of the hypercube with “biased” bits. [...] In this section we will revisit a number of combinatorial/probabilistic notions and show that for functions $f \in L^2(\Omega^n, \pi^{\otimes n})$, these notions have familiar Fourier formulas which don’t depend on the Fourier basis. [...] Given a voting rule $f : \{1,1\}^n \to \{1,1\}$ it’s natural to try to measure the “influence” or “power” of the $i$th voter. One can define this to be the “probability that the $i$th vote affects the outcome”. [...] 

Copyright © 2014 Ryan O'Donnell  All Rights Reserved 
Recent comments