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.

Arrow’s Theorem was the field’s first major result; Arrow proved it in 1950 [Arr50] under the extra assumption of monotonicity (and with a minor error [Bla57]), with the refined version appearing in 1963 [Arr63]. He was awarded the Nobel Prize for this work in 1972. May’s Theorem is from 1952 [May52]. Guilbaud’s Formula is also from 1952 [Gui52], though Guilbaud only stated it in a footnote and wrote that it is computed “by the usual means in combinatorial analysis”. The first published proof appears to be due to Garman and Kamien [GK68]; they also introduced the impartial culture assumption. The term “junta” appears to have been introduced by [PRS01].

The notion of influence $\mathbf{Inf}_i[f]$ was originally introduced by the geneticist Penrose [Pen46], who observed that $\mathbf{Inf}_i[\mathrm{Maj}_n] \sim \frac{\sqrt{2/\pi}}{\sqrt{n}}$. It was rediscovered by the lawyer Banzhaf in 1965 [Ban65]; he sued the Nassau County (NY) Board after proving that the voting system it used (the one in Exercise 2.8) gave some towns zero influence. Influence is sometimes referred to as the Banzhaf, Penrose–Banzhaf, or Banzhaf–Coleman index (Coleman being another rediscoverer [Col71]). Influences were first studied in the computer science literature by Ben-Or and Linial [BL85]; they introduced also introduced “tribes” as an example of a function with constant variance yet small influences. The Fourier formulas for influence may have first appeared in [CGG87].

Total influence of boolean functions has long been studied in combinatorics, since it is equivalent to edge-boundary size for subsets of the Hamming cube. For example, the edge-isoperimetric inequality was first proved by Harper in 1964 [Har64]. In the context of boolean functions, Karpovsky [Kar76] proposed $\mathbf{I}[f]$ as a measure of the computational complexity of $f$ and Hurst, Miller, and Muzio [HMM82] gave the Fourier formula $\sum_S |S|\widehat{f}(S)^2$. The terminology “Poincaré Inequality” comes from the theory of functional inequalities and Markov chains; the inequality is equivalent to the spectral gap for the discrete cube graph.

The noise stability of boolean functions was first studied explicitly by Benjamini, Kalai, and Schramm in 1999 [BKS99], though it plays an important role in the earlier work of Håstad [Has97]. See [O'D03] for a survey. The noise operator was introduced by Bonami [Bon70] and independently by Beckner [Bec75], who used the notation $\mathrm{T}_\rho$ which was standardized by [KKL88]. For nonnegative noise rates it’s often natural to use the alternate parameterization $\mathrm{T}_{e^{-t}}$ for $t \in [0,\infty]$.

The Fourier approach to Arrow’s Theorem is due to Kalai [Kal02]; he also proved Theorem 56 and Corollary 59. The FKN Theorem is from [FKN02]; the observation from Exercise 2.42 is due to Kindler.

The polarizations from Exercise 2.45 originate in [Kle66]. Exercise 2.46 is a theorem of Enflo from 1970 [Enf70]. Exercise 2.48 is a theorem of Latala and Oleszkiewicz [LO94]. In Exercise 2.49, part (b) is from [MO05]; part (c) was conjectured by Yang [Yan04] and proved in [OW11]. Exercise 2.50 is a polishing of the 1987 work by Chor and Geréb-Graus [CGG87,CGG88], a precursor of the KKL Theorem. The weaker Exercise 2.25 is also due to them and Alon independently.

2 comments to Chapter 2 notes

Leave a Reply to Chin Ho Lee Cancel reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>