Sharp Thresholds for Monotone Non Boolean Functions and Social Choice Theory

Gil Kalai, Elchanan Mossel

Abstract

A key fact in the theory of Boolean functions $f : \{0,1\}^n \to \{0,1\}$ is that they often undergo sharp thresholds. For example: if the function $f : \{0,1\}^n \to \{0,1\}$ is monotone and symmetric under a transitive action with $\mathbb{E}_p[f] = \epsilon$ and $\mathbb{E}_q[f] = 1-\epsilon$ then $q-p \to 0$ as $n \to \infty$. Here $\mathbb{E}_p$ denotes the product probability measure on $\{0,1\}^n$ where each coordinate takes the value $1$ independently with probability $p$. The fact that symmetric functions undergo sharp thresholds is important in the study of random graphs and constraint satisfaction problems as well as in social choice. In this paper, we prove sharp thresholds for monotone functions taking values in arbitrary finite sets. We also provide examples of applications of the results to social choice and to random graph problems. Among the applications is an analog for Condorcet's jury theorem and an indeterminacy result for a large class of social choice functions.

Introduction

In statistical mechanics, random graph theory, and social choice, systems often exhibit "phase transitions." These are points where a marginal change in input parameters leads to a dramatic, discontinuous shift in the global outcome. In the context of Boolean functions—where outcomes are binary (0 or 1)—this phenomenon is known as a "sharp threshold." While the mathematical foundations for Boolean sharp thresholds are well-established, many real-world systems involve multiple possible states or candidates.

This research extends the theory of sharp thresholds to functions mapping to arbitrary finite sets. By moving beyond the binary constraint, the authors provide a more robust framework for understanding complex decision-making processes and network behaviors where multiple outcomes are possible.

Theoretical Framework and Methodology

The study of sharp thresholds relies on relating the "sharpness" of a transition to the "influence" of individual variables. To extend this to non-Boolean functions, the authors utilize several advanced tools from discrete Fourier analysis and probability theory:

  • Generalization of Russo’s Formula: The authors derive a version of Russo’s formula applicable to non-Boolean functions. This formula is critical as it quantifies how the expected value of a function changes relative to the probability parameters of the input.
  • Efron-Stein Decomposition: This method is employed to decompose the variance of functions over product spaces, allowing the authors to manage the increased complexity of non-Boolean output sets.
  • Talagrand’s Influence Bounds and Hypercontractivity: By generalizing Michel Talagrand’s results on the sum of influences, the authors prove that symmetric monotone functions must possess a large total influence. This large influence is the mathematical driver that necessitates a sharp threshold as the number of participants ($n$) increases.

Key Insights in Social Choice

The theoretical results yield significant implications for social choice theory, particularly regarding how groups aggregate information and reach consensus.

Condorcet’s Jury Theorem for $q$ Candidates

The classical Condorcet Jury Theorem suggests that if each member of a group has a slight bias toward a "correct" binary choice, the group's collective decision will be correct with near certainty as the group size grows. This paper provides a rigorous analog for elections with $q$ candidates. It demonstrates that even a minimal bias—specifically on the order of $O(\frac{\log \log n}{\log n})$—is sufficient to ensure a landslide victory for a candidate in any fair, symmetric voting system.

Indeterminacy and Voting Paradoxes

The authors also explore the limits of social choice rules. They show that for large populations, rules satisfying standard axioms (such as the Independence of Rejected Alternatives) can lead to "complete indeterminacy." This suggests that in certain high-dimensional choice environments, almost any collective behavior can emerge, extending previous work on voting paradoxes and the inherent instability of certain preference aggregation rules.

Results and Applications

The Threshold Bound

The primary mathematical result is the proof that for a symmetric monotone function, the "threshold interval"—the range of input probability where the outcome remains uncertain—is bounded by $O\left(\frac{\log \log n}{\log n}\right)$. As the number of inputs $n$ approaches infinity, this interval shrinks to zero, confirming the existence of a sharp threshold.

Information Aggregation

The findings confirm that symmetric voting systems are highly efficient at aggregating information. In a race with $q$ candidates, a lead of only $O\left(\frac{\log \log n}{\log n}\right)$ in individual preference probability is enough to guarantee that candidate's election with probability $1 - \epsilon$.

Graph Properties

Beyond social choice, the results apply to monotone graph properties in edge-colored graphs. This demonstrates that phase transitions are not limited to simple connectivity or reachability in binary graphs but are a fundamental feature of more complex, multi-colored network structures.

Limitations and Future Directions

While the paper establishes a new bound for non-Boolean thresholds, the authors note that the $O\left(\frac{\log \log n}{\log n}\right)$ bound may not be optimal. In the Boolean case, the bound is a tighter $O(1/\log n)$. The authors conjecture that the non-Boolean case should ultimately match this Boolean efficiency, though proving this would require more specialized influence sum bounds.

Additionally, the current work focuses on systems with transitive symmetry (where all participants are treated equally). Future research is needed to determine how these thresholds behave in systems with weaker symmetry or more structured, non-symmetric influence patterns, which are common in real-world social and biological networks.

Summary updated

Abstract

A key fact in the theory of Boolean functions $f : \{0,1\}^n \to \{0,1\}$ is that they often undergo sharp thresholds. For example: if the function $f : \{0,1\}^n \to \{0,1\}$ is monotone and symmetric under a transitive action with $\E_p[f] = \eps$ and $\E_q[f] = 1-\eps$ then $q-p \to 0$ as $n \to \infty$. Here $\E_p$ denotes the product probability measure on $\{0,1\}^n$ where each coordinate takes the value $1$ independently with probability $p$. The fact that symmetric functions undergo sharp thresholds is important in the study of random graphs and constraint satisfaction problems as well as in social choice.In this paper we prove sharp thresholds for monotone functions taking values in an arbitrary finite sets. We also provide examples of applications of the results to social choice and to random graph problems. Among the applications is an analog for Condorcet's jury theorem and an indeterminacy result for a large class of social choice functions.
BibTeX
@article{kalai2015sharp,
  author = {Gil Kalai and Elchanan Mossel},
  title = {{Sharp Thresholds for Monotone Non Boolean Functions and Social Choice Theory}},
  journal = {Math. Oper. Res.},
  year = {2015},
  doi = {10.1287/moor.2014.0703},
}

Loading related content...

Figure