This paper discusses an aspect of computational complexity in social choice theory. We consider the problem of designing voting rules, which is formulated in terms of simple games. We prove that it is an NP-complete problem to decide whether a given simple game is stable, or not.

It is known that on some social choice and economic domains, a social choice function is coalition strategy-proof if and only if it is Maskin monotonic (e.g. Muller and Satterthwaite, 1977). This paper studies the foundation of those results. I provide a set of conditions which is sufficient for...

This paper studies the incentive compatibility of solutions to generalized indivisible good allocation problems introduced by Sonmez (1999), which contain the well-known marriage problems (Gale and Shapley, 1962) and the housing markets (Shapley and Scarf, 1974) as special cases. In particular,...

This paper reexamines the paradoxical aspect of the electronic mail game (Rubinstein, 1989). The electronic mail game is a coordination game with payoff uncertainty. At a Bayesian Nash equilibrium of the game, players cannot achieve the desired coordination of actions even when a high order of...

This paper studies allocation correspondences in the house allocation problems with collective initial endowments. We examine the implications of two axioms, namely "consistency" and "unanimity." Consistency requires the allocation correspondence be invariant under reductions of population....