Dynamics of Profit-Sharing Games

Augustine, John; Chen, Ning; Elkind, Edith; Fanelli, Angelo; Gravin, Nick; Shiryaev, Dmitry

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

Dynamics of Profit-Sharing Games

John Augustine, Ning Chen, Edith Elkind, Angelo Fanelli, Nick Gravin, Dmitry Shiryaev

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 37-41.

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

Abstract

An important task in the analysis of multiagent systems is to understand how groups of selfish players can form coalitions, i.e., work together in teams. In this paper, we study the dynamics of coalition formation under bounded rationality. We consider settings where each team's profit is given by a concave function, and propose three profit-sharing schemes, each of which is based on the concept of marginal utility. The agents are assumed to be myopic, i.e., they keep changing teams as long as they can increase their payoff by doing so. We study the properties (such as closeness to Nash equilibrium or total profit) of the states that result after a polynomial number of such moves, and prove bounds on the price of anarchy and the price of stability of the corresponding games.

John Augustine, Ning Chen, Edith Elkind, Angelo Fanelli, Nick Gravin, and Dmitry Shiryaev. 2011. Dynamics of Profit-Sharing Games. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 37–41. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-018

@inproceedings{ijcai2011p18,
  title     = {Dynamics of Profit-Sharing Games},
  author    = {Augustine, John and Chen, Ning and Elkind, Edith and Fanelli, Angelo and Gravin, Nick and Shiryaev, Dmitry},
  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     = {37--41},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-018},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-018},
}

TY  - CPAPER
TI  - Dynamics of Profit-Sharing Games
AU  - Augustine, John
AU  - Chen, Ning
AU  - Elkind, Edith
AU  - Fanelli, Angelo
AU  - Gravin, Nick
AU  - Shiryaev, Dmitry
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  - 37
EP  - 41
DO  - 10.5591/978-1-57735-516-8/IJCAI11-018
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-018
ER  -