Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Efficient coalition structure generation via approximately equivalent induced subgraph games

Bistaffa Filippo, Chalkiadakis Georgios, Farinelli Alessandro

Πλήρης Εγγραφή


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.

Διαθέσιμα αρχεία

Υπηρεσίες

Στατιστικά