×

Sharp thresholds for monotone non-Boolean functions and social choice theory. (English) Zbl 1409.91107

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

MSC:

91B14 Social choice
91B12 Voting theory
06E30 Boolean functions
91A12 Cooperative games
05C80 Random graphs (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bourgain J, Kahn J, Kalai G, Katznelson Y, Linial N (1992) The influence of variables in product spaces. Israel J. Math. 77:55-64. CrossRef · Zbl 0771.60002
[2] Dasgupta P, Maskin E (2008) The robustness of majority rule. J. Eur. Econom. Assoc. 6:949-973. CrossRef
[3] Friedgut E, Kalai G (1996) Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc. 124:2993-3002. CrossRef · Zbl 0864.05078
[4] Kalai G (2004) Social indeterminacy. Econometrica 72:1565-1581. CrossRef · Zbl 1141.91373
[5] Margulis GA (1974) Probabilistic characteristics of graphs with large connectivity. Problemy Peredači Informacii 10(2):101-108.
[6] May KO (1952) A set of independent necessary and sufficient conditions for simple majority decisions. Econometrica 20(4):680-684. CrossRef · Zbl 0047.38402
[7] McGarvey DC (1953) A theorem on the construction of voting paradoxes. Econometrica 21:608-610. CrossRef
[8] Russo L (1981) On the critical percolation probabilities. Z. Wahrsch. Verw. Gebiete 56(2):229-237. CrossRef · Zbl 0457.60084
[9] Saari DG (1989) A dictionary of voting paradoxes. J. Econom. Theory 48(2):443-475. CrossRef · Zbl 0672.90010
[10] Steele JM (1986) An Efron-Stein inequality for nonsymmetric statistics. Ann. Statist. 14(2):753-758. CrossRef · Zbl 0604.62017
[11] Talagrand M (1994) On Russo’s approximate 0-1 law. Ann. Probab. 22:1576-1587. CrossRef · Zbl 0819.28002
[12] Wolff P (2007) Hypercontractivity of simple random variables. Studia Mathematica 180(3):219-326. CrossRef · Zbl 1133.60011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.