Noncryptographic selection protocols

Selection tasks generalize some well studied problems, such as collective coin flipping and leader election. We present new selection protocols in the full information model, and new negative results. In particular when there are (1+δ)n/2 good players, we show a protocol that chooses a good leader with probability Ω(δ^1.65), and show that every leader election protocol has success probability O(δ^1-ε), for every ε>0. Previously known protocols for this problem have success probability that is exponentially small in 1/δ, and no nontrivial upper bounds on the success probability were known