Error message

Deprecated function: Array and string offset access syntax with curly braces is deprecated in include_once() (line 20 of /mnt/web104/a0/07/510451407/htdocs/includes/file.phar.inc).

Convexity of Network Restricted Games Induced by Minimum Partitions

Printer-friendly version
Working paper
Author/s: 
Alexandre Skoda
Issue number: 
2016.19
Series: 
CES Working Papers
Publisher: 
Centre d’Economie de la Sorbonne
Year: 
2016
We consider restricted games on weighted communication graphs associated with minimum partitions. We replace in the classical definition of Myerson’s graph-restricted game the connected components of any subgraph by the sub-components corresponding to a minimum partition. This minimum partition Pmin is induced by the deletion of the minimum weight edges. We provide necessary conditions on the graph edge-weights to have inheritance of convexity from the underlying game to the restricted game associated with Pmin. Then we establish that these conditions are also sufficient for a weaker condition, called Fconvexity, obtained by restriction of convexity to connected subsets. Moreover we show that Myerson’s game associated to a given graph G can be obtained as a particular case of the Pmin-restricted game for a specific weighted graph G′. Then we prove that G is cycle-complete if and only if a specific condition on adjacent cycles is satisfied on G′.
Developed by Paolo Gittoi