Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/6C6EE2BE-7034-4579-A4F0-2ED46A32B3F1 | ||
| Έτος | 2022 | ||
| Τύπος | Δημοσίευση σε Περιοδικό με Κριτές | ||
| Άδεια Χρήσης |
|
||
| Βιβλιογραφική Αναφορά | 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.
Copyright © DIAS 2013
