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

Alexandre Skoda
Additional contact information
Alexandre Skoda: Centre d'Economie de la Sorbonne

Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne

Abstract: Let G = (N,E,w) be a weighted communication graph (with weight function w on E). For every subset A inclut 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 = sigmaF appartient à Pmin(A)v(F) for all A inclut 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: communication networks; cooperative game; convex game; restricted game; partitions; supermodularity; graph; complexity (search for similar items in EconPapers)
Pages: 28 pages
Date: 2016-07
New Economics Papers: this item is included in nep-gth and nep-hpe
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Published in RAIRO - Operations Research, 2020, 54 (1), pp.143-161

Downloads: (external link)
https://shs.hal.science/halshs-01382502 (application/pdf)
https://doi.org/10.1051/ro/2019003

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:mse:cesdoc:16055

Access Statistics for this paper

More papers in Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().