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 \to \{-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 1For $n$ odd,themajorityfunction $\mathrm{Maj}_n : \{-1,1\}^n \to \{-1,1\}$ is defined by $\mathrm{Maj}_n(x) = \mathrm{sgn}(x_1 + x_2 + \cdots + x_n)$. (Occasionally, for $n$ even we say that $f$ isamajority function if $f(x)$ equals the sign of $x_1 + \cdots + x_n$ whenever this number is nonzero.)

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 $\mathsf{True}$ and $+1$ represents $\mathsf{False}$:

Definition 2The function $\mathrm{AND}_n : \{-1,1\}^n \to \{-1,1\}$ is defined by $\mathrm{AND}_n(x) = +1$ unless $x = (-1, -1, \dots, -1)$. The function $\mathrm{OR}_n : \{-1,1\}^n \to \{-1,1\}$ is defined by $\mathrm{OR}_n(x) = -1$ unless $x = (+1, +1, \dots, +1)$.

Another voting rule commonly encountered in practice:

Definition 3The $i$thdictatorfunction $\chi_i : \{-1,1\}^n \to \{-1,1\}$ is defined by $\chi_i(x) = x_i$.

Here we are simplifying notation for the singleton monomial from $\chi_{\{i\}}$ to $\chi_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 colourful terminology “dictator functions” to the more mathematically staid “projection functions”. Generalizing:

Definition 4A function $f : \{-1,1\}^n \to \{-1,1\}$ is called a$k$-juntafor $k \in {\mathbb N}$ if it depends on at most $k$ of its input coordinates; i.e., $f(x) = g(x_{i_1}, \dots, x_{i_k})$ for some $g : \{-1,1\}^k \to \{-1,1\}$ and $i_1, \dots, i_k \in [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 \to \{-1,1\}$ which are $1$-juntas is precisely $2n+2$: the $n$ dictators, the $n$ negated-dictators, and the $2$ constant functions $\pm 1$.

The European Union’s Council of Ministers adopts decisions based on a weighted majority voting rule:

Definition 5A function $f : \{-1,1\}^n \to \{-1,1\}$ is called aweighted majorityor(linear) threshold functionif it is expressible as $f(x) = \mathrm{sgn}(a_0 + a_1 x_1 + \cdots + a_n x_n)$ for some $a_0, a_1, \dots, a_n \in {\mathbb R}$.

In the exercises you will be asked to 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 6Thedepth-$d$ recursive majority of $n$function, denoted $\mathrm{Maj}_n^{\otimes d}$, is the boolean function of $n^d$ bits defined inductively as follows: $\mathrm{Maj}_n^{\otimes 1} = \mathrm{Maj}_n$, and $\mathrm{Maj}_n^{\otimes(d+1)}(x^{(1)}, \dots, x^{(n)}) = \mathrm{Maj}_n(\mathrm{Maj}^{\otimes d}_n(x^{(1)}), \dots, \mathrm{Maj}^{\otimes d}_n(x^{(n)}))$ for $x^{(i)} \in \{-1,1\}^{n^d}$.

In our last example of a $2$-candidate voting rule, the voters are divided into “tribes” of equal size and the outcome is $\mathsf{True}$ if and only if at least one tribe is unanimously in favour of $\mathsf{True}$. This rule is only somewhat plausible in practice, but it plays a very important role in the analysis of boolean functions:

Definition 7Thetribesfunction of width $w$ and size $s$, $\mathrm{Tribes}_{w,s} : \{-1,1\}^{sw} \to \{-1,1\}$, is defined by $\mathrm{Tribes}_{w,s}(x^{(1)}, \dots, x^{(s)}) = \mathrm{OR}_s(\mathrm{AND}_w(x^{(1)}), \dots, \mathrm{AND}_w(x^{(s)}))$, where $x^{(i)} \in \{-1,1\}^w$.

Here are some natural properties of $2$-candidate social choice functions which may be considered desirable:

Definition 8We say that a function $f : \{-1,1\}^n \to \{-1,1\}$ is:

monotoneif $f(x) \leq f(y)$ whenever $x \leq y$ coordinate-wise;oddif $f(-x) = -f(x)$;unanimousif $f(1, \dots, 1) = 1$ and $f(-1, \dots, -1) = -1$;symmetricif $f(x^\pi) = f(x)$ for all permutations $\pi \in S_n$ (using the notation from Exercise 1.29); 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 \to {\mathbb R}$.

Examples 9The majority function (for $n$ odd) has all four properties in Definition 8; indeed,May’s Theorem(an exercise in this chapter) 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 10A function $f : \{-1,1\}^n \to \{-1,1\}$ istransitive-symmetricif for all $i, i’ \in [n]$ there exists a permutation $\pi \in S_n$ taking $i$ to $i’$ such $f(x^\pi) = f(x)$ for all $x \in \{-1,1\}^n$. (In other words, the symmetry group of $f$ acts transitively on~$[n]$.)

Intuitively, a function is transitive-symmetric if any two coordinates $i, j \in [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 $\pm 1$. Of course, this presupposes the uniform probability distribution on votes.

Definition 11Theimpartial culture assumptionis 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. One might also consider it as a model for the votes of just the “undecided” or “party-independent” voters.

I am looking forward to getting to the proof of Kalai’s theorem, thanks for the nice site! As a comment, there is a more accurate wording for the intuitive explanation of transitive-symmetric… you may have no distinguished elements and yet non-transitivity, e.g. (taking another simpler setting) the permutation group generated by (12)(34)… I guess it is more like that no pair is distinguishable?

Hi David, you’re right — it wasn’t quite the most accurate explanation, even ‘intuitively’. Thanks.

“Transitive-symmetric” seems an awkward phrasing. In view of David’s comment, does it mean that the symmetry group of $f$ acts transitively or 2-transitively on $[n]$? In either case, perhaps you could add a clarifying remark which would be accessible to those who know this language.

Well, as the definition says, it just means transitively, not 2-transitively. It seems it’s hard to succinctly paraphrase the mathematical definition in a way that works for everyone! I mean the way I kind of think of it is that it’s an election scheme such that, if the designer came to you and said,

“Hey, I’ll do you a favour; before anyone else gets to decide, I’ll let you pick which voter number you want to be, anything from #1 to #n.”,

you would say,

“Well, it doesn’t matter to me.”

I understood the definition to mean transitive, except for David’s comment which mentioned 2-transitivity. Here’s a longer version of what I was trying to propose:

1. Right after the definition, there’s the sentence “Intuitively, …”. You could add after that another sentence like: “Formally, a function is transitive-symmetric if it is invariant under a transitive subgroup of $S_n$” or “Formally, a function is transitive-symmetric if its symmetry group acts transitively on $[n]$”. This merely repeats the definition, but for those members of the audience who know about transitive group actions makes it clear you are talking about 1-transitivity.

2. Is the term “transitive-symmetric” already standard in the literature? If not, perhaps “single-input-symmetric”, “voter-symmetric” or “1-transitive” would be better?

[I'd have proposed to simply call it "transitive", but probably a voting scheme ought to be "transitive" if when the voters prefer A to B and B to C they also prefer A to C]

It’s not completely standard terminology… using the word ‘transitive’ is standard, and I personally just refer to them as ‘transitive’ functions. But as you say, it’s a bit questionable to just call them ‘transitive’, so I went with ‘transitive symmetric’.

Hi, in definition 6. It seems to me that the recursive majority function should be defined as

Maj_n^{d+1}(x^{(1)}, …, x^{(n)}) = Maj_n(Maj_n^{d}(x^{(1)}), …, Maj_n^{d}(x^{(1)}))

x^{(i)}\in {+1, -1}^n. Am I right?

Fixed, thanks!