§9.6: Highlight: The Kahn–Kalai–Linial Theorem

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$ [...]

§2.1: Social choice functions

In this section we describe some rudiments of the mathematics of social choice, a topic studied by economists, political scientists, mathematicians, and computer scientists. The fundamental question in this area is how best to aggregate the opinions of many agents. Examples where this problem arises include citizens voting in an election, committees deciding on [...]