On the convexity of independent set games

Independent set games are cooperative games defined on graphs, where players are edges and the value of a coalition is the maximum cardinality of independent sets in the subgraph defined by the coalition. In this paper, we investigate the convexity of independent set games, as convex games possess many nice properties both economically and computationally. For independent set games introduced by Deng et al. [5], we provide a necessary and sufficient characterization for the convexity, i.e., every non-pendant edge is incident to a pendant edge in the underlying graph. Our characterization implies that convex instances of independent set games can be recognized efficiently. Besides, we introduce a new class of independent set games and provide a necessary and sufficient characterization for the convexity. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

This paper investigates the convexity of independent set games, providing a necessary and sufficient characterization for convex instances. It also introduces a new class of independent set games and provides a characterization for their convexity.