nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Coalition Structure Formation Using Anytime Dynamic Programming

verfasst von : Narayan Changder, Animesh Dutta, Aditya K. Ghose

Erschienen in: PRIMA 2016: Principles and Practice of Multi-Agent Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The optimal coalition structure generation is an important problem in multi-agent systems that remains difficult to solve. This paper presents a novel anytime dynamic programming algorithm to compute the optimal coalition structure. The proposed algorithm can be interrupted, and upon interruption, uses heuristic to select the largest valued coalition from each subproblem of size x and picks the rest of the unassigned agent from other subproblem of size \(n- x\), where n is the total number of agents. We compared the performance of our algorithm against the only existing proposal in the literature for the optimal coalition structure problem that uses anytime dynamic programming using 9 distinct datasets (each corresponding to a different distribution). The empirical evaluation shows that our algorithm always generates better or, at least, as good a solution as the previous anytime dynamic programming algorithm.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Competitive VCG Redistribution Mechanism for Public Project Problem

Nächstes Kapitel Demand Response Integration Through Agent-Based Coordination of Consumers in Virtual Power Plants

If the coalition contains single agent, we do not need to split it anymore.

After \(k^{th}\) iteration algorithm solves all the subproblem of size \(1,2,\ldots ,k\).

We pick the largest valued coalition of size n, because if \(C_{max}=n\), then it contains optimal solution.

If size of coalition X is 0 then the value of the coalition \(X=0\).

Boddy, M.S.: Anytime problem solving using dynamic programming. In: AAAI, pp. 738–743 (1991)

Dang, V.D., Dash, R.K., Rogers, A., Jennings, N.R.: Overlapping coalition formation for efficient data fusion inmulti-sensor networks. In: AAAI, vol. 6, pp. 635–640 (2006)

Dang, V.D., Jennings, N.R.: Generating coalition structures with finite bound from the optimal guarantees. In: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, vol. 2, pp. 564–571. IEEE Computer Society (2004)

Kahan, J.P., Rapoport, A.: Theories of Coalition Formation. Psychology Press, Palo Altom (2014)

Kreher, D.L., Stinson, D.R.: Combinatorial Algorithms: Generation, Enumeration, and Search, vol. 7. CRC Press, Boca Raton (1998)MATH

Larson, K.S., Sandholm, T.W.: Anytime coalition structure generation: an average case study. J. Exp. Theoret. Artif. Intell. 12(1), 23–42 (2000)CrossRefMATH

Michalak, T., Rahwan, T., Elkind, E., Wooldridge, M., Jennings, N.R.: A hybrid exact algorithm for complete set partitioning. Artif. Intell. 230, 14–50 (2015)MathSciNetCrossRefMATH

Rahwan, T., Jennings, N.R.: Coalition structure generation: dynamic programming meets anytime optimization. In: AAAI, vol. 8, pp. 156–161 (2008)

Rahwan, T., Jennings, N.R.: An improved dynamic programming algorithm for coalition structure generation. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, vol. 3, pp. 1417–1420. International Foundation for Autonomous Agents and Multiagent Systems (2008)

10.

Rahwan, T., Michalak, T., Jennings, N.R.: A hybrid algorithm for coalition structure generation (2012)

11.

Rahwan, T., Michalak, T.P., Wooldridge, M., Jennings, N.R.: Coalition structure generation: a survey. Artif. Intell. 229, 139–174 (2015)MathSciNetCrossRefMATH

12.

Rahwan, T., Ramchurn, S.D., Dang, V.D., Giovannucci, A., Jennings, N.R.: Anytime optimal coalition structure generation. In: AAAI, vol. 7, pp. 1184–1190 (2007)

13.

Rahwan, T., Ramchurn, S.D., Jennings, N.R., Giovannucci, A.: An anytime algorithm for optimal coalition structure generation. J. Artif. Intell. Res. 34, 521–567 (2009)MathSciNetMATH

14.

Sandhlom, T.W., Lesser, V.R.: Coalitions among computationally bounded agents. Artif. Intell. 94(1), 99–137 (1997)MathSciNetCrossRefMATH

15.

Sandholm, T., Larson, K., Andersson, M., Shehory, O., Tohmé, F.: Coalition structure generation with worst case guarantees. Artif. Intell. 111(1), 209–238 (1999)MathSciNetCrossRefMATH

16.

Service, T.C., Adams, J.A.:Anytime dynamic programming for coalition structure generation. In: Proceedings of the 9th International Conference on AutonomousAgents and Multiagent Systems, vol. 1, pp. 1411–1412. International Foundation for Autonomous Agents and Multiagent Systems (2010)

17.

Service, T.C., Adams, J.A.: Approximate coalition structure generation. In: Twenty-Fourth AAAI Conference on Artificial Intelligence (2010)

18.

Tsvetovat, M., Sycara, K.: Customer coalitions in the electronic marketplace. In: Proceedings of the Fourth International Conference on Autonomous Agents, pp. 263–264. ACM (2000)

19.

Yun Yeh, D.: A dynamic programming approach to the complete set partitioning problem. BIT Numer. Math. 26(4), 467–474 (1986)MathSciNetCrossRefMATH

Titel: Coalition Structure Formation Using Anytime Dynamic Programming
verfasst von: Narayan Changder
Animesh Dutta
Aditya K. Ghose
Verlag: Springer International Publishing
Buch: PRIMA 2016: Principles and Practice of Multi-Agent Systems
Print ISBN: 978-3-319-44831-2

Electronic ISBN: 978-3-319-44832-9

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-44832-9_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"