On the Robustness of Majority Rule