Bounding the Cost of Stability in Games over Interaction Networks
Abstract
We study the stability of cooperative games played over an interaction network, in a 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 underlying interaction networks. Specifically, we prove that if the treewidth of the interaction network H is k, then the relative cost of stability of any game played over H is at most k + 1, and if the pathwidth of H is k', then the relative cost of stability is at most k'. We show that these bounds are tight for all k≥ 2and all k' ≥ 1, respectively.
Cite
Text
Meir et al. "Bounding the Cost of Stability in Games over Interaction Networks." AAAI Conference on Artificial Intelligence, 2013. doi:10.1609/AAAI.V27I1.8613Markdown
[Meir et al. "Bounding the Cost of Stability in Games over Interaction Networks." AAAI Conference on Artificial Intelligence, 2013.](https://mlanthology.org/aaai/2013/meir2013aaai-bounding/) doi:10.1609/AAAI.V27I1.8613BibTeX
@inproceedings{meir2013aaai-bounding,
title = {{Bounding the Cost of Stability in Games over Interaction Networks}},
author = {Meir, Reshef and Zick, Yair and Elkind, Edith and Rosenschein, Jeffrey S.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2013},
pages = {690-696},
doi = {10.1609/AAAI.V27I1.8613},
url = {https://mlanthology.org/aaai/2013/meir2013aaai-bounding/}
}