Anytime Dynamic Programming for Coalition Structure Generation

Determining the optimal coalition structure is a central problem in multi-agent systems. Two popular techniques includedynamic programming and anytime search algorithms. Dynamic programming algorithms guarantee an optimal solution and have the best worst case running time. Anytime algorithms are flexible as they can terminate before the searchhas completed, but have a significantly poorer worst caseruntime. This paper provides an anytime dynamic programming algorithm with the worst case runtime of dynamic programming and the flexibility of anytime search.

Authors

• Travis Service Vanderbilt University
• Julie Adams Vanderbilt University

Keywords

• coalition formation
• coalition structure generation