An Effective Dynamic Programming Algorithm for Optimal Coalition Structure Generation Coalition formation is one of the most studied topics in multiagent systems. Central to this endeavor is the problem of partitioning the set of agents into exhaustive and disjoint coalitions so as to maximize social welfare. The coalition structure generation problem is challenging due to the fact that it needs to explore an exponential number of partitions. The fastest exact algorithm to solve this combinatorial optimization problem is ODPIP 1, which is a hybrid version of two previously established algorithms, namely IDP (Improved Dynamic Programming 2 and IP 3. Given this, it is desirable to come up with a new algorithm which could build on the same principles as IDP follows and which in turn, improves upon the state. In this paper, we propose a new algorithm EDP (Effective Dynamic Programming). This algorithm is a new design paradigm for this difficult problem. Both EDP and IDP have been implemented and tested on wellknown data distribution. We prove that EDP is practically faster than IDP.

Automated Mechanism Design: Compact and Decomposition Linear Programming Models In the context of multiagent systems, Automated Mechanism Design (AMD) is the computerbased design of the rules of a mechanism, which reaches an equilibrium despite the fact that agents can be selfish and lie about their preferences. Although it has been shown that AMD can be modelled as a linear program, it is with an exponential number of variables and consequently, there is no known efficient algorithm. We revisit the latter linear program model proposed for the AMD problem and introduce a new one with a polynomial number of variables. We show that the latter model corresponds to a DantzigWolfe decomposition of the second one and design efficient solution schemes in polynomial time for both two models. Numerical experiments compare the solution efficiency of both models and show that we can solve very significantly larger data instances than before, up to 2,000 agents or 2,000 resources in about 35 seconds.