@Article{sandholm99b,
  author =	 {Tuomas Sandholm and Kate Larson and Martin Anderson
                  and Onn Shehory and Fernando Tohm\'{e}},
  title =	 {Coalition Structure Generation with Worst Case
                  Guarantees},
  journal =	 {Artificial Intelligence},
  googleid =	 {EteI9udjyxkJ:scholar.google.com/},
  year =	 1999,
  volume =	 111,
  number =	 {1-2},
  pages =	 {209--238},
  abstract =	 {Coalition formation is a key topic in multiagent
                  systems. One may prefer a coalition structure that
                  maximizes the sum of the values of the coalitions,
                  but often the number of coalition structures is too
                  large to allow exhaustive search for the optimal
                  one. Furthermore, finding the optimal coalition
                  structure is NP-complete. But then, can the
                  coalition structure found via a partial search be
                  guaranteed to be within a bound from optimum? We
                  show that none of the previous coalition structure
                  generation algorithms can establish any bound
                  because they search fewer nodes than a threshold
                  that we show necessary for establishing a bound. We
                  present an algorithm that establishes a tight bound
                  within this minimal amount of search, and show that
                  any other algorithm would have to search strictly
                  more. The fraction of nodes needed to be searched
                  approaches zero as the number of agents grows. If
                  additional time remains, our anytime algorithm
                  searches further, and establishes a progressively
                  lower tight bound. Surprisingly, just searching one
                  more node drops the bound in half. As desired, our
                  algorithm lowers the bound rapidly early on, and
                  exhibits diminishing returns to computation. It also
                  significantly outperforms its obvious
                  contenders. Finally, we show how to distribute the
                  desired search across self-interested manipulative
                  agents.},
  keywords =     {multiagent coalitions},
  url =		 {http://jmvidal.cse.sc.edu/library/sandholm99b.pdf},
  doi =		 {10.1016/S0004-3702(99)00036-3},
  cluster =	 1858689119145219858
}