Por favor, use este identificador para citar o enlazar a este item:
http://hdl.handle.net/10261/223529
COMPARTIR / EXPORTAR:
SHARE BASE | |
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE | |
Título: | Efficient Coalition Structure Generation via Approximately Equivalent Induced Subgraph Games |
Autor: | Bistaffa, Filippo CSIC ORCID ; Chalkiadakis, Georgios; Farinelli, Alessandro | Palabras clave: | Induced subgraph games Coalition structure generation Ridesharing Social networks Graphs |
Fecha de publicación: | nov-2020 | Citación: | IEEE Transactions on Cybernetics, in press | Resumen: | We show that any characteristic function game (CFG) G can be always turned into an approximately equivalent game represented using the induced subgraph game (ISG) representation. Such a transformation incurs obvious benefits in terms of tractability of computing solution concepts for G. Our transformation approach, namely AE-ISG, is based on the solution of a norm approximation problem. We then propose a novel coalition structure generation (CSG) approach for ISGs that is based on graph clustering, which outperforms existing CSG approaches for ISGs by using off-the-shelf optimisation solvers. Finally, we provide theoretical guarantees on the value of the optimal CSG solution of G wrt the optimal CSG solution of the approximately equivalent ISG. As a consequence, our approach allows one to compute approximate CSG solutions with quality guarantees for any CFG. Results on a real-world application domain show that our approach outperforms a domain-specific CSG algorithm, both in terms of quality of the solutions and theoretical quality guarantees. | Versión del editor: | https://doi.org/10.1109/TCYB.2020.3040622 | URI: | http://hdl.handle.net/10261/223529 |
Aparece en las colecciones: | (IIIA) Artículos |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
BistaffaEtAl2020TCYB.pdf | Accepted version | 3,3 MB | Adobe PDF | Visualizar/Abrir |
CORE Recommender
Page view(s)
160
checked on 28-mar-2024
Download(s)
410
checked on 28-mar-2024
Google ScholarTM
Check
NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.