Skip to main content

Bounding the Cost of Stability in Games with Restricted Interaction

Yair Zick ( Nanyang Technological University )

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.

Share this: