| Abstract: | Submodularity (or concavity) is considered as an important property in the field of cooperative game theory. In this article, we characterize submodular minimum coloring games and submodular minimum vertex cover games. These characterizations immediately show that it can be decided in polynomial time that the minimum coloring game or the minimum vertex cover game on a given graph is submodular or not. Related to these results, the Shapley values are also investigated.Supported by the Berlin-Zürich Joint Graduate Program  Combinatorics, Geometry, and Computation (CGC), financed by ETH Zürich and the German Science Foundation (DFG). |
