The Nakamura numbers for computable simple games
Tóm tắt
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.
Tài liệu tham khảo
Andjiga NG and Mbih B (2000). A note on the core of voting games. J Math Econ 33: 367–372
Arrow KJ (1963). Social choice and individual values, 2nd edn. Yale University Press, New Haven
Austen-Smith D and Banks JS (1999). Positive political theory I: collective preference. University of Michigan Press, Ann Arbor
Banks JS (1995). Acyclic social choice from finite sets. Soc Choice Welf 12: 293–310
Bartholdi III J, Tovey CA and Trick MA (1989a). Voting schemes for which it can be difficult to tell who won the election. Soc Choice Welf 6: 157–165
Bartholdi III JJ, Tovey CA and Trick MA (1989b). The computational difficulty of manipulating an election. Soc Choice Welf 6: 227–241
Deb R (2004). Rights as alternative game forms. Soc Choice Welf 22: 83–111
Kelly JS (1988). Social choice and computational complexity. J Math Econ 17: 1–8
Kolpin V (1990). Equivalent game forms and coalitional power. Math Soc Sci 20: 239–249
Kumabe M, Mihara HR (2007) Computability of simple games: a complete investigation of the sixty-four possibilities. MPRA Paper 4405, Munich University Library
Kumabe M and Mihara HR (2008). Computability of simple games: a characterization and application to the core. J Math Econ 44: 348–366
Lewis AA (1988). An infinite version of Arrow’s Theorem in the effective setting. Math Soc Sci 16: 41–48
Mihara HR (1997). Arrow’s Theorem and Turing computability. Econ Theory 10: 257–76
Mihara HR (1999). Arrow’s theorem, countably many agents and more visible invisible dictators. J Math Econ 32: 267–287
Mihara HR (2004). Nonanonymity and sensitivity of computable simple games. Math Soc Sci 48: 329–341
Nakamura K (1979). The vetoers in a simple game with ordinal preferences. Int J 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, KJ, Sen, AK and Suzumura, K (eds) Handbook of social choice and welfare, vol 1, chap 8, pp 395–423. Elsevier, Amsterdam
Richter MK and Wong K-C (1999). Computable preference and utility. J Math Econ 32: 339–354
Shapley LS (1962). Simple games: an outline of the descriptive theory. Behav Sci 7: 59–66
Soare RI (1987). Recursively enumerable sets and degrees: a study of computable functions and computably generated sets. Springer, Berlin
Tanaka Y (2007). Type two computability of social choice functions and the Gibbard-Satterthwaite theorem in an infinite society. Appl Math Comput 192: 168–174
Truchon M (1995). Voting games and acyclic collective choice rules. Math Soc Sci 29: 165–179
van Hees M (1999). Liberalism, efficiency and stability: some possibility results. J Econ Theory 88: 294–309
Weber RJ (1994). Games in coalitional form. In: Aumann, RJ and Hart, S (eds) Handbook of game theory, vol 2, chap 36, pp 1285–1303. Elsevier, Amsterdam