An n-person game is considered where each player has a preference order over a finite set A of possible alternatives and a rule for social choice is given in the form of an effectivity function E. The effectivity function is called stable if for any combination of individual preference orders there exists a subset of A called a core such that any alternative in the core cannot be ‘dominated’ by such individual preferences. It has been shown by Keiding that the effectivity function E is stable if and only if E does not generate any ‘Cycle’. This paper is concerned with the computational complexity of the problem (CYCLE) for determining whether or not a given effectivity function has a Cycle. The authors show that a familiar NPC problem SATISFIABILITY can be transformed into CYCLE through a polynomial time procedure. This, combined with the fact that CYCLE is an NP problem, implies NP-completeness of CYCLE, and therefore that of verifying the unstability of the effectivity function, thereby formally proving a previously unanswered conjecture.
