Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/ED975482-3B31-457A-B55B-29636E06AA23 | - |
| Αναγνωριστικό | https://www.sciencedirect.com/science/article/pii/S0004370215001812?via%3Dihub | - |
| Αναγνωριστικό | https://doi.org/10.1016/j.artint.2015.12.005 | - |
| Γλώσσα | en | - |
| Μέγεθος | 38 pages | en |
| Τίτλος | Characteristic function games with restricted agent interactions: core-stability and coalition structures | en |
| Δημιουργός | Chalkiadakis Georgios | en |
| Δημιουργός | Χαλκιαδακης Γεωργιος | el |
| Δημιουργός | Greco Gianluigi | en |
| Δημιουργός | Markakis, Evangelos | en |
| Εκδότης | Elsevier | en |
| Περίληψη | In many real-world settings, the structure of the environment constrains the formation of coalitions among agents. These settings can be represented by characteristic function games, also known as coalitional games, equipped with interaction graphs. An interaction graph determines the set of all feasible coalitions, in that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. Our work analyzes stability issues arising in such environments, by focusing on the core as a solution concept, and by considering the coalition structure viewpoint, that is, without assuming that the grand-coalition necessarily forms. The complexity of the coalition structure core is studied over a variety of interaction graph structures of interest, including complete graphs, lines, cycles, trees, and nearly-acyclic graphs (formally, having bounded treewidth). The related stability concepts of the least core and the cost of stability are also studied. Results are derived for the setting of compact coalitional games, i.e., for games that are implicitly described via a compact encoding, and where simple calculations on this encoding are to be performed in order to compute the payoff associated with any coalition. Moreover, specific results are provided for compact games defined via marginal contribution networks, an expressive encoding mechanism that received considerable attention in the last few years. | en |
| Τύπος | Peer-Reviewed Journal Publication | en |
| Τύπος | Δημοσίευση σε Περιοδικό με Κριτές | el |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2018-10-22 | - |
| Ημερομηνία Δημοσίευσης | 2016 | - |
| Θεματική Κατηγορία | Coalitional games | en |
| Θεματική Κατηγορία | Computational complexity | en |
| Θεματική Κατηγορία | Marginal contribution networks | en |
| Θεματική Κατηγορία | Solution concepts | en |
| Θεματική Κατηγορία | Treewidth | en |
| Βιβλιογραφική Αναφορά | G. Chalkiadakis, G. Greco and E. Markakis, "Characteristic function games with restricted agent interactions: core-stability and coalition structures," Artif. Intell., vol. 232, pp. 76-113, Mar. 2016. doi: 10.1016/j.artint.2015.12.005 | en |
Copyright © DIAS 2013
