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

Kumabe, Masahiro and Mihara, H. Reiju (2006): Computability of simple games: A characterization and application to the core.

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
• Language: English
• Keywords: Voting games; infinitely many players; recursion theory; Turingcomputability; computable manuals and contracts
• 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 Decision-Making > D71 - Social Choice ; Clubs ; Committees ; Associations; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

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. Austen-Smith 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. Addison-Wesley, 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. North-Holland. [26] M. Kumabe and H. R. Mihara. Computability of simple games: A complete investigation of the sixty-four 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. Game-theoretic 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. Non-computability 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. Springer-Verlag, 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.