Balancedness of edge covering games

In this work we discuss two related cooperative games, relaxed and rigid edge covering games, which arise from edge covering problems on graphs. On the basis of a new 0–1 program formulation for edge covering problems and LP duality theory, we obtain a common necessary and sufficient condition on the balancedness of both edge covering games.