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

PDF
MPRA_paper_4403.pdf Download (333kB)  Preview 
Abstract
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 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; Turing computability; computable manuals and contracts 
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 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:  4403 
Depositing User:  H. Reiju Mihara 
Date Deposited:  09. Aug 2007 
Last Modified:  01. Mar 2013 18:46 
References:  Anderlini, L., Felli, L., 1994. Incomplete written contracts: Undescribable states of nature. Quarterly Journal of Economics 109, 1085–1124. Anderlini, L., Sabourian, H., 1995. Cooperation and effective computability. Econometrica 63, 1337–1369. Andjiga, N. G., Mbih, B., 2000. A note on the core of voting games. Journal of Mathematical Economics 33, 367–372. Armstrong, T. E., 1980. Arrow’s Theorem with restricted coalition algebras. Journal of Mathematical Economics 7, 55–75. Armstrong, T. E., 1985. Precisely dictatorial social welfare functions: Erra tum and addendum to ‘Arrow’s Theorem with restricted coalition alge bras’. Journal of Mathematical Economics 14, 57–59. Arrow, K. J., 1963. Social Choice and Individual Values, 2nd Edition. Yale University Press, New Haven. Arrow, K. J., 1986. Rationality of self and others in an economic system. Journal of Business 59, S385–S399. AustenSmith, D., Banks, J. S., 1999. Positive Political Theory I: Collective Preference. University of Michigan Press, Ann Arbor. Banks, J. S., 1995. Acyclic social choice from finite sets. Social Choice and Welfare 12, 293–310. Banks, J. S., Duggan, J., Breton, M. L., 2006. Social choice and electoral competition in the general spatial model. Journal of Economic Theory 126, 194–234. 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, 157–165. Bartholdi III, J. J., Tovey, C. A., Trick, M. A., 1989b. The computational difficulty of manipulating an election. Social Choice and Welfare 6, 227– 241. Canning, D., 1992. Rationality, computability, and Nash equilibrium. Econo metrica 60, 877–888. Ce ̆ıtin, G. S., 1959. Algorithmic operators in constructive complete separable metric spaces. Doklady Akad. Nauk 128, 49–52, (in Russian). Deng, X., Papadimitriou, C. H., 1994. On the complexity of cooperative solution concepts. Mathematics of Operations Research 19, 257–266. Downs, A., 1957. An Economic Theory of Democracy. AddisonWesley, Boston. Evans, R., Thomas, J. P., 2001. Cooperation and punishment. Econometrica 69, 1061–1075. Fang, Q., Zhu, S., Cai, M., Deng, X., 2002. On computational complexity of membership test in flow games and linear production games. International Journal of Game Theory 31, 39–45. Fey, M., 2004. May’s theorem with an infinite population. Social Choice and Welfare 23, 275–293. Gilboa, I., Oct. 1990. Philosophical applications of Kolmogorov’s complex ity measure. Discussion Paper 923, Northwestern University, Center for Mathematical Studies in Economics and Management Science. Gomberg, A., Martinelli, C., Torres, R., 2005. Anonymity in large societies. Social Choice and Welfare 25, 187–205. Kelly, J. S., 1988. Social choice and computational complexity. Journal of Mathematical Economics 17, 1–8. Kirman, A. P., Sondermann, D., 1972. Arrow’s Theorem, many agents, and invisible dictators. Journal of Economic Theory 5, 267–277. Koppelberg, S., 1989. Handbook of Boolean Algebras. Vol. 1. NorthHolland, Amsterdam, edited by J. D. Monk, with the cooperation of R. Bonnet. Kreisel, G., Lacombe, D., Shoenfield, J. R., 1959. Partial recursive func tionals and effective operations. In: Heyting, A. (Ed.), Constructivity in Mathematics. Studies in Logic and the Foundations of Mathematics. NorthHolland, Amsterdam, pp. 290–297. Kumabe, M., Mihara, H. R., May 2007. Computability of simple games: A characterization and application to the core. MPRA Paper 3296, Munich University Library. Kumabe, M., Mihara, H. R., Oct. 2006. Computability of simple games: A complete investigation of the sixtyfour possibilities. MPRA Paper 440, Munich University Library. Kumabe, M., Mihara, H. R., Jun. 2007b. The Nakamura numbers for com putable simple games. MPRA Paper 3684, Munich University Library. Lewis, A. A., 1988. An infinite version of Arrow’s Theorem in the effective setting. Mathematical Social Sciences 16, 41–48. Lipman, B. L., 1995. Information processing and bounded rationality: A survey. Canadian Journal of Economics 28, 42–67. Mihara, H. R., 1997a. Anonymity and neutrality in Arrow’s Theorem with restricted coalition algebras. Social Choice and Welfare 14, 503–12. Mihara, H. R., 1997b. Arrow’s Theorem and Turing computability. Eco nomic 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., 2001. Existence of a coalitionally strategyproof social choice function: A constructive proof. Social Choice and Welfare 18, 543–553. Mihara, H. R., 2004. Nonanonymity and sensitivity of computable simple games. Mathematical Social Sciences 48, 329–341. Nakamura, K., 1979. The vetoers in a simple game with ordinal preferences. International Journal of Game Theory 8, 55–61. 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. 395–423. Prasad, K., 1997. On the computability of Nash equilibria. Journal of Eco nomic Dynamics and Control 21, 943–953. Richter, M. K., Wong, K.C., 1999a. Computable preference and utility. Journal of Mathematical Economics 32, 339–354. Richter, M. K., Wong, K.C., 1999b. Noncomputability of competitive equi librium. Economic Theory 14, 1–27. Rubinstein, A., 1998. Modeling Bounded Rationality. MIT Press, Cam bridge, Massachusetts. Soare, R. I., 1987. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. SpringerVerlag, Berlin. Spear, S. E., Jul. 1989. Learning rational expectations under computability constraints. Econometrica 57, 889–910. Takamiya, K., Tanaka, A., Jan. 2007. Computational complexity in the de sign of voting rules. http://ecows.econ.niigatau.ac.jp/∼takamiya/ rsrch.html Truchon, M., 1995. Voting games and acyclic collective choice rules. Math ematical Social Sciences 29, 165–179. 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. Yokoo, M., Conitzer, V., Sandholm, T., Ohta, N., Iwasaki, A., 2005. Coali tional games in open anonymous environments. In: Proceedings of the National Conference on Artificial Intelligence (AAAI). American Associ ation for Artificial Intelligence, Pittsburgh, PA. 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/4403 
Available Versions of this Item

Computability of simple games: A characterization and application to the core. (deposited 13. Oct 2006)

Computability of simple games: A characterization and application to the core. (deposited 22. May 2007)
 Computability of simple games: A characterization and application to the core. (deposited 09. Aug 2007) [Currently Displayed]

Computability of simple games: A characterization and application to the core. (deposited 22. May 2007)