Coalitional Affinity Games and the Stability Gap
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 79-83.
Abstract
We present and analyze coalitional affinity games, a family of hedonic games that explicitly model the value that an agent receives from being associated with other agents. We provide a characterization of the social-welfare maximizing coalition structures, and study the stability properties of affinity games, using the core solution concept. Interestingly, we observe that members of the core do not necessarily maximize social welfare. We introduce a new measure, the stability-gap to capture this difference. Using the stability gap, we show that for an interesting class of coalitional affinity games, the difference between the social welfare of a stable coalition structure and a social welfare maximizing coalition structure is bounded by a factor of two, and that this bound is tight.Simina Branzei, Kate Larson
@inproceedings{ijcai2009p24,
title = {Coalitional Affinity Games and the Stability Gap},
author = {Brânzei, Simina and Larson, Kate},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {79--83},
year = {2009},
url = {https://ijcai.org/proceedings/2009/24},
}
TY - CPAPER TI - Coalitional Affinity Games and the Stability Gap AU - Brânzei, Simina AU - Larson, Kate T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 79 EP - 83 UR - https://ijcai.org/proceedings/2009/24 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
