Kumabe, Masahiro and Mihara, H. Reiju (2007): Computability of simple games: A complete investigation of the sixtyfour possibilities.
There is a more recent version of this item available. 

PDF
MPRA_paper_4405.pdf Download (261kB)  Preview 
Abstract
Classify simple games into sixteen "types" in terms of the four conventional axioms: monotonicity, properness, strongness, and nonweakness. Further classify them into sixtyfour 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 infinite games and noncomputable ones. This strongly suggests that computability is logically, as well as conceptually, unrelated to the conventional axioms.
Item Type:  MPRA Paper 

Original Title:  Computability of simple games: A complete investigation of the sixtyfour possibilities 
Language:  English 
Keywords:  Voting games; axiomatic method; complete independence; Turing computability; legal precedents 
Subjects:  C  Mathematical and Quantitative Methods > C7  Game Theory and Bargaining Theory > C71  Cooperative Games D  Microeconomics > D9  Intertemporal Choice and Growth > D90  General D  Microeconomics > D7  Analysis of Collective DecisionMaking > D71  Social Choice; Clubs; Committees; Associations C  Mathematical and Quantitative Methods > C6  Mathematical Methods; Programming Models; Mathematical and Simulation Modeling > C69  Other 
Item ID:  4405 
Depositing User:  H. Reiju Mihara 
Date Deposited:  09. Aug 2007 
Last Modified:  23. Feb 2013 21:50 
References:  AlNa jjar, N. I., Anderlini, L., Felli, L., 2006. Undescribable events. Review of Economic Studies 73, 849868. Anderlini, L., Felli, L., 1994. Incomplete written contracts: Undescribable states of nature. Quarterly Journal of Economics 109, 10851124. Arrow, K. J., 1963. Social Choice and Individual Values, 2nd Edition. Yale University Press, New Haven. Bartholdi, III, J., 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, 157165. Bartholdi, III, J. J., Tovey, C. A., Trick, M. A., 1989b. The computational difficulty of manipulating an election. Social Choice and Welfare 6, 227241. Kelly, J. S., 1988. Social choice and computational complexity. Journal of Mathematical Economics 17, 18. Krasa, S., Williams, S. R., 2007. Limited observability as a constraint in contract design. Journal of Economic Theory 134, 379404. Kumabe, M., Mihara, H. R., 2007a. Computability of simple games: A characterization and application to the core. Journal of Mathematical Economics Doi:10.1016/j.jmateco.2007.05.012. Kumabe, M., Mihara, H. R., Jun. 2007b. The Nakamura numbers for computable simple games. MPRA Paper 3684, Munich University Library. Landes, W. M., Posner, R. A., 1976. Legal precedent: A theoretical and empirical analysis. Journal of Law and Economics 19, 249307. Lewis, A. A., 1988. An infinite version of Arrow's Theorem in the effective setting. Mathematical Social Sciences 16, 4148. Lyons, D., 1984. Formal justice, moral commitment, and judicial precedent. Journal of Philosophy 81, 580587. May, K. O., 1952. A set of independent, necessary and sufficient conditions for simple ma jority decision. Econometrica 20, 68084. May, K. O., 1953. A note on the complete independence of the conditions for simple ma jority decision. Econometrica 21, 172173. Mihara, H. R., Aug. 1997. Arrow's Theorem and Turing computability. Eco nomic Theory 10, 25776. Mihara, H. R., 1999. Arrow's theorem, countably many agents, and more visible invisible dictators. Journal of Mathematical Economics 32, 267287. Mihara, H. R., 2004. Nonanonymity and sensitivity of computable simple games. Mathematical Social Sciences 48, 329341. Odifreddi, P., 1992. Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers. Elsevier, Amsterdam. Peleg, B., 2002. Gametheoretic 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. 395423. Rasmusen, E., 1994. Judicial legitimacy as a repeated game. Journal of Law, Economics, and Organization 10, 6383. Richter, M. K., Wong, K.C., 1999. Computable preference and utility. Journal of Mathematical Economics 32, 339354. Soare, R. I., 1987. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. SpringerVerlag, Berlin. Thomson, W., 2001. On the axiomatic method and its recent applications to game theory and resource allocation. Social Choice and Welfare 18, 327386. 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. 12851303. Weihrauch, K., July 1995. A simple introduction to computable analysis, http://eccc.hpiweb.de/eccclocal/ECCCBooks/klaus bookreadme.html 
URI:  http://mpra.ub.unimuenchen.de/id/eprint/4405 
Available Versions of this Item

Computability of simple games: A complete investigation of the sixtyfour possibilities. (deposited 13. Oct 2006)
 Computability of simple games: A complete investigation of the sixtyfour possibilities. (deposited 09. Aug 2007) [Currently Displayed]