The Nakamura numbers for computable simple games

Kumabe, Masahiro and Mihara, H. Reiju (2007): The Nakamura numbers for computable simple games.

Abstract

The Nakamura number of a simple game plays a critical role in preference aggregation (or multi-criterion ranking): the number of alternatives that the players can always deal with rationally is less than this number. We comprehensively study the restrictions that various properties for a simple game impose on its Nakamura number. We find that a computable game has a finite Nakamura number greater than three only if it is proper, nonstrong, and nonweak, regardless of whether it is monotonic or whether it has a finite carrier. The lack of strongness often results in alternatives that cannot be strictly ranked.

• Item Type: MPRA Paper
• Language: English
• Keywords: Nakamura number; voting games; core; Turing computability; axiomatic method; multi-criterion decision-making
• Subjects: 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

Andjiga, N. G. and Mbih, B. (2000). A note on the core of voting games. Journal of Mathematical Economics, 33:367–372. Arrow, K. J. (1963). Social Choice and Individual Values. Yale University Press, New Haven, 2nd edition. Austen-Smith, D. and Banks, J. S. (1999). Positive Political Theory I: Col lective Preference. University of Michigan Press, Ann Arbor.

Banks, J. S. (1995). Acyclic social choice from finite sets. Social Choice and Welfare, 12:293–310. Bartholdi, III, J., Tovey, C. A., and 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., and Trick, M. A. (1989b). The computa- tional difficulty of manipulating an election. Social Choice and Welfare, 6:227–241. Deb, R. (2004). Rights as alternative game forms. Social Choice and Welfare, 22:83–111. Kelly, J. S. (1988). Social choice and computational complexity. Journal of Mathematical Economics, 17:1–8. Kolpin, V. (1990). Equivalent game forms and coalitional power. Mathe- matical Social Sciences, 20:239–249. Kumabe, M. and Mihara, H. R. (2007a). Computability of simple games: A characterization and application to the core. Journal of Mathematical Economics. doi:10.1016/j.jmateco.2007.05.012. Kumabe, M. and Mihara, H. R. (2007b). Computability of simple games: A complete investigation of the sixty-four possibilities. MPRA Paper 4405, Munich University Library. Kumabe, M. and Mihara, H. R. (2007c). 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. Mihara, H. R. (1997). 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. (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., and Suzumura, K., editors, Handbook of Social Choice and Welfare, volume 1, chapter 8, pages 395–423. Elsevier, Amsterdam. Richter, M. K. and Wong, K.-C. (1999). Computable preference and utility. Journal of Mathematical Economics, 32:339–354. Shapley, L. S. (1962). Simple games: An outline of the descriptive theory. Behavioral Science, 7:59–66. Soare, R. I. (1987). Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Springer-Verlag, Berlin. Tanaka, Y. (2007). Type two computability of social choice functions and the Gibbard-Satterthwaite theorem in an infinite society. Applied Mathe- matics and Computation, 192:168–174. Truchon, M. (1995). Voting games and acyclic collective choice rules. Math- ematical Social Sciences, 29:165–179. van Hees, M. (1999). Liberalism, efficiency, and stability: Some possibility results. Journal of Economic Theory, 88:294–309. Weber, R. J. (1994). Games in coalitional form. In Aumann, R. J. and Hart, S., editors, Handbook of Game Theory, volume 2, chapter 36, pages 1285–1303. Elsevier, Amsterdam.