Better Than the Best: The Power of Cooperation

Tad Hogg and Bernardo A. Huberman
Dynamics of Computation Group
Xerox Palo Alto Research Center
Palo Alto, CA 94304
hogg@parc.xerox.com

@INCOLLECTION {,
 AUTHOR = "Tad Hogg and Bernardo A. Huberman",
 TITLE = "Better Than the Best: The Power of Cooperation",
 BOOKTITLE = "1992 Lectures in Complex Systems",
 EDITOR = "Lynn Nadel and Daniel Stein",
 PAGES = "165-184",
 SERIES = "SFI Studies in the Sciences of Complexity",
 VOLUME = "V",
 PUBLISHER = "Addison-Wesley",
 ADDRESS = "Reading, MA",
 YEAR = "1993"}

Abstract

We show that when agents cooperate in a distributed search problem, they can solve it faster than any agent working in isolation. This is accomplished by having agents exchange hints within a computational ecosystem. We present a quantitative assessment of the value of cooperation for solving constraint satisfaction problems through a series of experiments. Our results suggest an alternative methodology to existing techniques for solving constraint satisfaction problems in computer science and distributed artificial intelligence.
postcript (283K, 22 pages, available on-line only within Xerox)