IDEAS home Printed from https://ideas.repec.org/a/spr/reecde/v26y2022i2d10.1007_s10058-021-00265-4.html
   My bibliography  Save this article

Minimum coloring problems with weakly perfect graphs

Author

Listed:
  • Eric Bahel

    (Virginia Polytechnic Institute and State University)

  • Christian Trudeau

    (University of Windsor)

Abstract

The minimum coloring game allows to model economic situations where costly and potentially conflicting tasks have to be executed. The primitives of the game are a graph (describing conflicts between the respective tasks) and a cost function (giving the cost of completing any number of pairwise conflicting tasks). This setting gives rise to a cooperative game where agents have to split the minimum cost of completing all tasks. Our study of the core allows to find a necessary and sufficient condition guaranteeing its non-vacuity; and we describe a subset of allocations that are always in the core (when it is nonempty). These allocations put weights on the incompatible groups with highest cardinality, called maximal cliques. We then propose two cost sharing rules and their axiomatizations. The first rule assigns shares in proportion to the number of maximal cliques an agent belongs to; and the key property in its axiomatization prevents splitting and merging manipulations. The second rule is an extension of the well-known airport rule; and it requires every agent to pay a minimal fraction of the total cost.

Suggested Citation

  • Eric Bahel & Christian Trudeau, 2022. "Minimum coloring problems with weakly perfect graphs," Review of Economic Design, Springer;Society for Economic Design, vol. 26(2), pages 211-231, June.
    • Handle: RePEc:spr:reecde:v:26:y:2022:i:2:d:10.1007_s10058-021-00265-4
    DOI: 10.1007/s10058-021-00265-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10058-021-00265-4
    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/s10058-021-00265-4?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. Hervé Moulin, 1990. "Joint Ownership of a Convex Technology: Comparison of Three Solutions," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 57(3), pages 439-452.
    2. Bahel, Eric & Trudeau, Christian, 2019. "Stability and fairness in the job scheduling problem," Games and Economic Behavior, Elsevier, vol. 117(C), pages 1-14.
    3. Thomas Bietenhader & Yoshio Okamoto, 2006. "Core Stability of Minimum Coloring Games," Mathematics of Operations Research, INFORMS, vol. 31(2), pages 418-431, May.
    4. 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.
    5. Hougaard, Jens Leth & Moulin, Hervé, 2014. "Sharing the cost of redundant items," Games and Economic Behavior, Elsevier, vol. 87(C), pages 339-352.
    6. Maniquet, Francois, 1996. "Allocation Rules for a Commonly Owned Technology: The Average Cost Lower Bound," Journal of Economic Theory, Elsevier, vol. 69(2), pages 490-507, May.
    7. S. C. Littlechild & G. Owen, 1973. "A Simple Expression for the Shapley Value in a Special Case," Management Science, INFORMS, vol. 20(3), pages 370-372, November.
    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. Eric Bahel & Christian Trudeau, 2021. "Minimum coloring problem: the core and beyond," Working Papers 2005, University of Windsor, Department of Economics.
    2. Bahel, Eric & Trudeau, Christian, 2019. "Stability and fairness in the job scheduling problem," Games and Economic Behavior, Elsevier, vol. 117(C), pages 1-14.
    3. Yoshihara, Naoki, 1998. "Characterizations of the public and private ownership solutions," Mathematical Social Sciences, Elsevier, vol. 35(2), pages 165-184, March.
    4. Hervé Moulin & Yves Sprumont, 2007. "Fair allocation of production externalities : recent results," Revue d'économie politique, Dalloz, vol. 117(1), pages 7-36.
    5. Trudeau, Christian & Vidal-Puga, Juan, 2020. "Clique games: A family of games with coincidence between the nucleolus and the Shapley value," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 8-14.
    6. Chambers, Christopher P. & Hayashi, Takashi, 2020. "Can everyone benefit from innovation?," Journal of Mathematical Economics, Elsevier, vol. 88(C), pages 187-191.
    7. Yuntong Wang, 2013. "An Axiomatic Approach to the Airline Emission Fees Problem," Working Papers 1308, University of Windsor, Department of Economics.
    8. 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.
    9. Miguel Ángel Mirás Calvo & Carmen Quinteiro Sandomingo & Estela Sánchez Rodríguez, 2016. "Monotonicity implications for the ranking of rules for airport problems," International Journal of Economic Theory, The International Society for Economic Theory, vol. 12(4), pages 379-400, December.
    10. Boram Park & Suh-Ryung Kim & Hye Kyung Kim, 2013. "On the cores of games arising from integer edge covering functions of graphs," Journal of Combinatorial Optimization, Springer, vol. 26(4), pages 786-798, November.
    11. 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.
    12. Debing Ni & Yuntong Wang, 2013. "Additive cost sharing on a tree," Working Papers 1307, University of Windsor, Department of Economics.
    13. 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.
    14. Léa Munich, 2023. "Schedule Situations and their Cooperative Game Theoretic Representations," Working Papers 2023-08, CRESE.
    15. Corchon, Luis C. & Puy, M. Socorro, 1998. "Individual rationality and voting in cooperative production," Economics Letters, Elsevier, vol. 59(1), pages 83-90, April.
    16. Corchon, Luis C. & Iturbe-Ormaetxe, Inigo, 2001. "A Proposal to Unify Some Concepts in the Theory of Fairness," Journal of Economic Theory, Elsevier, vol. 101(2), pages 540-571, December.
    17. Shellshear, Evan & Sudhölter, Peter, 2009. "On core stability, vital coalitions, and extendability," Games and Economic Behavior, Elsevier, vol. 67(2), pages 633-644, November.
    18. Marcus Berliant & Karl Dunz & William Thomson, 2000. "On the Fairness Literature: Comment," Southern Economic Journal, John Wiley & Sons, vol. 67(2), pages 479-484, October.
    19. Sergei Dotsenko & Vladimir Mazalov, 2021. "A Cooperative Network Packing Game with Simple Paths," Mathematics, MDPI, vol. 9(14), pages 1-18, July.
    20. Martin Shubik, 1984. "The Cooperative Form, the Value and the Allocation of Joint Costs and Benefits," Cowles Foundation Discussion Papers 706, Cowles Foundation for Research in Economics, Yale University.

    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:reecde:v:26:y:2022:i:2:d:10.1007_s10058-021-00265-4. 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.