mirage

The cost of stability in coalitional games.

DSpace/Manakin Repository

 

Search DR-NTU


Advanced Search Subject Search

Browse

My Account

The cost of stability in coalitional games.

Show simple item record

dc.contributor.author Bachrach, Yoram.
dc.contributor.author Elkind, Edith.
dc.contributor.author Meir, Reshef.
dc.contributor.author Pasechnik, Dmitrii V.
dc.contributor.author Zuckerman, Michael.
dc.contributor.author Rothe, Jӧrg.
dc.contributor.author Rosenschein, Jeffrey S.
dc.date.accessioned 2012-03-09T03:20:49Z
dc.date.available 2012-03-09T03:20:49Z
dc.date.copyright 2009
dc.date.issued 2012-03-09
dc.identifier.citation Bachrach, Y., Elkind, E., Meir, R., Pasechnik, D., Zurkerman, M., Rothe, J. & Rosenschein, J. S. (2009). The Cost of Stability in Coalitional Games. Proceedings of the 2nd International symposium, SAGT 2009, Paphos, Cyprus, pp.122-134.
dc.identifier.uri http://hdl.handle.net/10220/7628
dc.description.abstract A key question in cooperative game theory is that of coalitional stability, usually captured by the notion of the core--the set of outcomes such that no subgroup of players has an incentive to deviate. However, some coalitional games have empty cores, and any outcome in such a game is unstable. In this paper, we investigate the possibility of stabilizing a coalitional game by using external payments. We consider a scenario where an external party, which is interested in having the players work together, offers a supplemental payment to the grand coalition (or, more generally, a particular coalition structure). This payment is conditional on players not deviating from their coalition(s). The sum of this payment plus the actual gains of the coalition(s) may then be divided among the agents so as to promote stability. We define the cost of stability (CoS) as the minimal external payment that stabilizes the game. We provide general bounds on the cost of stability in several classes of games, and explore its algorithmic properties. To develop a better intuition for the concepts we introduce, we provide a detailed algorithmic study of the cost of stability in weighted voting games, a simple but expressive class of games which can model decision-making in political bodies, and cooperation in multiagent settings. Finally, we extend our model and results to games with coalition structures.
dc.format.extent 13 p.
dc.language.iso en
dc.rights © 2009 Springer-Verlag Berlin Heidelberg. This is the author created version of a work that has been peer reviewed and accepted for publication by Proceedings of SAGT 2009, LNCS 5814, Springer-Verlag Berlin Heidelberg. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [DOI: http://dx.doi.org/10.1007/978-3-642-04645-2 ].
dc.subject DRNTU::Science::Mathematics.
dc.title The cost of stability in coalitional games.
dc.type Conference Paper
dc.contributor.conference Symposium on Algorithmic Game Theory (2nd : 2009 : Paphos, Cyprus)
dc.contributor.school School of Physical and Mathematical Sciences
dc.identifier.doi http://dx.doi.org/10.1007/978-3-642-04645-2
dc.description.version Accepted version

Files in this item

Files Size Format View
52. The Cost of Stability in Coalitional Games.pdf 175.5Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Statistics

Total views

All Items Views
The cost of stability in coalitional games. 357

Total downloads

All Bitstreams Views
52. The Cost of Stability in Coalitional Games.pdf 213

Top country downloads

Country Code Views
China 70
Singapore 64
United States of America 53
Russian Federation 5
Unknown Country 4

Top city downloads

city Views
Singapore 64
Beijing 56
Mountain View 41
Redwood City 3
Shenzhen 3

Downloads / month

  2014-07 2014-08 2014-09 total
52. The Cost of Stability in Coalitional Games.pdf 0 0 5 5