Totally balanced combinatorial optimization games

Combinatorial optimization games deal with cooperative games for which the value of every subset of players is obtained by solving a combinatorial opt imization problem on the resources collectively owned by this subset. A sol ution of the game is in the cure if no subset of players is able to gain ad vantage by breaking away from this collective decision of all players. The game is totally balanced if and only if the core is non-empty For every ind uced subgame of it. We study the total balancedness of several combinatorial optimization games in this paper. For a class of the partition game [5], we have a complete c haracterization fur the total balancedness. For the packing and covering ga mes [3], we completely clarify the relationship between the related primal/ dual lineal programs for the corresponding games to be totally balanced. Ou r work opens up the question of fully characterizing the combinatorial stru ctures of totally balanced packing and covering games, for which we present some interesting examples: the totally balanced matching, vertex cover, an d minimum coloring games.