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.
https://doi.org/10.1109/TCYB.2020.3040622
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.