@InProceedings{	  sandholm98a,
  author =	 {Tuomas Sandholm and Kate Larson and Martin Andersson and
                  Onn Shehory and F. Tohm\'{e} },
  title =	 {Worst-Case-Optimal Anytime Coalition Structure
                  Generation},
  booktitle =	 {Proceedings of {AAAI-98}},
  googleid = 	 {HANZ_9cA4OgJ:scholar.google.com/},
  pages =	 {43--56},
  year =	 1998,
  month =	 {July},
  publisher =	 pub-aaai,
  address =	 pub-aaai:adr,
  abstract =	 { Coalition formation is a key topic in multiagent
                  systems. One would 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. 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 drastically outperforms its
                  obvious contenders. Finally, we show how to
                  distribute the desired search across self-interested
                  manipulative agents.},
  keywords =     {multiagent coalitions},
  comment =	 {Says that searching $2^a -1$ nodes is neccessary and
                  suficient to guarantee that the utility of the best
                  coalition structure found is no works that $a$-times
                  the optimal coalition structure.},
  url =		 {http://jmvidal.cse.sc.edu/library/sandholm98a.pdf},
  created =	 1001877534,
  cluster = 	 {16780413139284460316}
}