Skip to Main content Skip to Navigation
Journal articles

Convexity of graph-restricted games induced by minimum partitions

Abstract : We consider restricted games on weighted graphs associated with minimum partitions. We replace in the classical definition of Myerson restricted game the connected components of any subgraph by the sub-components corresponding to a minimum partition. This minimum partition P min is induced by the deletion of the minimum weight edges. We provide five necessary conditions on the graph edge-weights to have inheritance of convexity from the underlying game to the restricted game associated with P min. Then, we establish that these conditions are also sufficient for a weaker condition, called F-convexity, obtained by restriction of convexity to connected subsets. Moreover, we prove that inheritance of convexity for Myerson restricted game associated with a given graph G is equivalent to inheritance of F-convexity for the P min-restricted game associated with a particular weighted graph G ′ built from G by adding a dominating vertex, and with only two different edge-weights. Then, we prove that G is cycle-complete if and only if a specific condition on adjacent cycles is satisfied on G ′ .
Document type :
Journal articles
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download
Contributor : Alexandre Skoda <>
Submitted on : Monday, October 16, 2017 - 1:05:21 AM
Last modification on : Sunday, January 19, 2020 - 6:38:28 PM
Document(s) archivé(s) le : Wednesday, January 17, 2018 - 12:47:55 PM


Files produced by the author(s)




Alexandre Skoda. Convexity of graph-restricted games induced by minimum partitions. RAIRO - Operations Research, EDP Sciences, In press, ⟨10.1051/ro/2017069⟩. ⟨halshs-01617023⟩



Record views


Files downloads