§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 \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 1 For $n$ odd, the majority function $\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$ is a majority 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 2 The 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 3 The $i$th dictator function $\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 4 A function $f : \{-1,1\}^n \to \{-1,1\}$ is called a $k$-junta for $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 5 A function $f : \{-1,1\}^n \to \{-1,1\}$ is called a weighted majority or (linear) threshold function if 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 6 The depth-$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 7 The tribes function 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 8 We say that a function $f : \{-1,1\}^n \to \{-1,1\}$ is:

  • monotone if $f(x) \leq f(y)$ whenever $x \leq y$ coordinate-wise;
  • odd if $f(-x) = -f(x)$;
  • unanimous if $f(1, \dots, 1) = 1$ and $f(-1, \dots, -1) = -1$;
  • symmetric if $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 9 The 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 10 A function $f : \{-1,1\}^n \to \{-1,1\}$ is transitive-symmetric if 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 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. One might also consider it as a model for the votes of just the “undecided” or “party-independent” voters.

8 comments to §2.1: Social choice functions

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

  • Lior Silberman

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

      • Lior Silberman

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

  • Hamidreza Jahanjou

    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?

Leave a Reply to Ryan O'Donnell 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>