Researchers in the multi-agent systems community of DA1 assume that agents will have to interact with others agents that were designed by different designers for different goals. These diverse agents could benefit each other by collaborating, but they will do so only if the resulting deal is beneficial from each agent’s point of view. One useful definition of beneficial is that of economic rationality, maximizing the agent’s expected payoff in terms of a utility function. An open problem in this area is to design a protocol that allows a large pool of agents to determine which of the subsets among them can profit by working together. A solution to a coalition problem is a partition of the agents into subsets (coalitions), such that each agent in every coalition receives the most utility it can expect.