Multi-agent coordination through coalition formation
Lecture notes in computer sciencePublished 1 January 1998
Onn Shehory, Katia Sycara, Somesh Jha
Citations108
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The problems that arise when attempting to utilize the theoretical coalition formation algorithms for a real-world system are presented, how some of their restrictive assumptions can be relaxed are demonstrated, and the resulting benefits are discussed.
Abstract
Incorporating coalition formation algorithms into agent systems shall be advantageous due to the consequent increase in the overall quality of task performance. Coalition formation was addressed in game theory, however the game theoretic approach is centralized and computationally intractable. Recent work in DAI has resulted in distributed algorithms with computational tractability. This paper addresses the implementation of distributed coalition formation algorithms within a real-world multi-agent system. We present the problems that arise when attempting to utilize the theoretical coalition formation algorithms for a real-world system, demonstrate how some of their restrictive assumptions can be relaxed, and discuss the resulting benefits. In addition, we analyze the modifications, the complexity and the quality of the cooperation mechanisms. The task domain of our multi-agent system is information gathering, filtering and decision support within the WWW.
Keywords
Social SciencesDecision SciencesEconomics, Econometrics and Finance
Communications of the ACMAgents that reduce work and information overload
2,321 Citations1994Pattie Maes
Results from several prototype agents that have been built using an approach to building interface agents are presented, including agents that provide personalized assistance with meeting scheduling, email handling, electronic news filtering, and selection of entertainment.
Elsevier eBooksNewsWeeder: Learning to Filter Netnews
2,022 Citations1995Ken Lang
The results show that a learning algorithm based on the Minimum Description Length (MDL) principle was able to raise the percentage of interesting articles to be shown to users from 14% to 52% on average.
Cambridge University Press eBooksRational Behaviour and Bargaining Equilibrium in Games and Social Situations
1,443 Citations1977John C. Harsanyi
Artificial IntelligenceNegotiation as a metaphor for distributed problem solving
1,235 Citations1983Randall Davis, Reid G. Smith
A framework called the contract net is presented that specifies communication and control in a distributed problem solver, and comparisons with planner, conniver, hearsay-ii, and pup 6 are used to demonstrate that negotiation is a natural extension to the transfer of control mechanisms used in earlier problem-solving systems.
Journal of Artificial Intelligence ResearchA Market-Oriented Programming Environment and its Application to Distributed Multicommodity Flow Problems
529 Citations1993Michael P. Wellman
WALRAS provides basic constructs for defining computational market structures, and protocols for deriving their corresponding price equilibria, and sees that careful construction of the decision process according to economic principles can lead to efficient distributed resource allocation and that the behavior of the system can be meaningfully analyzed in economic terms.
IEEE ExpertDistributed intelligent agents
528 Citations1996Katia Sycara, Anandeep Pannu +3 more
In Retsina, the authors have developed a distributed collection of software agents that cooperate asynchronously to perform goal-directed information retrieval and integration for supporting a variety of decision-making tasks.
WebWatcher: A Learning Apprentice for the World Wide Web
496 Citations1995R. Armstrong, Dayne Freitag +2 more
An information seeking assistant for the world wide web, called WebWatcher, interactively helps users locate desired information by employing learned knowledge about which hyperlinks are likely to lead to the target information.
Communications of the ACMA softbot-based interface to the Internet
452 Citations1994Oren Etzioni, Daniel S. Weld
The Internet Softbot (software robot) is a fullyimplemented AI agent developed at the University of Washington that uses a UNIX shell and the World-Wide Web to interact with a wide range of internet resources.
Middle-Agents for the Internet.
405 Citations1997Keith Decker, Katia Sycara +1 more
A spectrum of middle-agents is identified, characterizes the behavior of three different types, and reports on initial experiments that focus on evaluating performance tradeoffs between matchmaking and brokering middle- agents, according to criteria such as load balancing, robustness, dynamic preferences or capabilities, and privacy.
International Journal of Cooperative Information SystemsCOORDINATION OF MULTIPLE INTELLIGENT SOFTWARE AGENTS
166 Citations1996Katia Sycara, Dajun Zeng
This paper presents the distributed system architecture, agent collaboration interactions, and a reusable set of software components for structuring agents, which are developing collaborating agents in diverse complex real world tasks, such as organizational decision making, investment counseling, health care and electronic commerce.
DSpace@MIT (Massachusetts Institute of Technology)Coalition, Cryptography, and Stability: Mechanisms for Coalition Formation in Task Oriented Domains
163 Citations2011Gilad Zlotkin, Jeffrey S. Rosenschein
A simple coalition formation mechanism that uses cryptographic techniques for subadditive Task Oriented Domains that is efficient, symmetric, and individual rational and satisfies coalition rationality.
Coalition formation among bounded rational agents
136 Citations1995Tüomas Sandholm, Victor Lesser
Designing behaviors for information agents
131 Citations1997Keith Decker, Anandeep Pannu +2 more
A set of architectural building blocks that support the specification of behaviors for these information agents in a way that allows periodic actions, interleaving of planning and execution, and the concurrent activation of multiple behaviors with asynchronous components are discussed.
Forming coalitions in the face of uncertain rewards
124 Citations1994Steven P. Ketchpel
A "two agent auction" mechanism is suggested to complement an existing coalition formation algorithm for solving this problem of finding coalitions of agents that agree to work together for the benefit of all the members of the group.
Formation of overlapping coalitions for precedence-ordered task-execution among autonomous agents *
84 Citations1996Onn Shehory, Sarit Kraus
Algorithms that lead agents to the formation of overlapping t:oMition~, where each coalition is assigned a goal are presented, appropriate for agents working as a Distributedrolflem Solving system in non-superadditive environments.
On Using KQML for Matchmaking
68 Citations1995Daniel Kuokka, Larry Harada
Several problematic issues and potential solutions are discussed, including representational challenges in advertising complex databases, the need for persistent requests in information brokering, the dilemm~ between explicit vs. implicit broKQML, problems in error recovery and response timing, consistency among information providers, and efficiency.
Unified Information and Control Flow in Hierarchical Task Networks
53 Citations1996Michael P. Williamson, Keith Decker +1 more
This paper presents a framework for the representation and execution of hierarchical plans with information producing actions, conditional branches, periodic actions, and loops that subsumes several techniques found in the recent literature.
Lecture notes in computer scienceFacilitating open communication in agent systems: The InfoSleuth infrastructure
45 Citations1997Marian Nodine, Amy Unruh
It is argued that an open multiagent system should define the following support elements for agent communication: a common set of speech acts to define the types of messages that an agent might send to another agent.