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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Cooperative games with overlapping coalitions: charting the tractability frontier

Zick Yair, Chalkiadakis Georgios, Elkind, Edith, 1976-, Markakis, Evangelos

Απλή Εγγραφή


URIhttp://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 pagesen
ΤίτλοςCooperative games with overlapping coalitions: charting the tractability frontieren
ΔημιουργόςZick Yairen
ΔημιουργόςChalkiadakis Georgiosen
ΔημιουργόςΧαλκιαδακης Γεωργιοςel
ΔημιουργόςElkind, Edith, 1976-en
ΔημιουργόςMarkakis, Evangelosen
ΕκδότηςElsevieren
Περίληψη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 Publicationen
ΤύποςΔημοσίευση σε Περιοδικό με Κριτέςel
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2020-06-05-
Ημερομηνία Δημοσίευσης2019-
Θεματική ΚατηγορίαArbitration functionsen
Θεματική ΚατηγορίαCooperative gamesen
Θεματική ΚατηγορίαCoreen
Θεματική ΚατηγορίαOverlapping coalition formationen
Θεματική ΚατηγορίαTreewidthen
Βιβλιογραφική Αναφορά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.006en

Υπηρεσίες

Στατιστικά