On the convexity of independent set games
From MaRDI portal
Publication:2659079
DOI10.1016/J.DAM.2020.09.025zbMATH Open1460.05130arXiv1911.03169OpenAlexW3113891798MaRDI QIDQ2659079FDOQ2659079
Authors: Han Xiao, Yuanxi Wang, Qizhi Fang 
Publication date: 25 March 2021
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1911.03169
Recommendations
Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Combinatorial games (91A46)
Cites Work
- Game theoretic analysis of a bankruptcy problem from the Talmud
- A Simple Expression for the Shapley Value in a Special Case
- Sequencing games
- On the concavity of delivery games
- Submodularity of some classes of the combinatorial optimization games
- Graphs inducing totally balanced and submodular Chinese postman games
- Cores of convex games
- The kernel and bargaining set for convex games
- Independence numbers of graphs - an extension of the Koenig-Egervary theorem
- Geometric algorithms and combinatorial optimization.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Algorithmic Aspects of the Core of Combinatorial Optimization Games
- On games corresponding to sequencing situations with ready times
- On the convexity of communication games
- Title not available (Why is that?)
- Characterizations of Natural Submodular Graphs: A Polynomially Solvable Class of the TSP
- On the submodularity of multi-depot traveling salesman games
- An efficient characterization of submodular spanning tree games
- Submodularity of minimum-cost spanning tree games
Cited In (7)
- A combinatorial characterization for population monotonic allocations in convex independent set games
- Inheritance of convexity for the \(\mathcal{P}_{\min}\)-restricted game
- Title not available (Why is that?)
- Multiplayer boycotts in convex games
- Stable sets and max-convex decompositions of TU games
- On independent cliques and linear complementarity problems
- On the population monotonicity of 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)
