Computability of simple games: A complete investigation of the sixty-four possibilities

Kumabe, Masahiro and Mihara, H. Reiju (2011): Computability of simple games: A complete investigation of the sixty-four possibilities. Forthcoming in: Journal of Mathematical Economics

Abstract

Classify simple games into sixteen "types" in terms of the four conventional axioms: monotonicity, properness, strongness, and nonweakness. Further classify them into sixty-four classes in terms of finiteness (existence of a finite carrier) and algorithmic computability. For each such class, we either show that it is empty or give an example of a game belonging to it. We observe that if a type contains an infinite game, then it contains both computable ones and noncomputable ones. This strongly suggests that computability is logically, as well as conceptually, unrelated to the conventional axioms.

• Item Type: MPRA Paper
• Language: English
• Keywords: Voting games; axiomatic method; complete independence; Turing computability; multi-criterion decision-making
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games; D - Microeconomics > D9 - Intertemporal Choice > D90 - General; D - Microeconomics > D7 - Analysis of Collective Decision-Making > D71 - Social Choice ; Clubs ; Committees ; Associations; C - Mathematical and Quantitative Methods > C6 - Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C69 - Other

References

Al-Na jjar, N. I., Anderlini, L., Felli, L., 2006. Undescribable events. Review of Economic Studies 73, 849–868.

Arrow, K. J., 1963. Social Choice and Individual Values, 2nd Edition. Yale University Press, New Haven.

Bartholdi, J., III, Tovey, C. A., Trick, M. A., 1989a. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare 6, 157–165.

Bartholdi, J. J., III, Tovey, C. A., Trick, M. A., 1989b. The computational difficulty of manipulating an election. Social Choice and Welfare 6, 227–241.

Kelly, J. S., 1988. Social choice and computational complexity. Journal of Mathematical Economics 17, 1–8.

Kumabe, M., Mihara, H. R., Aug. 2007. Computability of simple games: A complete investigation of the sixty-four possibilities. MPRA Paper 4405, Munich University Library, http://mpra.ub.uni-muenchen.de/4405/

Kumabe, M., Mihara, H. R., 2008a. Computability of simple games: A characterization and application to the core. Journal of Mathematical Economics 44, 348–366.

Kumabe, M., Mihara, H. R., 2008b. The Nakamura numbers for computable simple games. Social Choice and Welfare 31, 621–640.

Kumabe, M., Mihara, H. R., 2010. Preference aggregation theory without acyclicity: The core without ma jority dissatisfaction. Games and Economic Behavior, Doi:10.1016/j.geb.2010.06.008

Lewis, A. A., 1988. An infinite version of Arrow’s Theorem in the effective setting. Mathematical Social Sciences 16, 41–48.

May, K. O., 1952. A set of independent, necessary and sufficient conditions for simple ma jority decision. Econometrica 20, 680–84.

May, K. O., 1953. A note on the complete independence of the conditions for simple ma jority decision. Econometrica 21, 172–173.

Mihara, H. R., 1997. Arrow’s Theorem and Turing computability. Economic Theory 10, 257–76.

Mihara, H. R., 1999. Arrow’s theorem, countably many agents, and more visible invisible dictators. Journal of Mathematical Economics 32, 267–287.

Mihara, H. R., 2004. Nonanonymity and sensitivity of computable simple games. Mathematical Social Sciences 48, 329–341.

Odifreddi, P., 1992. Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers. Elsevier, Amsterdam.

Peleg, B., 2002. Game-theoretic analysis of voting in committees. In: Arrow, K. J., Sen, A. K., Suzumura, K. (Eds.), Handbook of Social Choice and Welfare. Vol. 1. Elsevier, Amsterdam, Ch. 8, pp. 395–423.

Soare, R. I., 1987. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer-Verlag, Berlin.

Thomson, W., 2001. On the axiomatic method and its recent applications to game theory and resource allocation. Social Choice and Welfare 18, 327–386.

Weber, R. J., 1994. Games in coalitional form. In: Aumann, R. J., Hart, S. (Eds.), Handbook of Game Theory. Vol. 2. Elsevier, Amsterdam, Ch. 36, pp. 1285–1303.