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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Efficient coalition structure generation via approximately equivalent induced subgraph games

Bistaffa Filippo, Chalkiadakis Georgios, Farinelli Alessandro

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/6C6EE2BE-7034-4579-A4F0-2ED46A32B3F1-
Αναγνωριστικόhttps://doi.org/10.1109/TCYB.2020.3040622-
Αναγνωριστικόhttps://ieeexplore.ieee.org/document/9314263-
Γλώσσαen-
Μέγεθος11 pagesen
ΤίτλοςEfficient coalition structure generation via approximately equivalent induced subgraph gamesen
ΔημιουργόςBistaffa Filippoen
ΔημιουργόςChalkiadakis Georgiosen
ΔημιουργόςΧαλκιαδακης Γεωργιοςel
ΔημιουργόςFarinelli Alessandroen
ΕκδότηςInstitute of Electrical and Electronics Engineersen
Περίληψη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
ΤύποςPeer-Reviewed Journal Publicationen
ΤύποςΔημοσίευση σε Περιοδικό με Κριτέςel
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by-nc-nd/4.0/en
Ημερομηνία2023-02-21-
Ημερομηνία Δημοσίευσης2022-
Θεματική ΚατηγορίαCoalition structure generation (CSG)en
Θεματική ΚατηγορίαGraphsen
Θεματική ΚατηγορίαInduced subgraph games (ISGs)en
Θεματική ΚατηγορίαRidesharingen
Θεματική ΚατηγορίαSocial networksen
Βιβλιογραφική Αναφορά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

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

Υπηρεσίες

Στατιστικά