Sharp Thresholds for Monotone Non-Boolean Functions and Social Choice Theory

Gil Kalai, Elchanan Mossel

TL;DR

This paper extends the concept of "sharp thresholds" from simple yes/no (Boolean) functions to more complex functions with multiple outcomes. They prove that even for these richer functions, a small change in input probability can lead to a dramatic shift in the outcome, a phenomenon crucial for understanding how societies make decisions and how random graphs form.

What Problem Does This Paper Address?

In the study of Boolean functions (those with binary outputs, like "yes" or "no"), a key phenomenon is the existence of "sharp thresholds." This means that a small change in the probability of certain inputs can cause the function's output to flip from almost always "no" to almost always "yes." This has significant implications for understanding random graph properties and how information is aggregated in systems like voting. However, many real-world scenarios involve more than two possible outcomes (e.g., choosing among multiple candidates). This paper addresses the question of whether this sharp threshold phenomenon also exists for monotone functions that map to arbitrary finite sets, and what its implications are for social choice theory.

Methods

The paper builds upon existing work on sharp thresholds for Boolean functions, particularly using techniques related to influences and Russo's formula. They generalize these concepts to functions with outputs in an arbitrary finite set $A$. A key technique involves analyzing the derivative of the expected output of the function with respect to probability measures on the input space. They leverage a generalization of Talagrand's result on L2 influence sums and hypercontractivity to establish bounds on the "threshold interval" – the range of input probabilities where the function's output can change. The proofs involve careful analysis of probability measures, derivatives, and inequalities derived from influence sums.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on mathematical properties of functions rather than empirical data.

Key Insights and Ideas

  • Generalization of Sharp Thresholds: The core insight is that the sharp threshold phenomenon, previously understood for binary outcomes, extends to functions with multiple possible outcomes. This means that even in complex decision-making processes, small shifts in underlying probabilities can lead to decisive outcomes.
  • Social Choice Implications: The paper demonstrates that this sharp threshold behavior is fundamental to understanding social choice. It provides an extension of Condorcet's Jury Theorem for more than two candidates and offers insights into indeterminacy results in social choice theory, suggesting that even with complex voting rules, outcomes can be surprisingly predictable under certain conditions.
  • Information Aggregation: The findings imply that symmetric and monotone voting systems are efficient at aggregating information. Even with noisy individual signals, a slight bias towards one candidate can lead to that candidate winning with high probability, provided the voting rule is "fair" and "monotone."
  • Mathematical Tools: The paper showcases the power of influence analysis and Russo's formula in understanding the behavior of complex functions, extending their applicability beyond the binary case.

Key Results

  • Theorem 1.1: Establishes the existence of a universal constant $C$ such that for any symmetric and monotone function $f: [q]^n \to [q]$, the probability measure of the interval where $f$ takes a specific value $a$ with probability between $\epsilon$ and $1-\epsilon$ is bounded by $C \cdot (\log(1-\epsilon) - \log(\epsilon)) \cdot \frac{\log \log n}{\log n}$. This quantifies the sharpness of the threshold.
  • Theorem 1.3: Provides a generalized Condorcet's Jury Theorem. It states that if a probability measure on votes has a slight bias towards a candidate $i$, then for any fair monotone voting function, candidate $i$ will be elected with high probability (at least $1-\epsilon$).
  • Applications to Social Choice: The paper presents an extension of Condorcet's Jury Theorem for multiple candidates and discusses indeterminacy results for social choice functions, linking them to the sharp threshold behavior.
  • Applications to Graph Properties: It shows that monotone graph properties also exhibit sharp thresholds, meaning that a small change in the probability of edge labeling can drastically alter the resulting graph structure.

Limitations and Future Work

  • Threshold Interval Length: While the paper establishes sharp thresholds, the derived bound on the threshold interval length is $O(\frac{\log \log n}{\log n})$. The authors note that for the binary case, a tighter bound of $O(\frac{1}{\log n})$ is known and conjectured that this tighter bound might hold in general. Achieving this would likely require a more refined influence sum bound.
  • Generalization of Saari's Theorem: The paper mentions describing an extension of Saari's theorem but does not detail it within the provided text.
  • Further Exploration of Social Choice: The paper touches upon indeterminacy results in social choice theory and the size of classes of choice functions. Further exploration of these connections and the implications of sharp thresholds for various social choice mechanisms could be a fruitful direction.
  • Practical Implications: While the theoretical results are significant, translating these sharp threshold concepts into practical algorithms or analyses for real-world social choice scenarios or complex network formation could be a future research avenue.

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},
}
Figure