Let A be a finite set of m alternatives, let N be a finite set of n players, and let RN be a profile of linear orders on A of the players. Let uN be a profile of utility functions for RN. We define the nontransferable utility (NTU) game VuN that corresponds to simple majority voting, and investigate its Aumann–Davis–Maschler and Mas–Colell bargaining sets. The first bargaining set is nonempty for m ≤ 3, and it may be empty for m ≥ 4. However, in a simple probabilistic model, for fixed m, the probability that the Aumann–Davis–Maschler bargaining set is nonempty tends to one if n tends to infinity. The Mas–Colell bargaining set is nonempty for m ≤ 5, and it may be empty for m ≥ 6. Furthermore, it may be empty even if we insist that n be odd, provided that m is sufficiently large. Nevertheless, we show that the Mas–Colell bargaining set of any simple majority voting game derived from the k–fold replication of RN is nonempty, provided that k ≥ n+2.