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 : Monday, February 5, 2018 - 9:24:01 PM
Long-term archiving on: 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