Sharp Thresholds for Monotone Non Boolean Functions and Social Choice Theory

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

2010-11-16

arxiv.org/abs/1011.3566v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Sharp Thresholds for Monotone Non Boolean Functions and Social Choice Theory does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sharp Thresholds for Monotone Non Boolean Functions and Social Choice Theory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp Thresholds for Monotone Non Boolean Functions and Social Choice Theory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-463299