Nothing Special   »   [go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/p/mse/cesdoc/23001.html
   My bibliography  Save this paper

Minimal balanced collections: generation, applications and generalization

Author

Abstract
Minimal balanced collections are a generalization of partitions of a finite set of n elements and have important applications in cooperative game theory and discrete mathematics. However, their number is not known beyond n = 4. in this paper we investigate the problem of generating minimal balanced collections and implement the Peleg algorithm, permitting to generate all minimal balanced collections till n = 7. Secondly, we provide pratical algorithms to check many properties of coalitions and games, based on minimal balanced collections, in a way which is faster than linear programming based methods. In particular we construct an algorithm to check if the core of a cooperative game is a stable set in the sense of von Neumann and Morgenstern. The algorithm implements a theorem according to which the core is a stable set if and only if a certain nested balancedness condition is valid. The second level of this condition requires to generalize the notion of balanced collection to balanced sets

Suggested Citation

  • Dylan Laplace Mermoud & Michel Grabisch & Peter Sudh lter, 2023. "Minimal balanced collections: generation, applications and generalization," Documents de travail du Centre d'Economie de la Sorbonne 23001, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    • Handle: RePEc:mse:cesdoc:23001
    as

    Download full text from publisher

    File URL: http://mse.univ-paris1.fr/pub/mse/CES2023/23001.pdf
    Download Restriction: no
    File URL: https://shs.hal.science/halshs-03972833
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Peleg, B, 1986. "On the Reduced Game Property and Its Converse," International Journal of Game Theory, Springer;Game Theory Society, vol. 15(3), pages 187-200.
    2. Bezalel Peleg, 1965. "An inductive method for constructing mimmal balanced collections of finite sets," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 12(2), pages 155-162, June.
    3. Derks, Jean & Peters, Hans, 1998. "Orderings, excess functions, and the nucleolus," Mathematical Social Sciences, Elsevier, vol. 36(2), pages 175-182, September.
    Full references (including those not matched with items on IDEAS)

    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. Jean Derks & Hans Peters & Peter Sudhölter, 2014. "On extensions of the core and the anticore of transferable utility games," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(1), pages 37-63, February.
    2. E. Calvo & E. Gutiérrez, 1996. "A prekernel characterization by means of stability properties," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 4(2), pages 257-267, December.
    3. Nunez, Marina & Rafels, Carles, 2003. "Characterization of the extreme core allocations of the assignment game," Games and Economic Behavior, Elsevier, vol. 44(2), pages 311-331, August.
    4. Camelia Bejan & Juan Gómez, 2012. "Axiomatizing core extensions," International Journal of Game Theory, Springer;Game Theory Society, vol. 41(4), pages 885-898, November.
    5. Bossert, Walter & Derks, Jean & Peters, Hans, 2005. "Efficiency in uncertain cooperative games," Mathematical Social Sciences, Elsevier, vol. 50(1), pages 12-23, July.
    6. Nir Dagan, 1995. "Consistent Solutions in Exchange Economies: a Characterization of the Price Mechanism," Economic theory and game theory 011, Nir Dagan.
    7. Sylvain Béal & Stéphane Gonzalez & Philippe Solal & Peter Sudhölter, 2023. "Axiomatic characterizations of the core without consistency," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(3), pages 687-701, September.
    8. Peleg, Bezalel & Tijs, Stef, 1996. "The Consistency Principle for Games in Strategic Forms," International Journal of Game Theory, Springer;Game Theory Society, vol. 25(1), pages 13-34.
    9. Voorneveld, M. & van den Nouweland, C.G.A.M., 1998. "Cooperative Multicriteria Games with Public and Private Criteria : An Investigation of Core Concepts," Discussion Paper 1998-62, Tilburg University, Center for Economic Research.
    10. Ichiro Nishizaki & Tomohiro Hayashida & Yuki Shintomi, 2016. "A core-allocation for a network restricted linear production game," Annals of Operations Research, Springer, vol. 238(1), pages 389-410, March.
    11. Roberto Serrano, 2007. "Cooperative Games: Core and Shapley Value," Working Papers wp2007_0709, CEMFI.
    12. repec:ebl:ecbull:v:3:y:2008:i:70:p:1-8 is not listed on IDEAS
    13. Stéphane Gonzalez & Aymeric Lardon, 2018. "Optimal deterrence of cooperation," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(1), pages 207-227, March.
    14. William Thomson, 2011. "Consistency and its converse: an introduction," Review of Economic Design, Springer;Society for Economic Design, vol. 15(4), pages 257-291, December.
    15. Lohmann, E. & Borm, P. & Herings, P.J.J., 2012. "Minimal exact balancedness," Mathematical Social Sciences, Elsevier, vol. 64(2), pages 127-135.
    16. Anne van den Nouweland, 2011. "Comments on: Cooperative games and cost allocation problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 19(1), pages 29-32, July.
    17. Béal, Sylvain & Rémila, Eric & Solal, Philippe, 2010. "On the number of blocks required to access the core," MPRA Paper 26578, University Library of Munich, Germany.
    18. Akira Okada & Eyal Winter, 2002. "A Non-cooperative Axiomatization of the Core," Theory and Decision, Springer, vol. 53(1), pages 1-28, August.
    19. Stéphane Gonzalez & Michel Grabisch, 2015. "Autonomous coalitions," Annals of Operations Research, Springer, vol. 235(1), pages 301-317, December.
    20. Michel Grabisch & Peter Sudhölter, 2012. "The bounded core for games with precedence constraints," Annals of Operations Research, Springer, vol. 201(1), pages 251-264, December.
    21. Pedro Calleja & Francesc Llerena & Peter Sudhölter, 2020. "Monotonicity and Weighted Prenucleoli: A Characterization Without Consistency," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 1056-1068, August.

    More about this item

    Keywords

    minimal balanced collection; cooperative game; core; stable set; hypergraph; algorithm;
    All these keywords.

    JEL classification:

    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
    • C44 - Mathematical and Quantitative Methods - - Econometric and Statistical Methods: Special Topics - - - Operations Research; Statistical Decision Theory

    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:mse:cesdoc:23001. 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: Lucie Label (email available below). General contact details of provider: https://edirc.repec.org/data/cenp1fr.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.