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

Alexandre Skoda (1)

1 CES - Centre d'économie de la Sorbonne

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

Mots clés: graph; complexity; supermodularity; partitions; communication networks; cooperative game; convex game; restricted game

Domaines: Economies et finances; Combinatoire [math.CO]; Mathématique discrète [cs.DM]; Informatique et théorie des jeux [cs.GT]

Alexandre Skoda. Complexity of inheritance of F-convexity for restricted games induced by minimum partitions. 2016. ⟨halshs-01382502⟩