Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://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 pages | en |
| Τίτλος | Efficient coalition structure generation via approximately equivalent induced subgraph games | en |
| Δημιουργός | Bistaffa Filippo | en |
| Δημιουργός | Chalkiadakis Georgios | en |
| Δημιουργός | Χαλκιαδακης Γεωργιος | el |
| Δημιουργός | Farinelli Alessandro | en |
| Εκδότης | Institute of Electrical and Electronics Engineers | en |
| Περίληψη | 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 Publication | en |
| Τύπος | Δημοσίευση σε Περιοδικό με Κριτές | el |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by-nc-nd/4.0/ | en |
| Ημερομηνία | 2023-02-21 | - |
| Ημερομηνία Δημοσίευσης | 2022 | - |
| Θεματική Κατηγορία | Coalition structure generation (CSG) | en |
| Θεματική Κατηγορία | Graphs | en |
| Θεματική Κατηγορία | Induced subgraph games (ISGs) | en |
| Θεματική Κατηγορία | Ridesharing | en |
| Θεματική Κατηγορία | Social networks | en |
| Βιβλιογραφική Αναφορά | 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 |
Copyright © DIAS 2013
