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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

The price of democracy in coalition formation

Nicholas R Jennings

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/DD3A51F6-6D73-4884-8326-0C1D15C3803F-
Αναγνωριστικόhttp://eprints.soton.ac.uk/267067/1/cepjPoDaamas2009final.pdf-
Γλώσσαen-
Μέγεθος7 pagesen
ΤίτλοςThe price of democracy in coalition formationen
ΔημιουργόςNicholas R Jenningsen
ΔημιουργόςMaria Polukaroven
Δημιουργός Edith Elkinden
ΔημιουργόςGeorgios Chalkiadakisen
ΕκδότηςInternational Foundation for Autonomous Agents and Multiagent Systemsen
ΠερίληψηWhenever rational agents form coalitions to execute tasks, doing so via a de- centralized negotiation process—while more robust and democratic—may lead to a loss of efficiency compared to a centralized solution. To quantify this loss, we introduce the notion of the Price of Democracy (PoD), which measures the amount of resources needlessly committed to the task(s) at hand. After defining this concept for general coalitional games, we instan- tiate it in the setting of weighted voting games, a simple but expressive class of coalitional games that can be used to model resource allocation in multiagent scenarios. We approach the problem of forming winning coali- tions in this setting from a non-cooperative perspective, and put forward an intuitive deterministic bargaining process, which exhibits no delay of agree- ment (i.e., the agents are guaranteed to form a winning coalition in round one) and allows for efficient computation of bargaining strategies. We show a tight bound of 3/2 on the PoD of our process if two rounds of bargain- ing are allowed, and demonstrate that this bound cannot improve with more rounds. We then generalize our bargaining process to settings where mul- tiple coalitions are allowed to be formed, show that this generalization also exhibits no delay of agreement, and discuss the PoD in such settings.en
ΤύποςΠλήρης Δημοσίευση σε Συνέδριοel
ΤύποςConference Full Paperen
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-09-26-
Ημερομηνία Δημοσίευσης2009-
Βιβλιογραφική ΑναφοράG. Chalkiadakis, E. Elkind, M. Polukarov, N. R Jennings .(2009) .The Price of Democracy in Coalition Formation. Presented at the 8th International conference on autonomous agents and multiagent systems-volume 1.[online].Available :http://eprints.soton.ac.uk/267067/1/cepjPoDaamas2009final.pdfen

Υπηρεσίες

Στατιστικά