IDEAS home Printed from https://ideas.repec.org/a/eee/mateco/v47y2011i2p150-158.html
   My bibliography  Save this article

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 algorithmic 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 ones 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, 2011. "Computability of simple games: A complete investigation of the sixty-four possibilities," Journal of Mathematical Economics, Elsevier, vol. 47(2), pages 150-158, March.
    • Handle: RePEc:eee:mateco:v:47:y:2011:i:2:p:150-158
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0304406811000073
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to look for a different version below or search for a different version of it.

    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, September.
    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. 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.
    6. 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.
    7. 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.
    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. Lang, Matthias, 2019. "Communicating subjective evaluations," Journal of Economic Theory, Elsevier, vol. 179(C), pages 163-199.
    12. Xefteris, Dimitrios, 2017. "Multidimensional electoral competition between differentiated candidates," Games and Economic Behavior, Elsevier, vol. 105(C), pages 112-121.
    13. Anderlini, Luca & Felli, Leonardo, 2004. "Bounded rationality and incomplete contracts," Research in Economics, Elsevier, vol. 58(1), pages 3-30, March.
    14. Tovey, Craig A., 2010. "The instability of instability of centered distributions," Mathematical Social Sciences, Elsevier, vol. 59(1), pages 53-73, January.
    15. Matthias Lang, 2020. "Mechanism Design with Narratives," CESifo Working Paper Series 8502, CESifo.
    16. Tovey, Craig A., 2010. "The almost surely shrinking yolk," Mathematical Social Sciences, Elsevier, vol. 59(1), pages 74-87, January.
    17. 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.
    18. Ragavendran Gopalakrishnan & Jason R. Marden & Adam Wierman, 2014. "Potential Games Are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 1252-1296, November.
    19. Qizhi Fang & Bo Li & Xiaohan Shan & Xiaoming Sun, 2018. "Path cooperative games," Journal of Combinatorial Optimization, Springer, vol. 36(1), pages 211-229, July.
    20. 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.

    More about this item

    Keywords

    Voting games Axiomatic method Complete independence Turing computability Multi-criterion decision-making;

    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

    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:eee:mateco:v:47:y:2011:i:2:p:150-158. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/jmateco .

    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.