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

• 成果类型: Article
• 署名作者: Kalai, Gil; Mossel, Elchanan
• 署名单位: Hebrew University of Jerusalem; Yale University; University of Pennsylvania; University of California System; University of California Berkeley
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0703
• 发表日期: 2015
• 页码: 915-925
• 关键词: voting paradoxes; variables

摘要

A key fact in the theory of Boolean functions f : {0, 1}(n) -> {0, 1} is that they often undergo sharp thresholds. For example, if the function f : {0, 1}(n) -> {0, 1} is monotone and symmetric under a transitive action with E-p[f] = epsilon and E-q[f] = 1 - epsilon, then q - p -> 0 as n -> infinity. 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 set. 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.