Minimum Search To Establish Worst-Case Guarantees in Coalition Structure Generation

In this context, while it methods (see, e.g., [Shehory and Kraus, 1998; Sandholm et is desirable to generate a coalition structure that al., 1999; Sen and Dutta, 2000; Dang and Jennings, 2004; maximizes the sum of the values of the coalitions, Rahwan et al., 2009b]). In this context, an important line of the space of possible solutions is often too large research is the development of anytime CSG algorithms. In to allow exhaustive search. Thus, a fundamental particular, an algorithm is "anytime" if it can return a solution open question in this area is the following: Can we at any point of time during its execution, and the quality of its search through only a subset of coalition structures, solution improves monotonically until termination. This is and be guaranteed to find a solution that is within particularly desirable in the multi-agent system context since a desirable bound β from optimum? If so, what is the agents might not always have sufficient time to run the the minimum such subset?