1.7.Exercises and notes 41 Roth [Rot53](in the context of the cyclic group Z rather than F2).The work of Bellare et al.also gives additional analysis improving the results of Theorem 1.30 and Exercise 1.28.See also the work of Kaufman,Litsyn,and Xie [KLX10]for further slight improvement. In Exercise 1.1,the sortedness function was introduced by Ambainis [Amb03, LLS06];the hemi-icosahedron function was introduced by Kushilevitz [NW95]. The fast algorithm for computing the Fourier transform mentioned in Exer- cise 1.12 is due to Lechner [Lec63]. Copyright Ryan O'Donnell,2014
1.7. Exercises and notes 41 Roth [Rot53] (in the context of the cyclic group ❩N rather than ❋n 2 ). The work of Bellare et al. also gives additional analysis improving the results of Theorem 1.30 and Exercise 1.28. See also the work of Kaufman, Litsyn, and Xie [KLX10] for further slight improvement. In Exercise 1.1, the sortedness function was introduced by Ambainis [Amb03, LLS06]; the hemi-icosahedron function was introduced by Kushilevitz [NW95]. The fast algorithm for computing the Fourier transform mentioned in Exercise 1.12 is due to Lechner [Lec63]. Copyright © Ryan O’Donnell, 2014
Chapter 2 Basic concepts and social choice In this chapter we introduce a number of important basic concepts including influences and noise stability.Many of these concepts are nicely motivated using the language of social choice.The chapter is concluded with Kalai's Fourier-based proof of Arrow's Theorem. 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 com- puter scientists.The fundamental question in this area is how best to ag- gregate the opinions of many agents.Examples where this problem arises include citizens voting in an election,committees deciding on alternatives, and independent computational agents making collective decisions.Social choice theory also provides very appealing interpretations for a number of important functions and concepts in the analysis of Boolean functions. A Boolean function f:(-1,1)"-(-1,1)can be thought of as a voting rule or social choice function for an election with 2 candidates and n voters;it maps the votes of the voters to the winner of the election.Perhaps the most familiar voting rule is the majority function: Definition 2.1.For n odd,the majority function Majn (-1,1)"-(-1,1)is defined by Majn (x)=sgn(x1+x2+..+xn).(Occasionally,for n even we say that f is a majority function if f(x)equals the sign ofx1+.+xn whenever this number is nonzero.) 43 Copyright@Ryan O'Donnell,2014
Chapter 2 Basic concepts and social choice In this chapter we introduce a number of important basic concepts including influences and noise stability. Many of these concepts are nicely motivated using the language of social choice. The chapter is concluded with Kalai’s Fourier-based proof of Arrow’s Theorem. 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 alternatives, and independent computational agents making collective decisions. Social choice theory also provides very appealing interpretations for a number of important functions and concepts in the analysis of Boolean functions. A Boolean function f : {−1,1} n → {−1,1} can be thought of as a voting rule or social choice function for an election with 2 candidates and n voters; it maps the votes of the voters to the winner of the election. Perhaps the most familiar voting rule is the majority function: Definition 2.1. For n odd, the majority function Majn : {−1,1} n → {−1,1} is defined by Majn (x) = sgn(x1 + x2 + ··· + xn). (Occasionally, for n even we say that f is a majority function if f (x) equals the sign of x1 + ··· + xn whenever this number is nonzero.) 43 Copyright © Ryan O’Donnell, 2014
44 2.Basic concepts and social choice The Boolean AND and OR functions correspond to voting rules in which a certain candidate is always elected unless all voters are unanimously op- posed.Recalling our somewhat nonintuitive convention that-1 represents True and +1 represents False: Definition 2.2.The function AND:{-1,1)n-(-1,1}is defined by AND(x)= +1 unlessx=(-1,-1,...,-1).The function ORn :(-1,1)"-(-1,1)is defined by0Rn(x)=-1 unless x=(+1,+1,,+1). Another voting rule commonly encountered in practice: Definition 2.3.The ith dictator function xi:(-1,1)"-(-1,1)is defined by Xi(x)=xi. Here we are simplifying notation for the singleton monomial from x)to Xi.Even though they are extremely simple functions,the dictators play a very important role in analysis of Boolean functions;to highlight this we prefer the colorful terminology "dictator functions"to the more mathematically staid “projection functions'”.Generalizing: Definition 2.4.A function f:(-1,1)"-(-1,1)is called a k-junta for k Nif it depends on at most k of its input coordinates;i.e.,f(x)=g(xi,...,xi)for some g:(-1,1-(-1,1)and i1,...,ie[n].Informally,we say that f is a “junta”if it depends on only a“constant'”number of coordinates. For example,the number of functions f:{-1,1)2-(-1,1)which are 1-juntas is precisely 2n+2:the n dictators,the n negated-dictators,and the 2 constant functions±l. The European Union's Council of Ministers adopts decisions based on a weighted majority voting rule: Definition 2.5.A function f:(-1,1)"-(-1,1)is called a weighted majority or (linear)threshold function if it is expressible as f(x)=sgn(ao+ax1+...+ anxn)for some ao,a1,...,an ER. Exercise 2.2 has you verify that majority,AND,OR,dictators,and constants are all linear threshold functions. The leader of the United States (and many other countries)is elected via a kind of"two-level majority".We make a natural definition along these lines: Definition 2.6.The depth-d recursive majority of n function,denoted Majd, is the Boolean function of nd bits defined inductively as follows:Maj= Majn,and Maj(d+D(=Majn(Majd()...,Majd())for {-1,1n Copyright Ryan O'Donnell,2014
44 2. Basic concepts and social choice The Boolean AND and OR functions correspond to voting rules in which a certain candidate is always elected unless all voters are unanimously opposed. Recalling our somewhat nonintuitive convention that −1 represents True and +1 represents False: Definition 2.2. The function ANDn : {−1,1} n → {−1,1} is defined by ANDn(x) = +1 unless x = (−1,−1,...,−1). The function ORn : {−1,1} n → {−1,1} is defined by ORn(x) = −1 unless x = (+1,+1,...,+1). Another voting rule commonly encountered in practice: Definition 2.3. The ith dictator function χi : {−1,1} n → {−1,1} is defined by χi(x) = xi . Here we are simplifying notation for the singleton monomial from χ{i} to χi . Even though they are extremely simple functions, the dictators play a very important role in analysis of Boolean functions; to highlight this we prefer the colorful terminology “dictator functions” to the more mathematically staid “projection functions”. Generalizing: Definition 2.4. A function f : {−1,1} n → {−1,1} is called a k-junta for k ∈ ◆ if it depends on at most k of its input coordinates; i.e., f (x) = g(xi1 ,..., xik ) for some g : {−1,1} k → {−1,1} and i1,...,ik ∈ [n]. Informally, we say that f is a “junta” if it depends on only a “constant” number of coordinates. For example, the number of functions f : {−1,1} n → {−1,1} which are 1-juntas is precisely 2n+2: the n dictators, the n negated-dictators, and the 2 constant functions ±1. The European Union’s Council of Ministers adopts decisions based on a weighted majority voting rule: Definition 2.5. A function f : {−1,1} n → {−1,1} is called a weighted majority or (linear) threshold function if it is expressible as f (x) = sgn(a0 + a1x1 +··· + anxn) for some a0,a1,...,an ∈ ❘. Exercise 2.2 has you verify that majority, AND, OR, dictators, and constants are all linear threshold functions. The leader of the United States (and many other countries) is elected via a kind of “two-level majority”. We make a natural definition along these lines: Definition 2.6. The depth-d recursive majority of n function, denoted Maj⊗d n , is the Boolean function of n d bits defined inductively as follows: Maj⊗1 n = Majn , and Maj⊗(d+1) n (x (1) ,..., x (n) ) = Majn (Maj⊗d n (x (1)),...,Maj⊗d n (x (n) )) for x (i) ∈ {−1,1} n d . Copyright © Ryan O’Donnell, 2014
2.1.Social choice functions 45 In our last example of a 2-candidate voting rule,the voters are divided into "tribes"of equal size and the outcome is True if and only if at least one tribe is unanimously in favor of True.This rule is only somewhat plausible in practice, but it plays a very important role in the analysis of Boolean functions: Definition 2.7.The tribes function of width w and sizes,Tribess:(-1,1)s (-1,1],isdefinedbyTribesw.s(x)=OR:(AND(x),....AND(x(), where x(i)E(-1,1). Here are some natural properties of 2-candidate social choice functions which may be considered desirable: Definition 2.8.We say that a function f:(-1,1)"-(-1,1)is: ·monotone if f(x)≤f(y)whenever x≤y coordinate--wise; ·odd if f(-x)=-f(x; unanimous if f(1,...,1)=1 and f(-1,...,-1)=-1; symmetric if f(x")=f(x)for all permutations eSn(using the notation from Exercise 1.30);i.e.,f(x)only depends on the number of 1's in x. The definitions of monotone,odd,and symmetric are also natural for f: {-1,1m-R Example 2.9.The majority function (for n odd)has all four properties in Definition 2.8;indeed,May's Theorem(Exercise 2.3)states that it is the only monotone,odd,symmetric function.The dictator functions have the first three properties above,as do recursive majority functions.The AND and OR functions are monotone,unanimous,and symmetric,but not odd.The tribes functions are monotone and unanimous;although they are not symmetric they have an important weaker property: Definition 2.10.A function f:(-1,1)n-{-1,1)is transitive-symmetric if for all i,i'e[n]there exists a permutation eSn taking i to i'such f(x")=f(x) for allxe(-1,1)7. Intuitively,a function is transitive-symmetric if any two coordinates i,je[n] are“equivalent” One more natural desirable property of a 2-candidate voting rule is that it be unbiased as defined in Chapter 1.4,i.e.,"equally likely"to elect +1.Of course,this presupposes the uniform probability distribution on votes. Definition 2.11.The impartial culture assumption is that the n voters'pref- erences are independent and uniformly random. Although this assumption might seem somewhat unrealistic,it gives a good basis for comparing voting rules in the absence of other information. Copyright@Ryan O'Donnell,2014
2.1. Social choice functions 45 In our last example of a 2-candidate voting rule, the voters are divided into “tribes” of equal size and the outcome is True if and only if at least one tribe is unanimously in favor of True. This rule is only somewhat plausible in practice, but it plays a very important role in the analysis of Boolean functions: Definition 2.7. The tribes function of width w and size s, Tribesw,s : {−1,1} sw → {−1,1}, is defined by Tribesw,s(x (1) ,..., x (s) ) = ORs(ANDw(x (1)),...,ANDw(x (s) )), where x (i) ∈ {−1,1} w. Here are some natural properties of 2-candidate social choice functions which may be considered desirable: Definition 2.8. We say that a function f : {−1,1} n → {−1,1} is: • monotone if f (x) ≤ f (y) whenever x ≤ y coordinate-wise; • odd if f (−x) = −f (x); • unanimous if f (1,...,1) = 1 and f (−1,...,−1) = −1; • symmetric if f (x π ) = f (x) for all permutations π ∈ Sn (using the notation from Exercise 1.30); i.e., f (x) only depends on the number of 1’s in x. The definitions of monotone, odd, and symmetric are also natural for f : {−1,1} n → ❘. Example 2.9. The majority function (for n odd) has all four properties in Definition 2.8; indeed, May’s Theorem (Exercise 2.3) states that it is the only monotone, odd, symmetric function. The dictator functions have the first three properties above, as do recursive majority functions. The AND and OR functions are monotone, unanimous, and symmetric, but not odd. The tribes functions are monotone and unanimous; although they are not symmetric they have an important weaker property: Definition 2.10. A function f : {−1,1} n → {−1,1} is transitive-symmetric if for all i,i 0 ∈ [n] there exists a permutation π ∈ Sn taking i to i 0 such f (x π ) = f (x) for all x ∈ {−1,1} n . Intuitively, a function is transitive-symmetric if any two coordinates i, j ∈ [n] are “equivalent”. One more natural desirable property of a 2-candidate voting rule is that it be unbiased as defined in Chapter 1.4, i.e., “equally likely” to elect ±1. Of course, this presupposes the uniform probability distribution on votes. Definition 2.11. The impartial culture assumption is that the n voters’ preferences are independent and uniformly random. Although this assumption might seem somewhat unrealistic, it gives a good basis for comparing voting rules in the absence of other information. Copyright © Ryan O’Donnell, 2014
46 2.Basic concepts and social choice One might also consider it as a model for the votes of just the "undecided"or “party-independent”voters. 2.2.Influences and derivatives Given a voting rule f:(-1,1)n-(-1,1)it's natural to try to measure the “influence”or“power”of the ith voter..One can define this to be the“probability that the ith vote affects the outcome". Definition 2.12.We say that coordinate ie [n]is pivotal for f:(-1,1)"- {-1,1)on input x if f(x)f(x).Here we have used the notation xi for the string(x1,...,xi-1,-xi,xi+1,...,xn). Definition 2.13.The influence of coordinate i on f:(-1,1)"(-1,1}is de- fined to be the probability that i is pivotal for a random input: Infi[f]=Pr [f(x)f(xi)]. x-{-1.1}n Influences can be equivalently defined in terms of"geometry"of the Ham- ming cube: Fact 2.14.For f:(-1,1yn-(-1,1),the influence Infilf]equals the fraction of dimension-i edges in the Hamming cube which are boundary edges.Here (x,y)is a dimension-i edge ify=x;it is a boundary edge if f(x)#f(y). (+1+1,+1) (-1,-1.-1) Figure 2.1.Boundary edges of the Majg function Example 2.15.For the ith dictator function xi we have that coordinate i is pivotal for every input x;hence Infi[xi]=1.On the other hand,ifji then coordinate j is never pivotal;hence Infi[xi]=0 for j i.Note that the same two statements are true about the negated-dictator functions.For the constant functions +1,all influences are 0.For the ORn function,coordi- nate 1 is pivotal for exactly two inputs,(-1,1,1,...,1)and (1,1,1,...,1);hence Infi[ORn]=21-.Similarly,Infi[ORn]=Infi[ANDn]=21-7 for all ie [n]. The Majs is depicted in Figure 2.1;the points where it's +1 are colored gray and the points where it's-1 are colored white.Its boundary edges are high- lighted in black;there are 2 of them in each of the 3 dimensions.Since there Copyright@Ryan O'Donnell,2014
46 2. Basic concepts and social choice One might also consider it as a model for the votes of just the “undecided” or “party-independent” voters. 2.2. Influences and derivatives Given a voting rule f : {−1,1} n → {−1,1} it’s natural to try to measure the “influence” or “power” of the ith voter. One can define this to be the “probability that the ith vote affects the outcome”. Definition 2.12. We say that coordinate i ∈ [n] is pivotal for f : {−1,1} n → {−1,1} on input x if f (x) 6= f (x ⊕i ). Here we have used the notation x ⊕i for the string (x1,..., xi−1,−xi , xi+1,..., xn). Definition 2.13. The influence of coordinate i on f : {−1,1} n → {−1,1} is de- fined to be the probability that i is pivotal for a random input: Infi[f ] = Pr x∼{−1,1} n [f (x) 6= f (x ⊕i )]. Influences can be equivalently defined in terms of “geometry” of the Hamming cube: Fact 2.14. For f : {−1,1} n → {−1,1}, the influence Infi[f ] equals the fraction of dimension-i edges in the Hamming cube which are boundary edges. Here (x, y) is a dimension-i edge if y = x ⊕i ; it is a boundary edge if f (x) 6= f (y). Figure 2.1. Boundary edges of the Maj3 function Example 2.15. For the ith dictator function χi we have that coordinate i is pivotal for every input x; hence Infi[χi] = 1. On the other hand, if j 6= i then coordinate j is never pivotal; hence Infj[χi] = 0 for j 6= i. Note that the same two statements are true about the negated-dictator functions. For the constant functions ±1, all influences are 0. For the ORn function, coordinate 1 is pivotal for exactly two inputs, (−1,1,1,...,1) and (1,1,1,...,1); hence Inf1[ORn] = 2 1−n . Similarly, Infi[ORn] = Infi[ANDn] = 2 1−n for all i ∈ [n]. The Maj3 is depicted in Figure 2.1; the points where it’s +1 are colored gray and the points where it’s −1 are colored white. Its boundary edges are highlighted in black; there are 2 of them in each of the 3 dimensions. Since there Copyright © Ryan O’Donnell, 2014