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

@article{kumabe-m08jme, 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.}, author = {Kumabe, Masahiro and Mihara, H. R.}, citeulike-article-id = {2818166}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.jmateco.2007.05.012}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6VBY-4NX2NN6-3/1/b54eb912735b9dbe40466b3c80f9eb0f}, comment = {According to Rice's Theorem, any nontrivial property of a partial recursive functions (or recursively enumerable sets) is undecidable. There's no algorithm to tell, given a description (code) of a partial recursive function, whether it satisfies the property. Rice's Theorem is a negative, but powerful result. http://jp.citeulike.org/user/reiju/article/1681987 The main theorem of this paper does for recursive functions (or recursive sets) what Rice's theorem does for partial recursive functions. This variation (?) or version (?), or whatever you call it, of Rice's theorem brings you more positive news. Though appeared in an economic journal, the power of the theorem goes far beyond the game-theoretic applications illustrated in the paper. Recommended to anyone interested in computability theory. ---=note-separator=--- computational social choice? }, doi = {10.1016/j.jmateco.2007.05.012}, journal = {Journal of Mathematical Economics}, keywords = {computability, computable-manuals-and-contracts, computer\_science, cooperative\_game\_theory, economics, infinitely-many-players, nakamura-number, political\_science, recursion-theory, rice-theorem, social\_choice, turing-computability, vita, voting-games}, month = {February}, number = {3-4}, pages = {348--366}, posted-at = {2008-05-21 05:21:14}, priority = {0}, title = {Computability of simple games: A characterization and application to the core}, url = {http://dx.doi.org/10.1016/j.jmateco.2007.05.012}, volume = {44}, year = {2008} }

TY - JOUR ID - kumabe-m08jme L3 - citeulike-article-id:2818166 N2 - 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. IS - 3-4 JF - Journal of Mathematical Economics EP - 366 TI - Computability of simple games: A characterization and application to the core VL - 44 SP - 348 KW - computability KW - computable-manuals-and-contracts KW - computer_science KW - cooperative_game_theory KW - economics KW - infinitely-many-players KW - nakamura-number KW - political_science KW - recursion-theory KW - rice-theorem KW - social_choice KW - turing-computability KW - vita KW - voting-games N1 - According to Rice's Theorem, any nontrivial property of a partial recursive functions (or recursively enumerable sets) is undecidable. There's no algorithm to tell, given a description (code) of a partial recursive function, whether it satisfies the property. Rice's Theorem is a negative, but powerful result. http://jp.citeulike.org/user/reiju/article/1681987 The main theorem of this paper does for recursive functions (or recursive sets) what Rice's theorem does for partial recursive functions. This variation (?) or version (?), or whatever you call it, of Rice's theorem brings you more positive news. Though appeared in an economic journal, the power of the theorem goes far beyond the game-theoretic applications illustrated in the paper. Recommended to anyone interested in computability theory. N1 - computational social choice? AU - Kumabe, Masahiro AU - Mihara, HR PY - 2008/02// UR - http://dx.doi.org/10.1016/j.jmateco.2007.05.012 ER -