Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Efficient coalition structure generation via approximately equivalent induced subgraph games

Bistaffa Filippo, Chalkiadakis Georgios, Farinelli Alessandro

Simple record


URIhttp://purl.tuc.gr/dl/dias/6C6EE2BE-7034-4579-A4F0-2ED46A32B3F1-
Identifierhttps://doi.org/10.1109/TCYB.2020.3040622-
Identifierhttps://ieeexplore.ieee.org/document/9314263-
Languageen-
Extent11 pagesen
TitleEfficient coalition structure generation via approximately equivalent induced subgraph gamesen
CreatorBistaffa Filippoen
CreatorChalkiadakis Georgiosen
CreatorΧαλκιαδακης Γεωργιοςel
CreatorFarinelli Alessandroen
PublisherInstitute of Electrical and Electronics Engineersen
Content SummaryWe 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 optimization solvers. Finally, we provide theoretical guarantees on the value of the optimal CSG solution of G with respect to 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.en
Type of ItemPeer-Reviewed Journal Publicationen
Type of ItemΔημοσίευση σε Περιοδικό με Κριτέςel
Licensehttp://creativecommons.org/licenses/by-nc-nd/4.0/en
Date of Item2023-02-21-
Date of Publication2022-
SubjectCoalition structure generation (CSG)en
SubjectGraphsen
SubjectInduced subgraph games (ISGs)en
SubjectRidesharingen
SubjectSocial networksen
Bibliographic CitationF. Bistaffa, G. Chalkiadakis, and A. Farinelli, “Efficient coalition structure generation via approximately equivalent induced subgraph games,” IEEE Trans. Cybern., vol. 52, no. 6, pp. 5548–5558, June 2022, doi: 10.1109/TCYB.2020.3040622.en

Available Files

Services

Statistics