In this presentation, we present an overview of the characterization of properties of several classes of coloring games in terms of the underlying graph.
First, we discuss the class of minimum coloring games introduced by Deng et al. (1999). Here totally balancedness, existence of PMAS and submodularity are characterized by perfect graphs, 2K2P4 -free graphs and complete r-partite graphs, respectively (cf. Deng et al. (2000), Hamers et al. (2014), Okamoto (2003)).
Second, we discuss the class of weighted minimum coloring games introduced by Hamers et al. (2019). Here global (local) totally balancedness and global (local) submodularity are characterized by perfect graphs (any graph) and complete r-partite graphs (2K2P4 -free graphs), respectively.
Finally, we discuss the class of multiple player coloring games introduced in Hamers et al. (2020). Here we present some preliminary results.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Deng, X., Ibaraki, T., Nagamochi, H., 1999. Algorithmic aspects of the core of combinatorial optimization games. Mathematics of Operations Research 24(3), 751–766.
Deng, X., Ibaraki, T., Nagamochi, H., Zang, W., 2000. Totally balanced combinatorial optimization games. Mathematical Programming 87, 441–452.
Hamers, H., Miquel, S., Norde, H., 2014. Monotonic stable solutions for minimum coloring games. Mathematical Programming 145, 509–529.
Hamers, H., Horozoglu, N., Norde, H., Tornoe Platz, T. On totally balanced, submodular and PMAS-admissible weighted minimum coloring games (submitted).
Hamers, H., Miquel, S., Norde, H., Obadi, S. On submodular multiple minimum coloring games (in preparation).
Okamoto, Y., 2003. Submodularity of some classes of the combinatorial optimization games. Mathematical Methods of Operations Research 58(1), 131–139.
If you wish to receive a link for the zoom meeting on the day of the event, please send an email to Tamás Solymosi (tamas dot solymosi at uni dash corvinus dot hu)