Minimum coloring problems with weakly perfect graphs

Eric Bahel () and Christian Trudeau
Additional contact information
Eric Bahel: Virginia Polytechnic Institute and State University

Review of Economic Design, 2022, vol. 26, issue 2, No 4, 231 pages

Abstract: 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.

Keywords: Minimum coloring game; Cost sharing; Merge-proofness; Unanimity lower bound; classification: C71; D63 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10058-021-00265-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:reecde:v:26:y:2022:i:2:d:10.1007_s10058-021-00265-4

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/10058

DOI: 10.1007/s10058-021-00265-4

Access Statistics for this article

Review of Economic Design is currently edited by Atila Abdulkadiroglu, Fuhito Kojima and Tilman Börgers

More articles in Review of Economic Design from Springer, Society for Economic Design
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().