Recognizing majority-rule equilibrium in spatial voting games

It is provably difficult (NP-complete) to determine whether a given point can be defeated in a majority-rule spatial voting game. Nevertheless, one can easily generate a point with the property that if any point cannot be defeated, then this point cannot be defeated. Our results suggest that majority-rule equilibrium can exist as a purely practical matter: when the number of voters and the dimension of the policy space are both large, it can be too difficult to find an alternative to defeat the status quo. It is also computationally difficult to determine the radius of the yolk or the Nakamura number of a weighted voting game.We are grateful to Norman Schofield and an anonymous referee for many helpful suggestions.The first author was supported in part by a Presidential Young Investigator Award from the National Science Foundation (ECS-8351313) and by the Office of Naval Research (N00014-85-K-0147). The third author was supported in part by a Presendential Young Investigator Award from the National Science Foundation (ECS-8451032).