Complexity of inheritance of F-convexity for restricted games induced by minimum partitions

Alexandre Skoda ()
Additional contact information
Alexandre Skoda: 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: Let G = (N,E,w ) be a weighted communication graph (with weight function w on E ). For every subset A ⊆ N, we delete in the subset E (A ) of edges with ends in A, all edges of minimum weight in E (A ). Then the connected components of the corresponding induced subgraph constitue a partition of A that we Pmin(A ). For every game (N , v ), we define the Pmin-restricted game (N , v ) by v (A = ∑F∈ Pmin (A) v(F ) for all A ⊆ N. We prove that we can decide in polynomial time if there is inheritance of F-convexity from N , v ) to the Pmin-restricted game (N , v ) where F-convexity is obtained by restricting convexity to connected subsets

Keywords: graph; complexity; supermodularity; partitions; communication networks; cooperative game; convex game; restricted game (search for similar items in EconPapers)
Date: 2016-07
New Economics Papers: this item is included in nep-gth
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-01382502v1
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Published in 2016

Downloads: (external link)
https://shs.hal.science/halshs-01382502v1/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-01382502

Access Statistics for this paper

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