Efficient coalition structure generation via approximately equivalent induced subgraph gamesEfficient coalition structure generation via approximately equivalent induced subgraph games Peer-Reviewed Journal Publication Δημοσίευση σε Περιοδικό με Κριτές 2023-02-212022enWe 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.http://creativecommons.org/licenses/by-nc-nd/4.0/IEEE Transactions on Cybernetics5265548–5558Bistaffa_et_al_IEEE Trans. Cybern._52(6)_2022_preprint.pdfChania [Greece]Library of TUC2023-02-21application/pdf3.4 MBfree Bistaffa Filippo Chalkiadakis Georgios Χαλκιαδακης Γεωργιος Farinelli Alessandro Institute of Electrical and Electronics Engineers Coalition structure generation (CSG) Graphs Induced subgraph games (ISGs) Ridesharing Social networks