Three-valued simple games and applications to minimum coloring problems

We introduce the model of three-valued simple games as a natural extension of simple games. We analyze the core and the Shapley value of three-valued simple games. Using the concept of vital players as an extension of veto players, the vital core is constructed and we show that the vital core is a subset of the core. The Shapley value is characterized on the class of all three-valued simple games.

As an application, we characterize the class of conflict graphs inducing simple or three-valued simple minimum coloring games. We provide an upper bound on the number of maximum cliques of conflict graphs inducing such games. Moreover, it is seen that in case of a perfect conflict graph, the core of an induced three-valued simple minimum coloring game equals the vital core.

Marieke has applied for a position at the Tutor Academy in combination with a postdoc position at our institute