Widespread avoidance of Measles-Mumps-Rubella vaccination (MMR), with a consequent increase in the incidence of major measles outbreaks, demonstrates that the effectiveness of vaccination programs can be thwarted by the public misperceptions of vaccine risk. By coupling game theory and epidemic models, we examine vaccination choice among populations stratified into two behavioral groups: vaccine skeptics and vaccine believers. The two behavioral groups are assumed to be heterogeneous with respect to their perceptions of vaccine and infection risks. We demonstrate that the pursuit of self-interest among vaccine skeptics often leads to vaccination levels that are suboptimal for a population, even if complete coverage is achieved among vaccine believers. The demand for measles vaccine across populations driven by individual self-interest was found to be more sensitive to the proportion of vaccine skeptics than to the extent to which vaccine skeptics misperceive the risk of vaccine. Furthermore, as the number of vaccine skeptics increases, the probability of infection among vaccine skeptics increases initially, but it decreases once the vaccine skeptics begin receiving the vaccination, if both behavioral groups are vaccinated according to individual self-interest. Our results show that the discrepancy between the coverages of measles vaccine that are driven by self-interest and those driven by population interest becomes larger when the cost of vaccination increases. This research illustrates the importance of public education on vaccine safety and infection risk in order to maintain vaccination levels that are sufficient to maintain herd immunity.