Skip to Main content Skip to Navigation
Conference papers

Coalitional Games via Network Flows

Talal Rahwan 1 Tri-Dung Nguyen 1 Tomasz P. Michalak 2, 3 Maria Polukarov 1 Madalina Croitoru 4 Nicholas R. Jennings 1
4 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Document type :
Conference papers
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00936484
Contributor : Madalina Croitoru Connect in order to contact the contributor
Submitted on : Thursday, January 7, 2021 - 11:19:57 AM
Last modification on : Monday, October 11, 2021 - 1:24:06 PM
Long-term archiving on: : Thursday, April 8, 2021 - 6:47:06 PM

File

7007-30591-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00936484, version 1

Collections

Citation

Talal Rahwan, Tri-Dung Nguyen, Tomasz P. Michalak, Maria Polukarov, Madalina Croitoru, et al.. Coalitional Games via Network Flows. IJCAI: International Joint Conference on Artificial Intelligence, Aug 2013, Beijing, China. pp.324-331. ⟨lirmm-00936484⟩

Share

Metrics

Record views

456

Files downloads

27