Bounding the Cost of Stability in Games with Restricted Interaction
Yair Zick ( Nanyang Technological University )
- 16:30 10th July 2012 ( week 11, Trinity Term 2012 )380
We study stability of cooperative games with restricted interaction, in the model that was introduced by Myerson (Myerson, 1977). We show that the cost of stability (the maximal required subsidy) of such games can be bounded in terms of natural parameters of their interaction graphs. Specifically, we prove that if the treewidth of the interaction graph is k, then the relative cost of stability is at most k + 1, and this bound is tight for all k greater than 2. Also, we show that if the pathwidth of the interaction graph is k, then the relative cost of stability is at most k, and that this bound is tight for all k greater than 2.