•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.”
•
•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}