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

https://halshs.archives-ouvertes.fr/halshs-01617023
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

File

articleSkoda-Pmin8.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

156

Files downloads

365