Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/6C6EE2BE-7034-4579-A4F0-2ED46A32B3F1 | - |
| Identifier | https://doi.org/10.1109/TCYB.2020.3040622 | - |
| Identifier | https://ieeexplore.ieee.org/document/9314263 | - |
| Language | en | - |
| Extent | 11 pages | en |
| Title | Efficient coalition structure generation via approximately equivalent induced subgraph games | en |
| Creator | Bistaffa Filippo | en |
| Creator | Chalkiadakis Georgios | en |
| Creator | Χαλκιαδακης Γεωργιος | el |
| Creator | Farinelli Alessandro | en |
| Publisher | Institute of Electrical and Electronics Engineers | en |
| Content Summary | 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 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 Item | Peer-Reviewed Journal Publication | en |
| Type of Item | Δημοσίευση σε Περιοδικό με Κριτές | el |
| License | http://creativecommons.org/licenses/by-nc-nd/4.0/ | en |
| Date of Item | 2023-02-21 | - |
| Date of Publication | 2022 | - |
| Subject | Coalition structure generation (CSG) | en |
| Subject | Graphs | en |
| Subject | Induced subgraph games (ISGs) | en |
| Subject | Ridesharing | en |
| Subject | Social networks | en |
| Bibliographic Citation | F. 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 |
Copyright © DIAS 2013
