anytime dynamic programming for coalition structure generation
Determining the optimal coalition structure is a central problem in multi-agent systems. Two popular techniques include dynamic 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 search has completed, but have a significantly poorer worst case runtime. This paper provides an anytime dynamic programming algorithm with the worst case runtime of dynamic programming and the flexibility of anytime search.
coalition structure generation coalition formation