Abstract
Ann-person game is considered where each player has a preference order over a finite setA of possible alternatives and a rule for social choice is given in the form of an effectivity functionE. The effectivity function is called stable if for any combination of individual preference orders there exists a subset ofA called a core such that any alternative in the core cannot be ‘dominated’ by such individual preferences. It has been shown by Keiding (1985) that the effectivity functionE is stable if and only ifE 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, We 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Cook SA (1971) The complexity of theorem — proving procedure. Proceedings of the third annual ACM symposium on theory of computing 151–158
Demange G (1987) Nonmanipulable cores. Econometrica 55:1057–1074
Gary MR, Johnson DS (1979) Computers and intractability – A guide to the theory of NP-completeness. Freeman, New York
Keiding H (1985) Necessary and sufficient condition for stability of effectivity functions. International Journal of Game Theory 14:93–101
Lee NC, Nishino H, Mizutami M (1989) The nonemptiness of the core — balancedness of effectivity function. Discussion Paper
Moulin H, Peleg B (1982) Cores of effectivity functions and implementation theory. Journal of Economic Theory 10:115–145
Peleg B (1983) Game theoretic analysis of voting in committees. Cambridge University Press, Cambridge
Scarf HE (1967) The core of ann-person.game. Econometrica 35:50–69
Tarjan R (1972) Depth-first search and linear graph algorithms. SIAM Journal on Computing 1:146–160
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Mizutani, M., Hiraide, Y. & Nishino, H. Computational complexity to verify the unstability of effectivity function. Int J Game Theory 22, 225–239 (1993). https://doi.org/10.1007/BF01240054
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01240054