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

Université de Paris I, Centre d’Economie de la Sorbonne, 106-112 Bd de l’Hôpital, 75013 Paris, France

^* Corresponding author: alexandre.skoda@univ-paris1.fr

Received: 22 February 2018
Accepted: 31 December 2018

Abstract

Let G = (N, E, w) be a weighted communication graph. For any subset A ⊆ N, we delete all minimum-weight edges in the subgraph induced by A. The connected components of the resultant subgraph constitute the partition 𝒫_min(A) of A. Then, for every cooperative game (N, v), the 𝒫min-restricted game (N, v̅) is defined by v̅(A)=∑_{F∈𝒫min(A)}v(F) for all A ⊆ N. We prove that we can decide in polynomial time if there is inheritance of ℱ-convexity, i.e., if for every ℱ-convex game the 𝒫_min-restricted game is ℱ-convex, where ℱ-convexity is obtained by restricting convexity to connected subsets. This implies that we can also decide in polynomial time for any unweighted graph if there is inheritance of convexity for Myerson’s graph-restricted game.