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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Overlapping coalition formation games: Charting the tractability frontier

Chalkiadakis Georgios, Yair Zick, Edith Elkind

Απλή Εγγραφή

URIhttp://purl.tuc.gr/dl/dias/E555E189-E0A3-43FE-8668-BE65CBE04495-
Αναγνωριστικόhttp://www3.ntu.edu.sg/home2009/yair0001/ocfcomp.pdf-
Γλώσσαen-
Μέγεθος13 pagesen
ΤίτλοςOverlapping coalition formation games: Charting the tractability frontieren
ΔημιουργόςChalkiadakis Georgiosen
ΔημιουργόςΧαλκιαδακης Γεωργιοςel
ΔημιουργόςYair Zicken
ΔημιουργόςEdith Elkinden
ΠερίληψηCooperative games with overlapping coalitions (OCF games) [3, 23] model scenarios where agents can distribute their resources among several tasks; each task generates a profit which may be freely divided among the agents participating in the task. The goal of this work is to initiate a systematic investigation of algorithmic aspects of OCF games. We propose a discretized model of over- lapping coalition formation, where each agent i ∈ N has a weight wi ∈ N 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 al- gorithmic complexity of the associated problems crucially depends on the amount of resources that each agent possesses, the maximum coalition size, and the pattern of interaction among the agents. We identify several constraints that lead to tractable subclasses of OCF games, and provide efficient algorithms for games that belong to these subclasses. We supplement our tractability results by hard- ness proofs, which clarify the role of our constraints.en
ΤύποςΠλήρης Δημοσίευση σε Συνέδριοel
ΤύποςConference Full Paperen
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-09-30-
Ημερομηνία Δημοσίευσης2012-
Βιβλιογραφική ΑναφοράY. Zick ,G. Chalkiadakis ,E. Elkind .(2012).Overlapping Coalition Formation Games: Charting the Tractability Frontier .Presented at the 11th International Conference on Autonomous Agents and Multiagent Systems.[online].Available :http://www3.ntu.edu.sg/home2009/yair0001/ocfcomp.pdfen

Υπηρεσίες

Στατιστικά

 

Copyright © DIAS 2013