Chapter 2: Basic concepts and social choice « Analysis of Boolean Functions

Chapter 2 notes

The mathematical study of social choice began in earnest in the late 1940s; see Riker [Rik61] for an early survey or the compilation [BGR09] for some modern results.

[...]

Chapter 2 exercises, continued

[...]

§2.5: Highlight: Arrow’s Theorem

When there are just $2$ candidates, the majority function possesses all of the mathematical properties that seem desirable in a voting rule (e.g., May’s Theorem and Theorem 32). Unfortunately, as soon as there are $3$ (or more) candidates the problem of social choice becomes much more difficult. For example, suppose we have candidates $a$, [...]

§2.4: Noise stability

Suppose $f : \{-1,1\}^n \to \{-1,1\}$ is a voting rule for a $2$-candidate election. Making the impartial culture assumption, the $n$ voters independently and uniformly randomly choose their votes ${\boldsymbol{x}} = ({\boldsymbol{x}}_1, \dots, {\boldsymbol{x}}_n)$. Now imagine that when each voter goes to the ballot box there is some chance that their vote is misrecorded.

[...]

§2.3: Total influence

A very important quantity in the analysis of a boolean function is the sum of its influences.

Definition 26 The total influence of $f : \{-1,1\}^n \to {\mathbb R}$ is defined to be \[ \mathbf{I}[f] = \sum_{i=1}^n \mathbf{Inf}_i[f]. \]

[...]

§2.2: Influences and derivatives

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”.

[...]

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