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

PDF
MPRA_paper_440.pdf Download (235kB)  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 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 infinitegames 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; infinitely many players; axiomatic method; complete independence; algorithms; Turing computability; recursion theory 
Subjects:  D  Microeconomics > D9  Intertemporal Choice > D90  General C  Mathematical and Quantitative Methods > C6  Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C69  Other D  Microeconomics > D7  Analysis of Collective DecisionMaking > D71  Social Choice ; Clubs ; Committees ; Associations C  Mathematical and Quantitative Methods > C7  Game Theory and Bargaining Theory > C71  Cooperative Games 
Item ID:  440 
Depositing User:  H. Reiju Mihara 
Date Deposited:  13. Oct 2006 
Last Modified:  24. Mar 2015 07:55 
References:  [1] N. I. AlNa jjar, L. Anderlini, and L. Felli. Undescribable events. Review of Economic Studies, 73:849–868, 2006. [2] L. Anderlini and L. Felli. Incomplete written contracts: Undescribable states of nature. Quarterly Journal of Economics, 109:1085–1124, 1994. [3] K. J. Arrow. Social Choice and Individual Values. Yale University Press, New Haven, 2nd edition, 1963. [4] J. S. Banks, J. Duggan, and M. L. Breton. Social choice and electoral competition in the general spatial model. Journal of Economic Theory, 126:194–234, 2006. [5] J. Bartholdi III, C. A. Tovey, and M. A. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6:157–165, 1989. [6] J. J. Bartholdi III, C. A. Tovey, and M. A. Trick. The computational difficulty of manipulating an election. Social Choice and Welfare, 6:227– 241, 1989. [7] X. Deng and C. H. Papadimitriou. On the complexity of cooperative solution concepts. Mathematics of Operations Research, 19:257–266, 1994. [8] A. Downs. An Economic Theory of Democracy. AddisonWesley, Boston, 1957. [9] Q. Fang, S. Zhu, M. Cai, and X. Deng. On computational complexity of membership test in flow games and linear production games. Inter national Journal of Game Theory, 31:39–45, 2002. [10] J. S. Kelly. Social choice and computational complexity. Journal of Mathematical Economics, 17:1–8, 1988. [11] M. Kumabe and H. R. Mihara. Computability of simple games: A characterization and application to the core. MPRA Paper, July 2006. http://mpra.ub.unimuenchen.de/437/ [12] A. A. Lewis. An infinite version of Arrow’s Theorem in the effective setting. Mathematical Social Sciences, 16:41–48, 1988. [13] K. O. May. A set of independent, necessary and sufficient conditions for simple ma jority decision. Econometrica, 20:680–84, 1952. [14] K. O. May. A note on the complete independence of the conditions for simple ma jority decision. Econometrica, 21:172–173, 1953. [15] H. R. Mihara. Arrow’s Theorem and Turing computability. Economic Theory, 10(2):257–76, Aug. 1997. [16] H. R. Mihara. Arrow’s theorem, countably many agents, and more visi ble invisible dictators. Journal of Mathematical Economics, 32(3):267– 287, 1999. [17] H. R. Mihara. Nonanonymity and sensitivity of computable simple games. Mathematical Social Sciences, 48(3):329–341, 2004. [18] P. Odifreddi. Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers. Elsevier, Amsterdam, 1992. [19] B. Peleg. Gametheoretic analysis of voting in committees. In K. J. Arrow, A. K. Sen, and K. Suzumura, editors, Handbook of Social Choice and Welfare, volume 1, chapter 8, pages 395–423. Elsevier, Amsterdam, 2002. [20] M. K. Richter and K.C. Wong. Computable preference and utility. Journal of Mathematical Economics, 32:339–354, 1999. [21] R. I. Soare. Recursively Enumerable Sets and Degrees: A Study of Com putable Functions and Computably Generated Sets. SpringerVerlag, Berlin, 1987. [22] W. Thomson. On the axiomatic method and its recent applications to game theory and resource allocation. Social Choice and Welfare, 18:327–386, 2001. [23] R. J. Weber. Games in coalitional form. In R. J. Aumann and S. Hart, editors, Handbook of Game Theory, volume 2, chapter 36, pages 1285– 1303. Elsevier, Amsterdam, 1994. 
URI:  http://mpra.ub.unimuenchen.de/id/eprint/440 
Available Versions of this Item
 Computability of simple games: A complete investigation of the sixtyfour possibilities. (deposited 13. Oct 2006) [Currently Displayed]