Coalitional Games via Network Flows

Rahwan, Talal; Nguyen, Tri-Dung; Michalak, Tomasz P.; Polukarov, Maria; Croitoru, Madalina; Jennings, Nicholas R.

Coalitional Games via Network Flows

Talal Rahwan, Tri-Dung Nguyen, Tomasz P. Michalak, Maria Polukarov, Madalina Croitoru, Nicholas R. Jennings

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 324-330.

Abstract

We introduce a new representation scheme for coalitional games, called coalition-flow networks (CF-NETs), where the formation of effective coalitions in a task-based setting is reduced to the problem of directing flow through a network. We show that our representation is intuitive, fully expressive, and captures certain patterns in a significantly more concise manner compared to the conventional approach. Furthermore, our representation has the flexibility to express various classes of games, such as characteristic function games, coalitional games with overlapping coalitions, and coalitional games with agent types. As such, to the best of our knowledge, CF-NETs is the first representation that allows for switching conveniently and efficiently between overlapping/non-overlapping coalitions, with/without agent types. We demonstrate the efficiency of our scheme on the coalition structure generation problem, where near-optimal solutions for large instances can be found in a matter of seconds.

Talal Rahwan, Tri-Dung Nguyen, Tomasz P. Michalak, Maria Polukarov, Madalina Croitoru, and Nicholas R. Jennings. 2013. Coalitional Games via Network Flows. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 324–330. https://ijcai.org/proceedings/2013/56

@inproceedings{ijcai2013p56,
  title     = {Coalitional Games via Network Flows},
  author    = {Rahwan, Talal and Nguyen, Tri-Dung and Michalak, Tomasz P. and Polukarov, Maria and Croitoru, Madalina and Jennings, Nicholas R.},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {324--330},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/56},
}

TY  - CPAPER
TI  - Coalitional Games via Network Flows
AU  - Rahwan, Talal
AU  - Nguyen, Tri-Dung
AU  - Michalak, Tomasz P.
AU  - Polukarov, Maria
AU  - Croitoru, Madalina
AU  - Jennings, Nicholas R.
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 324
EP  - 330
UR  - https://ijcai.org/proceedings/2013/56
ER  -