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

Games induced by the partitioning of a graph

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, PSE - Paris School of Economics - UP1 - Université Paris 1 Panthéon-Sorbonne - ENS-PSL - École normale supérieure - Paris - PSL - Université Paris Sciences et Lettres - EHESS - École des hautes études en sciences sociales - ENPC - École des Ponts ParisTech - CNRS - Centre National de la Recherche Scientifique - INRAE - Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement)

  • Alexandre Skoda

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

Abstract

The paper aims at generalizing the notion of restricted game on a communication graph, introduced by Myerson. We consider communication graphs with weighted edges, and we define arbitrary ways of partitioning any subset of a graph, which we call correspondences. A particularly useful way to partition a graph is obtained by computing the strength of the graph. The strength of a graph is a measure introduced in graph theory to evaluate the resistance of networks under attacks, and it provides a natural partition of the graph (called the Gusfield correspondence) into resistant components. We perform a general study of the inheritance of superadditivity and convexity for the restricted game associated with a given correspondence. Our main result is to give for cycle-free graphs necessary and sufficient conditions for the inheritance of convexity of the restricted game associated with the Gusfield correspondence.

Suggested Citation

  • Michel Grabisch & Alexandre Skoda, 2012. "Games induced by the partitioning of a graph," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) hal-00830291, HAL.
    • Handle: RePEc:hal:cesptp:hal-00830291
    DOI: 10.1007/s10479-012-1200-8
    Note: View the original document on HAL open archive server: https://hal.science/hal-00830291
    as

    Download full text from publisher

    File URL: https://hal.science/hal-00830291/document
    Download Restriction: no
    File URL: https://libkey.io/10.1007/s10479-012-1200-8?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:

    References listed on IDEAS

    as
    1. Michel Grabisch, 2013. "The core of games on ordered structures and graphs," Annals of Operations Research, Springer, vol. 204(1), pages 33-64, April.
    2. Roger B. Myerson, 1977. "Graphs and Cooperation in Games," Mathematics of Operations Research, INFORMS, vol. 2(3), pages 225-229, August.
    3. van den Nouweland, Anne & Borm, Peter, 1991. "On the Convexity of Communication Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 19(4), pages 421-430.
    4. E. Algaba & J.M. Bilbao & J.J. López, 2001. "A unified approach to restricted games," Theory and Decision, Springer, vol. 50(4), pages 333-345, June.
    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. Alexandre Skoda, 2016. "Inheritance of Convexity for Partition Restricted Games," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-01318105, HAL.
    2. Alexandre Skoda, 2016. "Convexity of Network Restricted Games Induced by Minimum Partitions," Documents de travail du Centre d'Economie de la Sorbonne 16019, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    3. Alexandre Skoda, 2017. "Inheritance of Convexity for the P min-Restricted Game," Post-Print halshs-01660670, HAL.
    4. Ata Atay & Marina Núñez, 2019. "Multi-sided assignment games on m-partite graphs," Annals of Operations Research, Springer, vol. 279(1), pages 271-290, August.
    5. Alexandre Skoda, 2017. "Convexity of Graph-Restricted Games Induced by Minimum Partitions," Documents de travail du Centre d'Economie de la Sorbonne 17049, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    6. Alexandre Skoda, 2016. "Complexity of inheritance of F-convexity for restricted games induced by minimum partitions," Post-Print halshs-01382502, HAL.
    7. Alexandre Skoda, 2017. "Convexity of Graph-Restricted Games Induced by Minimum Partitions," Post-Print halshs-01659804, HAL.
    8. Alexandre Skoda, 2020. "Inheritance of Convexity for the P˜min-Restricted Game," Post-Print halshs-02967120, HAL.
    9. Alexandre Skoda, 2016. "Inheritance of Convexity for Partition Restricted Games," Post-Print halshs-01318105, HAL.
    10. Alexandre Skoda, 2017. "Convexity of Graph-Restricted Games Induced by Minimum Partitions," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-01659804, HAL.
    11. Alexandre Skoda, 2016. "Inheritance of Convexity for Partition Restricted," Documents de travail du Centre d'Economie de la Sorbonne 16040, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    12. Alexandre Skoda, 2020. "Inheritance of Convexity for the P˜min-Restricted Game," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-02967120, HAL.
    13. Alexandre Skoda, 2019. "Convexity of graph-restricted games induced by minimum partitions," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-01617023, HAL.
    14. Jerome Galtier, 2018. "Fast approximation of matroid packing and covering," Annals of Operations Research, Springer, vol. 271(2), pages 575-598, December.
    15. Alexandre Skoda, 2016. "Complexity of inheritance of F-convexity for restricted games induced by minimum partitions," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-01382502, HAL.
    16. Alexandre Skoda, 2020. "Inheritance of Convexity for the P˜min-Restricted Game," Documents de travail du Centre d'Economie de la Sorbonne 20020, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    17. Alexandre Skoda, 2017. "Inheritance of Convexity for the P min-Restricted Game," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-01660670, HAL.
    18. Alexandre Skoda, 2019. "Convexity of graph-restricted games induced by minimum partitions," Post-Print halshs-01617023, HAL.
    19. Alexandre Skoda, 2017. "Inheritance of Convexity for the Pmin-Restricted Game," Documents de travail du Centre d'Economie de la Sorbonne 17051, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    20. Alexandre Skoda, 2016. "Convexity of Network Restricted Games Induced by Minimum Partitions," Post-Print hal-01305005, HAL.
    21. Alexandre Skoda, 2016. "Complexity of inheritance of F-convexity for restricted games induced by minimum partitions," Documents de travail du Centre d'Economie de la Sorbonne 16055, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    22. Alexandre Skoda, 2016. "Convexity of Network Restricted Games Induced by Minimum Partitions," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) hal-01305005, HAL.

    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. Alexandre Skoda, 2019. "Convexity of graph-restricted games induced by minimum partitions," Post-Print halshs-01617023, HAL.
    2. Michel Grabisch, 2013. "The core of games on ordered structures and graphs," Annals of Operations Research, Springer, vol. 204(1), pages 33-64, April.
    3. Alexandre Skoda, 2020. "Inheritance of Convexity for the P˜min-Restricted Game," Post-Print halshs-02967120, HAL.
    4. Alexandre Skoda, 2016. "Inheritance of Convexity for Partition Restricted," Documents de travail du Centre d'Economie de la Sorbonne 16040, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    5. Alexandre Skoda, 2017. "Inheritance of Convexity for the P min-Restricted Game," Post-Print halshs-01660670, HAL.
    6. Alexandre Skoda, 2016. "Inheritance of Convexity for Partition Restricted Games," Post-Print halshs-01318105, HAL.
    7. Alexandre Skoda, 2020. "Inheritance of Convexity for the P˜min-Restricted Game," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-02967120, HAL.
    8. Alexandre Skoda, 2017. "Inheritance of Convexity for the P min-Restricted Game," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-01660670, HAL.
    9. Alexandre Skoda, 2017. "Convexity of Graph-Restricted Games Induced by Minimum Partitions," Post-Print halshs-01659804, HAL.
    10. Alexandre Skoda, 2017. "Convexity of Graph-Restricted Games Induced by Minimum Partitions," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-01659804, HAL.
    11. Alexandre Skoda, 2017. "Inheritance of Convexity for the Pmin-Restricted Game," Documents de travail du Centre d'Economie de la Sorbonne 17051, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    12. Alexandre Skoda, 2020. "Inheritance of Convexity for the P˜min-Restricted Game," Documents de travail du Centre d'Economie de la Sorbonne 20020, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    13. Alexandre Skoda, 2016. "Inheritance of Convexity for Partition Restricted Games," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-01318105, HAL.
    14. Alexandre Skoda, 2019. "Convexity of graph-restricted games induced by minimum partitions," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-01617023, HAL.
    15. Alexandre Skoda, 2017. "Convexity of Graph-Restricted Games Induced by Minimum Partitions," Documents de travail du Centre d'Economie de la Sorbonne 17049, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    16. Alexandre Skoda, 2016. "Convexity of Network Restricted Games Induced by Minimum Partitions," Documents de travail du Centre d'Economie de la Sorbonne 16019, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    17. Michel Grabisch & Alexandre Skoda, 2011. "Coalition structures induced by the strength of a graph," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) halshs-00639685, HAL.
    18. Alexandre Skoda, 2016. "Convexity of Network Restricted Games Induced by Minimum Partitions," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) hal-01305005, HAL.
    19. Rene van den Brink & Ilya Katsev & Gerard van der Laan, 2023. "Properties of Solutions for Games on Union-Closed Systems," Mathematics, MDPI, vol. 11(4), pages 1-16, February.
    20. René Brink, 2017. "Games with a permission structure - A survey on generalizations and applications," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(1), pages 1-33, April.

    More about this item

    Keywords

    Communication networks; Coalition structure; Cooperative game; Strength of a graph;
    All these keywords.

    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:hal:cesptp:hal-00830291. 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: 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.