IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v318y2022i2d10.1007_s10479-021-04374-9.html
   My bibliography  Save this article

On the properties of weighted minimum colouring games

Author

Listed:
  • Herbert Hamers

    (Tilburg University, and TIAS)

  • Nayat Horozoglu

    (London School of Economics and Political Science)

  • Henk Norde

    (Tilburg University)

  • Trine Tornøe Platz

    (University of Copenhagen)

Abstract

A weighted minimum colouring (WMC) game is induced by an undirected graph and a positive weight vector on its vertices. The value of a coalition in a WMC game is determined by the weighted chromatic number of its induced subgraph. A graph G is said to be globally (respectively, locally) WMC totally balanced, submodular, or PMAS-admissible, if for all positive integer weight vectors (respectively, for at least one positive integer weight vector), the corresponding WMC game is totally balanced, submodular or admits a population monotonic allocation scheme (PMAS). We show that a graph G is globally WMC totally balanced if and only if it is perfect, whereas any graph G is locally WMC totally balanced. Furthermore, G is globally (respectively, locally) WMC submodular if and only if it is complete multipartite (respectively, $$(2K_2,P_4)$$ ( 2 K 2 , P 4 ) -free). Finally, we show that G is globally PMAS-admissible if and only if it is $$(2K_2,P_4)$$ ( 2 K 2 , P 4 ) -free, and we provide a partial characterisation of locally PMAS-admissible graphs.

Suggested Citation

  • Herbert Hamers & Nayat Horozoglu & Henk Norde & Trine Tornøe Platz, 2022. "On the properties of weighted minimum colouring games," Annals of Operations Research, Springer, vol. 318(2), pages 963-983, November.
    • Handle: RePEc:spr:annopr:v:318:y:2022:i:2:d:10.1007_s10479-021-04374-9
    DOI: 10.1007/s10479-021-04374-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-021-04374-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-021-04374-9?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
    ---><---

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

    References listed on IDEAS

    as
    1. Çiftçi, BarIs & Borm, Peter & Hamers, Herbert, 2010. "Highway games on weakly cyclic graphs," European Journal of Operational Research, Elsevier, vol. 204(1), pages 117-124, July.
    2. Sprumont, Yves, 1990. "Population monotonic allocation schemes for cooperative games with transferable utility," Games and Economic Behavior, Elsevier, vol. 2(4), pages 378-394, December.
    3. Xiaotie Deng & Toshihide Ibaraki & Hiroshi Nagamochi, 1999. "Algorithmic Aspects of the Core of Combinatorial Optimization Games," Mathematics of Operations Research, INFORMS, vol. 24(3), pages 751-766, August.
    4. Yoshio Okamoto, 2003. "Submodularity of some classes of the combinatorial optimization games," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 58(1), pages 131-139, 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. Hamers, Herbert & Horozoglu, Nayat & Norde, Henk & Platz, Trine Tornoe, 2022. "On the properties of weighted minimum colouring games," Other publications TiSEM ee84d5e4-08d7-4154-9521-2, Tilburg University, School of Economics and Management.
    2. Hamers, H.J.M. & Miquel, S. & Norde, H.W., 2011. "Monotonic Stable Solutions for Minimum Coloring Games," Other publications TiSEM efae8d09-83e6-4fe4-9623-e, Tilburg University, School of Economics and Management.
    3. Hamers, H.J.M. & Miquel, S. & Norde, H.W., 2011. "Monotonic Stable Solutions for Minimum Coloring Games," Discussion Paper 2011-016, Tilburg University, Center for Economic Research.
    4. Stefano Moretti & Henk Norde, 2022. "Some new results on generalized additive games," International Journal of Game Theory, Springer;Game Theory Society, vol. 51(1), pages 87-118, March.
    5. M. Musegaas & P. E. M. Borm & M. Quant, 2016. "Simple and three-valued simple minimum coloring games," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 84(2), pages 239-258, October.
    6. Hamers, H.J.M. & Josune Albizuri, M., 2013. "Graphs Inducing Totally Balanced and Submodular Chinese Postman Games," Other publications TiSEM b1fbd78c-1207-4d55-8313-2, Tilburg University, School of Economics and Management.
    7. Hamers, H.J.M. & Josune Albizuri, M., 2013. "Graphs Inducing Totally Balanced and Submodular Chinese Postman Games," Discussion Paper 2013-006, Tilburg University, Center for Economic Research.
    8. Thomas Bietenhader & Yoshio Okamoto, 2006. "Core Stability of Minimum Coloring Games," Mathematics of Operations Research, INFORMS, vol. 31(2), pages 418-431, May.
    9. Luis Guardiola & Ana Meca & Justo Puerto, 2020. "Quid Pro Quo allocations in Production-Inventory games," Papers 2002.00953, arXiv.org.
    10. Luis A. Guardiola & Ana Meca & Justo Puerto, 2021. "Enforcing fair cooperation in production-inventory settings with heterogeneous agents," Annals of Operations Research, Springer, vol. 305(1), pages 59-80, October.
    11. Han Xiao & Qizhi Fang, 2022. "Population monotonicity in matching games," Journal of Combinatorial Optimization, Springer, vol. 43(4), pages 699-709, May.
    12. Sergei Dotsenko & Vladimir Mazalov, 2021. "A Cooperative Network Packing Game with Simple Paths," Mathematics, MDPI, vol. 9(14), pages 1-18, July.
    13. Sylvain Béal & Marc Deschamps & Catherine Refait-Alexandre & Guillaume Sekli, 2022. "Early contributors, cooperation and fair rewards in crowdfunding," Working Papers hal-04222321, HAL.
    14. Antonio Magaña & Francesc Carreras, 2018. "Coalition Formation and Stability," Group Decision and Negotiation, Springer, vol. 27(3), pages 467-502, June.
    15. Dall'Aglio, M. & Brânzei, R. & Tijs, S.H., 2008. "Cooperation in Dividing the Cake," Discussion Paper 2008-101, Tilburg University, Center for Economic Research.
    16. Sylvain Béal & Eric Rémila & Philippe Solal, 2017. "Axiomatization and implementation of a class of solidarity values for TU-games," Theory and Decision, Springer, vol. 83(1), pages 61-94, June.
    17. Tobias Harks & Martin Hoefer & Anja Schedel & Manuel Surek, 2021. "Efficient Black-Box Reductions for Separable Cost Sharing," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 134-158, February.
    18. Alexandre Skoda & Xavier Venel, 2022. "Weighted Average-convexity and Cooperative Games," Documents de travail du Centre d'Economie de la Sorbonne 22016, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    19. Bouchery, Yann & Hezarkhani, Behzad & Stauffer, Gautier, 2022. "Coalition formation and cost sharing for truck platooning," Transportation Research Part B: Methodological, Elsevier, vol. 165(C), pages 15-34.
    20. van Velzen, S., 2005. "Simple Combinatorial Optimisation Cost Games," Discussion Paper 2005-118, Tilburg University, Center for Economic Research.

    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:spr:annopr:v:318:y:2022:i:2:d:10.1007_s10479-021-04374-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.