IDEAS home Printed from https://ideas.repec.org/p/pra/mprapa/440.html
   My bibliography  Save this paper

Computability of simple games: A complete investigation of the sixty-four possibilities

Author

Listed:
  • Kumabe, Masahiro
  • Mihara, H. Reiju

Abstract

Classify simple games into sixteen "types" in terms of the four conventional axioms: monotonicity, properness, strongness, and nonweakness. Further classify them into sixty-four classes in terms of finiteness (existence of a finite carrier) and computability. For each such class, we either show that it is empty or give an example of a game belonging to it. We observe that if a type contains an infinite game, then it contains both computable infinitegames and noncomputable ones. This strongly suggests that computability is logically, as well as conceptually, unrelated to the conventional axioms.

Suggested Citation

  • Kumabe, Masahiro & Mihara, H. Reiju, 2006. "Computability of simple games: A complete investigation of the sixty-four possibilities," MPRA Paper 440, University Library of Munich, Germany.
    • Handle: RePEc:pra:mprapa:440
    as

    Download full text from publisher

    File URL: https://mpra.ub.uni-muenchen.de/440/1/MPRA_paper_440.pdf
    File Function: original version
    Download Restriction: no
    File URL: https://mpra.ub.uni-muenchen.de/4405/1/MPRA_paper_4405.pdf
    File Function: revised version
    Download Restriction: no
    File URL: https://mpra.ub.uni-muenchen.de/29000/1/MPRA_paper_29000.pdf
    File Function: revised version
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Peleg,Bezalel, 2008. "Game Theoretic Analysis of Voting in Committees," Cambridge Books, Cambridge University Press, number 9780521074650.
    2. Luca Anderlini & Leonardo Felli, 1994. "Incomplete Written Contracts: Undescribable States of Nature," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 109(4), pages 1085-1124.
    3. Richter, Marcel K. & Wong, Kam-Chau, 1999. "Computable preference and utility," Journal of Mathematical Economics, Elsevier, vol. 32(3), pages 339-354, November.
    4. H. Reiju Mihara, 1997. "Arrow's Theorem and Turing computability," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 10(2), pages 257-276.
    5. Masahiro Kumabe & H. Reiju Mihara, 2008. "The Nakamura numbers for computable simple games," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 31(4), pages 621-640, December.
    6. Weber, Robert J., 1994. "Games in coalitional form," Handbook of Game Theory with Economic Applications, in: R.J. Aumann & S. Hart (ed.), Handbook of Game Theory with Economic Applications, edition 1, volume 2, chapter 36, pages 1285-1303, Elsevier.
    7. Nabil I. Al-Najjar & Luca Anderlini & Leonardo Felli, 2006. "Undescribable Events," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 73(4), pages 849-868.
    8. Kumabe, Masahiro & Mihara, H. Reiju, 2011. "Preference aggregation theory without acyclicity: The core without majority dissatisfaction," Games and Economic Behavior, Elsevier, vol. 72(1), pages 187-201, May.
    9. Mihara, H. Reiju, 2004. "Nonanonymity and sensitivity of computable simple games," Mathematical Social Sciences, Elsevier, vol. 48(3), pages 329-341, November.
    10. Kumabe, Masahiro & Mihara, H. Reiju, 2008. "Computability of simple games: A characterization and application to the core," Journal of Mathematical Economics, Elsevier, vol. 44(3-4), pages 348-366, February.
    11. K. J. Arrow & A. K. Sen & K. Suzumura (ed.), 2002. "Handbook of Social Choice and Welfare," Handbook of Social Choice and Welfare, Elsevier, edition 1, volume 1, number 1.
    12. Xiaotie Deng & Christos H. Papadimitriou, 1994. "On the Complexity of Cooperative Solution Concepts," Mathematics of Operations Research, INFORMS, vol. 19(2), pages 257-266, May.
    13. Mihara, H. Reiju, 1999. "Arrow's theorem, countably many agents, and more visible invisible dictators1," Journal of Mathematical Economics, Elsevier, vol. 32(3), pages 267-287, November.
    14. Kelly, Jerry S., 1988. "Social choice and computational complexity," Journal of Mathematical Economics, Elsevier, vol. 17(1), pages 1-8, February.
    15. Anthony Downs, 1957. "An Economic Theory of Political Action in a Democracy," Journal of Political Economy, University of Chicago Press, vol. 65(2), pages 135-135.
    16. Banks, Jeffrey S. & Duggan, John & Le Breton, Michel, 2006. "Social choice and electoral competition in the general spatial model," Journal of Economic Theory, Elsevier, vol. 126(1), pages 194-234, January.
    17. Lewis, Alain A., 1988. "An infinite version of arrow's theorem in the effective setting," Mathematical Social Sciences, Elsevier, vol. 16(1), pages 41-48, August.
    18. H. Reiju Mihara, 1997. "Arrow's Theorem, countably many agents, and more visible invisible dictators," Public Economics 9705001, University Library of Munich, Germany, revised 01 Jun 2004.
    19. Shanfeng Zhu & Xiaotie Deng & Maocheng Cai & Qizhi Fang, 2002. "On computational complexity of membership test in flow games and linear production games," International Journal of Game Theory, Springer;Game Theory Society, vol. 31(1), pages 39-45.
    20. William Thomson, 2001. "On the axiomatic method and its recent applications to game theory and resource allocation," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 18(2), pages 327-386.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Masahiro Kumabe & H. Reiju Mihara, 2008. "The Nakamura numbers for computable simple games," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 31(4), pages 621-640, December.
    2. Kumabe, Masahiro & Mihara, H. Reiju, 2008. "Computability of simple games: A characterization and application to the core," Journal of Mathematical Economics, Elsevier, vol. 44(3-4), pages 348-366, February.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Kumabe, Masahiro & Mihara, H. Reiju, 2008. "Computability of simple games: A characterization and application to the core," Journal of Mathematical Economics, Elsevier, vol. 44(3-4), pages 348-366, February.
    2. Masahiro Kumabe & H. Reiju Mihara, 2008. "The Nakamura numbers for computable simple games," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 31(4), pages 621-640, December.
    3. Mihara, H. Reiju, 2004. "Nonanonymity and sensitivity of computable simple games," Mathematical Social Sciences, Elsevier, vol. 48(3), pages 329-341, November.
    4. Kumabe, Masahiro & Mihara, H. Reiju, 2011. "Preference aggregation theory without acyclicity: The core without majority dissatisfaction," Games and Economic Behavior, Elsevier, vol. 72(1), pages 187-201, May.
    5. Mihara, H. Reiju, 1999. "Arrow's theorem, countably many agents, and more visible invisible dictators1," Journal of Mathematical Economics, Elsevier, vol. 32(3), pages 267-287, November.
    6. H. Reiju Mihara, 1997. "Arrow's Theorem, countably many agents, and more visible invisible dictators," Public Economics 9705001, University Library of Munich, Germany, revised 01 Jun 2004.
    7. Andrei Gomberg & César Martinelli & Ricard Torres, 2005. "Anonymity in large societies," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 25(1), pages 187-205, October.
    8. Potgieter, Petrus H. & Rosinger, Elemér E., 2007. "Is Economics Entering its Post-Witchcraft Era?," MPRA Paper 3340, University Library of Munich, Germany.
    9. Ricard Torres, 2002. "Smallness of Invisible Dictators," Working Papers 0213, Centro de Investigacion Economica, ITAM, revised Sep 2003.
    10. Azar, Pablo D. & Micali, Silvio, 2018. "Computational principal agent problems," Theoretical Economics, Econometric Society, vol. 13(2), May.
    11. Xefteris, Dimitrios, 2017. "Multidimensional electoral competition between differentiated candidates," Games and Economic Behavior, Elsevier, vol. 105(C), pages 112-121.
    12. Tovey, Craig A., 2010. "The instability of instability of centered distributions," Mathematical Social Sciences, Elsevier, vol. 59(1), pages 53-73, January.
    13. Matthias Lang, 2020. "Mechanism Design with Narratives," CESifo Working Paper Series 8502, CESifo.
    14. Norbert Brunner & H. Reiju Mihara, 1999. "Arrow's theorem, Weglorz' models and the axiom of choice," Public Economics 9902001, University Library of Munich, Germany, revised 01 Jun 2004.
    15. M’hand Fares, 2011. "Can a specific performance contract solve the hold-up problem? [Un contrat à obligation d’exécution peut-il résoudre le problème du hold-up ?]," Post-Print hal-02647357, HAL.
    16. Koji Takamiya & Akira Tanaka, 2016. "Computational complexity in the design of voting rules," Theory and Decision, Springer, vol. 80(1), pages 33-41, January.
    17. Diego Dominguez, 2013. "Lower bounds and recursive methods for the problem of adjudicating conflicting claims," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 40(3), pages 663-678, March.
    18. Xiaotie Deng & Qizhi Fang & Xiaoxun Sun, 2009. "Finding nucleolus of flow game," Journal of Combinatorial Optimization, Springer, vol. 18(1), pages 64-86, July.
    19. Mihara, H. Reiju, 2017. "Characterizing the Borda ranking rule for a fixed population," MPRA Paper 78093, University Library of Munich, Germany.
    20. Nicholas G. Hall & Zhixin Liu, 2010. "Capacity Allocation and Scheduling in Supply Chains," Operations Research, INFORMS, vol. 58(6), pages 1711-1725, December.

    More about this item

    Keywords

    Voting games; infinitely many players; axiomatic method; complete independence; algorithms; Turing computability; recursion theory;
    All these keywords.

    JEL classification:

    • D90 - Microeconomics - - Micro-Based Behavioral Economics - - - General
    • C69 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Other
    • D71 - Microeconomics - - Analysis of Collective Decision-Making - - - Social Choice; Clubs; Committees; Associations
    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:pra:mprapa:440. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Joachim Winter (email available below). General contact details of provider: https://edirc.repec.org/data/vfmunde.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.