IDEAS home Printed from https://ideas.repec.org/p/hal/journl/hal-00321625.html
   My bibliography  Save this paper

On the vertices of the k-additive core

Author

Listed:
  • Michel Grabisch

    (CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique)

  • Pedro Miranda

    (UCM - Universidad Complutense de Madrid = Complutense University of Madrid [Madrid])

Abstract

The core of a game v on N, which is the set of additive games φ dominating v such that φ(N)=v(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Möbius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds' theorem for the greedy algorithm), which characterize the vertices of the core.

Suggested Citation

  • Michel Grabisch & Pedro Miranda, 2008. "On the vertices of the k-additive core," Post-Print hal-00321625, HAL.
  • Handle: RePEc:hal:journl:hal-00321625
    DOI: 10.1016/j.disc.2007.09.042
    Note: View the original document on HAL open archive server: https://hal.science/hal-00321625
    as

    Download full text from publisher

    File URL: https://hal.science/hal-00321625/document
    Download Restriction: no

    File URL: https://libkey.io/10.1016/j.disc.2007.09.042?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Other versions of this item:

    Citations

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


    Cited by:

    1. Pedro Miranda & Michel Grabisch, 2012. "An algorithm for finding the vertices of the k-additive monotone core," Post-Print hal-00806905, HAL.
    2. Gonzalez, Stéphane & Grabisch, Michel, 2016. "Multicoalitional solutions," Journal of Mathematical Economics, Elsevier, vol. 64(C), pages 1-10.
    3. Stéphane Gonzalez & Michel Grabisch, 2015. "Preserving coalitional rationality for non-balanced games," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(3), pages 733-760, August.
    4. Miranda, Pedro & Grabisch, Michel, 2010. "k-Balanced games and capacities," European Journal of Operational Research, Elsevier, vol. 200(2), pages 465-472, January.
    5. Michel Grabisch, 2016. "Remarkable polyhedra related to set functions, games and capacities," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 24(2), pages 301-326, July.
    6. Stéphane Gonzalez & Michel Grabisch, 2015. "Autonomous coalitions," Annals of Operations Research, Springer, vol. 235(1), pages 301-317, December.
    7. Grabisch, Michel & Li, Tong, 2011. "On the set of imputations induced by the k-additive core," European Journal of Operational Research, Elsevier, vol. 214(3), pages 697-702, November.
    8. Michel Grabisch, 2016. "Remarkable polyhedra related to set functions, games," Documents de travail du Centre d'Economie de la Sorbonne 16081, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    9. repec:hal:pseose:halshs-01235632 is not listed on IDEAS
    10. repec:hal:pseose:halshs-00881108 is not listed on IDEAS
    11. repec:hal:pseose:hal-01372858 is not listed on IDEAS
    12. E. Sánchez-Rodríguez & P. Borm & A. Estévez-Fernández & M. Fiestras-Janeiro & M. Mosquera, 2015. "$$k$$ k -core covers and the core," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 81(2), pages 147-167, April.
    13. repec:hal:pseose:halshs-01235625 is not listed on IDEAS

    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:hal:journl:hal-00321625. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    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.