An Imperfect Algorithm for Coalition Structure Generation
Abstract
Optimal Coalition Structure Generation (CSG) is a significant research problem that remains difficult to solve. Given n agents, the ODP-IP algorithm (Michalak et al. 2016) achieves the current lowest worst-case time complexity of O(3n). We devise an Imperfect Dynamic Programming (ImDP) algorithm for CSG with runtime O(n2n). Imperfect algorithm means that there are some contrived inputs for which the algorithm fails to give the optimal result. Experimental results confirmed that ImDP algorithm performance is better for several data distribution, and for some it improves dramatically ODP-IP. For example, given 27 agents, with ImDP for agentbased uniform distribution time gain is 91% (i.e. 49 minutes).
Cite
Text
Changder et al. "An Imperfect Algorithm for Coalition Structure Generation." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33019923Markdown
[Changder et al. "An Imperfect Algorithm for Coalition Structure Generation." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/changder2019aaai-imperfect/) doi:10.1609/AAAI.V33I01.33019923BibTeX
@inproceedings{changder2019aaai-imperfect,
title = {{An Imperfect Algorithm for Coalition Structure Generation}},
author = {Changder, Narayan and Aknine, Samir and Dutta, Animesh},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2019},
pages = {9923-9924},
doi = {10.1609/AAAI.V33I01.33019923},
url = {https://mlanthology.org/aaai/2019/changder2019aaai-imperfect/}
}