10/28/2005

11

•__Conj (Kalai-02) Thm: (M-O’Donnell-Oleskiewicz-05):
__

•Majority is Stablest ) “The probability of an Arrow Paradox” among all low influence
function is minimized by the majority function.

•__Conj (Kalai-01) Thm:
(M-O’Donnell-Oleskiewicz-05):
__

•For f with low influences – “it ain’t over until it’s over.”

B

C

A

•It is assumed that voters rank

3 candidates uniformly in S3n

•A “paradox” is the event that the

overall preference is A over
B over

C over A using an
aggregation

function f : {-1,1}n ! {-1,1}

• This means that for
every h, the probability to be (1-d)-“certain” of value of the function given a random fraction h of the inputs goes to 0 as d ! 0.