Subsidies, Stability, and Restricted Cooperation in Coalitional Games

Meir, Reshef; Rosenschein, Jeffrey S.; Malizia, Enrico

doi:10.5591/978-1-57735-516-8/IJCAI11-060

Subsidies, Stability, and Restricted Cooperation in Coalitional Games

Reshef Meir, Jeffrey S. Rosenschein, Enrico Malizia

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 301-305.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-060

Abstract

Cooperation among automated agents is becoming increasingly important in various artificial intelligence applications. Coalitional (i.e., cooperative) game theory supplies conceptual and mathematical tools useful in the analysis of such interactions, and in particular in the achievement of stable outcomes among self-interested agents. Here, we study the minimal external subsidy required to stabilize the core of a coalitional game. Following the Cost of Stability (CoS) model introduced by Bachrach et al. [2009a], we give tight bounds on the required subsidy under various restrictions on the social structure of the game. We then compare the extended core induced by subsidies with the least core of the game, proving tight bounds on the ratio between the minimal subsidy and the minimal demand relaxation that each lead to stability.

Reshef Meir, Jeffrey S. Rosenschein, and Enrico Malizia. 2011. Subsidies, Stability, and Restricted Cooperation in Coalitional Games. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 301–305. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-060

@inproceedings{ijcai2011p60,
  title     = {Subsidies, Stability, and Restricted Cooperation in Coalitional Games},
  author    = {Meir, Reshef and Rosenschein, Jeffrey S. and Malizia, Enrico},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {301--305},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-060},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-060},
}

TY  - CPAPER
TI  - Subsidies, Stability, and Restricted Cooperation in Coalitional Games
AU  - Meir, Reshef
AU  - Rosenschein, Jeffrey S.
AU  - Malizia, Enrico
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 301
EP  - 305
DO  - 10.5591/978-1-57735-516-8/IJCAI11-060
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-060
ER  -