Complexity of inheritance of ℱ-convexity for restricted games induced by minimum partitions
RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 1, pp. 143-161.

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(𝒜)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.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2019003
Classification : 91A12, 91A43, 90C27, 05C75, 68Q25
Mots-clés : Cooperative game, restricted game, graph partitions, convexity, complexity 
@article{RO_2020__54_1_143_0,
     author = {Skoda, A.},
     title = {Complexity of inheritance of {\ensuremath{\mathscr{F}}-convexity} for restricted games induced by minimum partitions},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {143--161},
     publisher = {EDP-Sciences},
     volume = {54},
     number = {1},
     year = {2020},
     doi = {10.1051/ro/2019003},
     mrnumber = {4052234},
     zbl = {1437.91038},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2019003/}
}
TY  - JOUR
AU  - Skoda, A.
TI  - Complexity of inheritance of ℱ-convexity for restricted games induced by minimum partitions
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2020
SP  - 143
EP  - 161
VL  - 54
IS  - 1
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2019003/
DO  - 10.1051/ro/2019003
LA  - en
ID  - RO_2020__54_1_143_0
ER  - 
%0 Journal Article
%A Skoda, A.
%T Complexity of inheritance of ℱ-convexity for restricted games induced by minimum partitions
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2020
%P 143-161
%V 54
%N 1
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2019003/
%R 10.1051/ro/2019003
%G en
%F RO_2020__54_1_143_0
Skoda, A. Complexity of inheritance of ℱ-convexity for restricted games induced by minimum partitions. RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 1, pp. 143-161. doi : 10.1051/ro/2019003. https://www.numdam.org/articles/10.1051/ro/2019003/

E. Algaba, Extensión de juegos definidos en sistemas de conjuntos. Ph.D. thesis, Univ. of Seville (1998).

E. Algaba, J. Bilbao, P. Borm and J. Lopez, The position value for union stable systems. Math. Methods Oper. Res. 52 (2000) 221–236. | DOI | MR | Zbl

E. Algaba, J. Bilbao, P. Borm and J. Lopez, A unified approach to restricted games. Theor. Decis. 50 (2001) 333–345. | DOI | MR | Zbl

J.M. Bilbao, Cooperative Games on Combinatorial Structures. Kluwer Academic Publishers, Boston (2000). | DOI | MR | Zbl

J.M. Bilbao, Cooperative games under augmenting systems. SIAM J. Discrete Math. 17 (2003) 122–133. | DOI | MR | Zbl

J. Edmonds and R. Giles, A min-max relation for submodular functions on graphs. Ann. Discrete Math. 1 (1977) 185–204. | DOI | MR | Zbl

U. Faigle, Cores of games with restricted cooperation. ZOR – Methods Models. Oper. Res. 33 (1989) 405–422. | MR | Zbl

U. Faigle, M. Grabisch and M. Heyne, Monge extensions of cooperation and communication structures. Eur. J. Oper. Res. 206 (2010) 104–110. | DOI | MR | Zbl

S. Fujishige, Submodular functions and optimization, 2nd edition. In Vol. 58 of Annals of Discrete Mathematics. Elsevier, (2005). | MR | Zbl

M. Grabisch, The core of games on ordered structures and graphs. Ann. Oper. Res. 204 (2013) 33–64. | DOI | MR | Zbl

M. Grabisch, A. Skoda, Games induced by the partitioning of a graph. Ann. Oper. Res. 201 (2012) 229–249. | DOI | MR | Zbl

R. Myerson, Graphs and cooperation in games. Math. Oper. Res. 2 (1977) 225–229. | DOI | MR | Zbl

A. Skoda, Convexity of graph-restricted games induced by minimum partitions. RAIRO: OR 53 (2019) 841–866. | DOI | Numdam | MR | Zbl

A. Skoda, Inheritance of Convexity for the 𝒫min- Restricted Game. Documents de travail du Centre d’Economie de la Sorbonne. ISSN : 1955-611X (2017).

A. Skoda, Inheritance of Convexity for the 𝒫min- Restricted Game (2018).

A. Van Den Nouweland and P. Borm, On the convexity of communication games. Int. J. Game Theor. 19 (1991) 421–30. | DOI | MR | Zbl

Cité par Sources :