Speaker: Reshef Meir
Hebrew University http://www.cs.huji.ac.il/~reshef24/
Title: Bounding the Cost of Stability in Games with Restricted Interaction
We study stability of cooperative games with restricted interaction, in the model that was introduced by Myerson ['77]. We show that the Cost of Stability of such games (i.e., the subsidy required to stabilize the game) 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>= 2. Also, we show that if the pathwidth of the interaction graph is k, then the relative cost of stability is at most k.
Joint work with Yair Zick, Edith Elkind, and Jeffrey S. Rosenschein.