Convexity of graph-restricted games induced by minimum partitions

Alexandre Skoda ()
Additional contact information
Alexandre Skoda: UP1 - Université Paris 1 Panthéon-Sorbonne, CES - Centre d'économie de la Sorbonne - UP1 - Université Paris 1 Panthéon-Sorbonne - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

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 ′ .

Keywords: restricted game; convex game; partitions; communication networks; cooperative game (search for similar items in EconPapers)
Date: 2019-07
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-01617023v1
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Published in RAIRO - Operations Research, 2019, 53 (3), pp.841-866. ⟨10.1051/ro/2017069⟩

Downloads: (external link)
https://shs.hal.science/halshs-01617023v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:halshs-01617023

DOI: 10.1051/ro/2017069

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().