Kumabe, Masahiro and Mihara, H. Reiju (2006): Computability of simple games: A characterization and application to the core.
There is a more recent version of this item available. 

PDF
MPRA_paper_437.pdf Download (278kB)  Preview 
Abstract
It was shown earlier that the class of algorithmically computable simple games (i) includes the class of games that have finite carriers and (ii) is included in the class of games that have finite winning coalitions. This paper characterizes computable games, strengthens the earlier result that computable games violate anonymity, and gives examples showing that the above inclusions are strict. It also extends Nakamura’s theorem about the nonemptyness of the core and shows that computable simple games have a finite Nakamura number, implying that the number of alternatives that the players can deal with rationally is restricted.
Item Type:  MPRA Paper 

Original Title:  Computability of simple games: A characterization and application to the core 
Language:  English 
Keywords:  Voting games; infinitely many players; recursion theory; Turingcomputability; computable manuals and contracts 
Subjects:  D  Microeconomics > D9  Intertemporal Choice and Growth > 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:  437 
Depositing User:  H. Reiju Mihara 
Date Deposited:  13. Oct 2006 
Last Modified:  27. Feb 2013 18:07 
References:  [1] L. Anderlini and L. Felli. Incomplete written contracts: Undescribable states of nature. Quarterly Journal of Economics, 109:1085–1124, 1994. [2] L. Anderlini and H. Sabourian. Cooperation and effective computabil ity. Econometrica, 63:1337–1369, 1995. [3] N. G. Andjiga and B. Mbih. A note on the core of voting games. Journal of Mathematical Economics, 33:367–372, 2000. [4] T. E. Armstrong. Arrow’s Theorem with restricted coalition algebras. Journal of Mathematical Economics, 7:55–75, 1980. [5] T. E. Armstrong. Precisely dictatorial social welfare functions: Erratum and addendum to ‘Arrow’s Theorem with restricted coalition algebras’. Journal of Mathematical Economics, 14:57–59, 1985. [6] K. J. Arrow. Social Choice and Individual Values. Yale University Press, New Haven, 2nd edition, 1963. [7] K. J. Arrow. Rationality of self and others in an economic system. Journal of Business, 59:S385–S399, 1986. [8] D. AustenSmith and J. S. Banks. Positive Political Theory I: Col lective Preference. University of Michigan Press, Ann Arbor, 1999. [9] J. S. Banks. Acyclic social choice from finite sets. Social Choice and Welfare, 12:293–310, 1995. [10] 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. [11] 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. [12] 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. [13] D. Canning. Rationality, computability, and Nash equilibrium. Econo metrica, 60(4):877–888, July 1992. [14] G. S. Ce ̆ıtin. Algorithmic operators in constructive complete separable metric spaces. Doklady Akad. Nauk, 128:49–52, 1959. (in Russian). [15] X. Deng and C. H. Papadimitriou. On the complexity of cooperative solution concepts,. Mathematics of Operations Research, 19:257–266, 1994. [16] A. Downs. An Economic Theory of Democracy. AddisonWesley, Boston, 1957. [17] R. Evans and J. P. Thomas. Cooperation and punishment. Economet rica, 69:1061–1075, 2001. [18] 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. [19] M. Fey. May’s theorem with an infinite population. Social Choice and Welfare, 23:275–293, 2004. [20] I. Gilboa. Philosophical applications of Kolmogorov’s complexity mea sure. Discussion Paper 923, Northwestern University, Center for Math ematical Studies in Economics and Management Science, Oct. 1990. [21] A. Gomberg, C. Martinelli, and R. Torres. Anonymity in large societies. Social Choice and Welfare, 25:187–205, 2005. [22] J. S. Kelly. Social choice and computational complexity. Journal of Mathematical Economics, 17:1–8, 1988. [23] A. P. Kirman and D. Sondermann. Arrow’s Theorem, many agents, and invisible dictators. Journal of Economic Theory, 5:267–277, 1972. [24] S. Koppelberg. Handbook of Boolean Algebras, volume 1. North Holland, Amsterdam, 1989. Edited by J. D. Monk, with the cooperation of R. Bonnet. [25] G. Kreisel, D. Lacombe, and J. R. Shoenfield. Partial recursive func tionals and effective operations. In A. Heyting, editor, Constructivity in Mathematics, Studies in Logic and the Foundations of Mathematics, pages 290–297, Amsterdam, 1959. NorthHolland. [26] M. Kumabe and H. R. Mihara. Computability of simple games: A complete investigation of the sixtyfour possibilities. In preparation, 2006. [27] A. A. Lewis. An infinite version of Arrow’s Theorem in the effective setting. Mathematical Social Sciences, 16:41–48, 1988. [28] B. L. Lipman. Information processing and bounded rationality: A survey. Canadian Journal of Economics, 28:42–67, 1995. [29] H. R. Mihara. Anonymity and neutrality in Arrow’s Theorem with restricted coalition algebras. Social Choice and Welfare, 14(4):503–12, Oct. 1997. [30] H. R. Mihara. Arrow’s Theorem and Turing computability. Economic Theory, 10(2):257–76, Aug. 1997. [31] H. R. Mihara. Arrow’s theorem, countably many agents, and more visi ble invisible dictators. Journal of Mathematical Economics, 32(3):267– 287, 1999. [32] H. R. Mihara. Existence of a coalitionally strategyproof social choice function: A constructive proof. Social Choice and Welfare, 18(3):543– 553, 2001. [33] H. R. Mihara. Nonanonymity and sensitivity of computable simple games. Mathematical Social Sciences, 48(3):329–341, 2004. [34] K. Nakamura. The vetoers in a simple game with ordinal preferences. International Journal of Game Theory, 8:55–61, 1979. [35] P. Odifreddi. Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers. Elsevier, Amsterdam, 1992. [36] 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. [37] K. Prasad. On the computability of Nash equilibria. Journal of Eco nomic Dynamics and Control, 21:943–953, 1997. [38] M. K. Richter and K.C. Wong. Computable preference and utility. Journal of Mathematical Economics, 32:339–354, 1999. [39] M. K. Richter and K.C. Wong. Noncomputability of competitive equi librium. Economic Theory, 14:1–27, 1999. [40] A. Rubinstein. Modeling Bounded Rationality. MIT Press, Cambridge, Massachusetts, 1998. [41] R. I. Soare. Recursively Enumerable Sets and Degrees: A Study of Com putable Functions and Computably Generated Sets. SpringerVerlag, Berlin, 1987. [42] S. E. Spear. Learning rational expectations under computability con straints. Econometrica, 57:889–910, July 1989. [43] M. Truchon. Voting games and acyclic collective choice rules. Mathe matical Social Sciences, 29, 1995. [44] 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. [45] M. Yokoo, V. Conitzer, T. Sandholm, N. Ohta., and A. Iwasaki. Coali tional games in open anonymous environments. In Proceedings of the National Conference on Artificial Intel ligence (AAAI), Pittsburgh, PA, 2005. American Association for Artificial Intelligence. 
URI:  http://mpra.ub.unimuenchen.de/id/eprint/437 
Available Versions of this Item
 Computability of simple games: A characterization and application to the core. (deposited 13. Oct 2006) [Currently Displayed]