Computing Sequences of Coalition Structures

We consider the problem of finding optimal sequences of coalition-structures in realistic applications where organisational structure is an important factor. In particular, we analyse sequential characteristic-function games induced by valuation structures, and define feasible coalition structure sequences as a solution concept for such games. Besides the restrictions on feasible sequences, the valuation structures allow us to express further constraints on the formation of coalitions. We present a new dynamic-programming algorithm for the computation of sequences of feasible coalition structures and evaluate it on several scenarios. Although this is a hard problem, we show that constraints inspired by real-world applications reduce the size of the search space significantly.