Totally balanced combinatorial optimization games (Q1575068)

A cooperative game is said to be balanced if for every subgame defined on a subset \(S\subset V\) of players, the core is nonempty. The authors study the total balancedness of a number of cooperative optimization games, in which the cost function \(c(S)\) for any subset \(S\subseteq V\) of players arises as the solution of a combinatorial optimization problem on \(S\). In particular, they give a complete characterization of total balancedness for a class of partition game. For packing and covering games, a correspondence of total balancedness between primal and dual problem (i.e., a packing and a covering game) is established. Finally it is shown that matching games are totally balanced precisely for bipartite graphs, while a minimum coloring game on a graph \(G\) is totally balanced if and only \(G\) is perfect. This paper can be considered a sequel to the paper by the first three authors [Math. Oper. Res. 24, 751-766 (1999; Zbl 1064.91505)]that considers the core of optimization games.