Computability of simple games: A characterization and application to the core

Kumabe, Masahiro and Mihara, H. Reiju (2007): Computability of simple games: A characterization and application to the core. Published in: Journal of Mathematical Economics , Vol. 44, No. 3-4 (February 2008): pp. 348-366.

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
• 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 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

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. Austen-Smith, 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. Addison-Wesley, 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. North-Holland, 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. North-Holland, 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 sixty-four 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. 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.

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. Non-computability 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. Springer-Verlag, 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.niigata-u.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.