On the convexity of independent set games

DOI10.1016/J.DAM.2020.09.025MaRDI QIDQ2659079zbMATH OpenOpenAlexFDO

Authors Han Xiao, Yuanxi Wang, Qizhi Fang

Publication date 25 March 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.03169

zbMATH Keywords

convexitycooperative gameindependent set

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Combinatorial games (91A46)

Abstract: 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. (Math. Oper. Res., 24:751-766, 1999), 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 immediately yields a polynomial time algorithm for recognizing convex instances of independent set games. Besides, we introduce a new class of independent set games and provide an efficient characterization for the convexity.

Recommendations

• A combinatorial characterization for population monotonic allocations in convex independent set games
• Characterizations ofk-Convex Games
• Cores of convex games
• scientific article; zbMATH DE number 4077005
• scientific article; zbMATH DE number 1163151

Cites work

• scientific article; zbMATH DE number 3750720 (Why is no real title available?)
• A Simple Expression for the Shapley Value in a Special Case
• Algorithmic Aspects of the Core of Combinatorial Optimization Games
• An efficient characterization of submodular spanning tree games
• Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Cores of convex games
• Game theoretic analysis of a bankruptcy problem from the Talmud
• Geometric algorithms and combinatorial optimization.
• Graphs inducing totally balanced and submodular Chinese postman games
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• On games corresponding to sequencing situations with ready times
• On the concavity of delivery games
• On the convexity of communication games
• On the submodularity of multi-depot traveling salesman games
• Sequencing games
• Submodularity of minimum-cost spanning tree games
• Submodularity of some classes of the combinatorial optimization games
• The kernel and bargaining set for convex games

Cited in

(7)

• On independent cliques and linear complementarity problems
• Inheritance of convexity for the \(\mathcal{P}_{\min}\)-restricted game
• Multiplayer boycotts in convex games
• Stable sets and max-convex decompositions of TU games
• On the population monotonicity of independent set games
• scientific article; zbMATH DE number 19353 (Why is no real title available?)
• A combinatorial characterization for population monotonic allocations in convex independent set games

This page was built for publication: On the convexity of independent set games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2659079)