Automated negotiation systems with self-interested agents are becoming increasingly important. One reason for this is the technology push of a growing standardized communication infrastructure - Internet, WWW, NII, EDI, KQML, FIPA, Concordia, Voyager, Odyssey, Aglets, Telescript, Java, etc - over which separately designed agents belonging to different organizations can interact in an open environment in real-time and safely carry out transactions. The second reason is strong application pull for computer support for negotiation at the operative decision making level. For example, we are witnessing the advent of small transaction commerce on the Internet for purchasing goods, information, and communication bandwidth. There is also an industrial trend toward virtual enterprises: dynamic alliances of small, agile enterprises which together can take advantage of economies of scale when available (e.g., respond to more diverse orders than individual agents can), but do not suffer from diseconomies of scale.
Multiagent technology facilitates the automated formation of such dynamic coalitions at the operative decision making level. This automation can save labor time of human negotiators, but in addition, other savings are possible because computational agents can be more effective at finding beneficial short-term coalitions than humans are in strategically and combinatorially complex settings.
We have devised a normative theory of which coalitions should form among agents that operate under costly computation. This theory also determines the stability of the coalition structures. We verified the theory on a large scale real world vehicle routing problem consisting of multiple different dispatching companies.
We have also designed an optimal anytime coalition structure generation algorithm. We have proven that for any computation allocation (i.e. any amount of search for a good coalition structure), any other algorithm finds a worse coalition structure than our algorithm (both algorithms are compared according to their worst case performance).
See also Negotiation among Computationally Bounded Self-interested Agents.
Questions about this research may be directed to sandholm@cs.wustl.edu.Larson, K. and Sandholm, T. 2000. Anytime Coalition Structure Generation: An Average Case Study. Journal of Experimental and Theoretical AI, 11, 1-20.
Sandholm, T., Larson, K., Andersson, M., Shehory, O., and Tohmé, F. 1999. Coalition Structure Generation with Worst Case Guarantees. Artificial Intelligence, 111(1-2), 209-238.
Tohmé, F. and Sandholm, T. 1999. Coalition Formation Processes with Belief Revision among Bounded Rational Self-Interested Agents. Journal of Logic and Computation, 9(97-63), 1-23.
Larson, K. and Sandholm, T. 1999. Anytime Coalition Structure Generation: An Average Case Study. Third International Conference on Autonomous Agents (AGENTS), pp. 40-47, Seattle, WA, May.
Sandholm, T., Shehory, O., Andersson, M., Larson, K., and Tohmé, F. 1998. Anytime Coalition Structure Generation with Worst Case Guarantees. Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI), pp. 46-53, Madison, WI, July.
Sandholm, T. and Lesser, V. 1997. Coalitions among Computationally Bounded Agents. Artificial Intelligence 94(1), 99-137, Special issue on Economic Principles of Multiagent Systems.