Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/3BAB89F1-ED11-4489-A5EE-77A85A269438 | - |
| Αναγνωριστικό | https://doi.org/10.1016/j.artint.2018.11.006 | - |
| Αναγνωριστικό | https://www.sciencedirect.com/science/article/pii/S0004370219300219 | - |
| Γλώσσα | en | - |
| Μέγεθος | 24 pages | en |
| Τίτλος | Cooperative games with overlapping coalitions: charting the tractability frontier | en |
| Δημιουργός | Zick Yair | en |
| Δημιουργός | Chalkiadakis Georgios | en |
| Δημιουργός | Χαλκιαδακης Γεωργιος | el |
| Δημιουργός | Elkind, Edith, 1976- | en |
| Δημιουργός | Markakis, Evangelos | en |
| Εκδότης | Elsevier | en |
| Περίληψη | The framework of cooperative games with overlapping coalitions (OCF games), which was proposed by Chalkiadakis et al. [1], generalizes classic cooperative games to settings where agents may belong to more than one coalition. OCF games can be used to model scenarios where agents distribute resources, such as time or energy, among several tasks, and then divide the payoffs generated by these tasks in a fair and/or stable manner. As the framework of OCF games is very expressive, identifying settings that admit efficient algorithms for computing ‘good’ outcomes of OCF games is a challenging task. In this work, we put forward two approaches that lead to tractability results for OCF games. First, we propose a discretized model of overlapping coalition formation, where each agent i has a weight W i ∈ℕ and may allocate an integer amount of weight to any task. Within this framework, we focus on the computation of outcomes that are socially optimal and/or stable. We discover that the algorithmic complexity of this task crucially depends on the amount of resources that each agent possesses, the maximum coalition size, and the pattern of communication among the agents. We identify several constraints that lead to tractable subclasses of discrete OCF games, and supplement our tractability results by hardness proofs, which clarify the role of our constraints. Second, we introduce and analyze a natural class of (continuous) OCF games—the Linear Bottleneck Games. We show that such games always admit a stable outcome, even assuming a large space of feasible deviations, and provide an efficient algorithm for computing such outcomes. | en |
| Τύπος | Peer-Reviewed Journal Publication | en |
| Τύπος | Δημοσίευση σε Περιοδικό με Κριτές | el |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2020-06-05 | - |
| Ημερομηνία Δημοσίευσης | 2019 | - |
| Θεματική Κατηγορία | Arbitration functions | en |
| Θεματική Κατηγορία | Cooperative games | en |
| Θεματική Κατηγορία | Core | en |
| Θεματική Κατηγορία | Overlapping coalition formation | en |
| Θεματική Κατηγορία | Treewidth | en |
| Βιβλιογραφική Αναφορά | Y. Zick, G. Chalkiadakis, E. Elkind and E. Markakis, "Cooperative games with overlapping coalitions: charting the tractability frontier," Artif. Intell., vol. 271, pp. 74-97, Jun. 2019. doi: 10.1016/j.artint.2018.11.006 | en |
Copyright © DIAS 2013
