Search

ISER discussion paper, March 2006 Revised July 2006 (Originally entitled "Computational Complexity in the Design of Voting Systems."), 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.

In a simple game, coalitions belonging to a given class are "absolutely powerful" while others have no power. We attempt to make this distinction operational. Toward this end, we propose two axioms on social choice correspondences, Strong Non-Discrimination and Exclusion. Strong Non-Discrimination describes circumstances under which certain coalitions, the losing coalitions, have no influence over social choice. Exclusion requires that there are situations in which certain coalitions, the winning coalitions, can exercise their power. We show that the weak core correspondence is the minimal correspondence satisfying Maskin Monotonicity and Strong Non-Discrimination. We also show that the weak core is the unique correspondence satisfying Nash implementability, Strong Non-Discrimination, and Exclusion.

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.

In the marriage problem (two-sided one-to-one matching problem), it is well-known that the weak core, the strong core and the set of stable matchings are all equivalent. This paper generalizes the above observation considering the G-weak core and the G-strong core. These are core concepts in which blocking power is restricted to the coalitions belonging to the prescribed class of coalitions G. I give a necessary and sufficient condition that G should satisfy for the equivalence of the G-weak core and the G-strong core.