[Main Page] [Personnel] [Research] [Classes] [Publications] [Openings] [Links]
[BACK TO RESEARCH]

Multiagent Systems Research Group

Negotiation among computationally bounded self-interested agents

In this work we look at inherently distributed combinatorial problems - resource and task allocation and scheduling among agents with different levels of autonomy, eg. representing different real world enterprises that are seeking synergies by limited cooperation. One of our applications includes several freight dispatch centers of different companies negotiating over the solution to their vehicle routing problem. Other applications are from the factory floor scheduling domain, where different companies in a subcontracting web negotiate over the joint scheduling problem, and from the airport resource management domain, where the negotiation takes place over the servicing of airplanes between flights.

In domains where the agents represent different real world entities such as different companies, self-interest prevails. The agents cannot be assumed to use cooperative negotiation strategies (designed centrally), but instead, each agent will try to use a strategy that provides the highest possible utility for itself without concern of the other agents' utilities. Work in game theory addresses exactly this issue. What makes our work unique is the fact that we relax the assumption of perfect rationality. In classical game theory it is assumed that given its possibly imperfect information, an agent perfectly deduces (without any deduction cost or time delay), what action it should choose at any given time. On the other hand, we assume that the deduction process itself is costly: either an agent has to pay for computational resources or the computation with its own limited resources takes time, thus making the domain actions less valuable. In our NP-hard example problems it would be clearly unrealistic to assume that the agents can solve the problems exactly without any delay or cost.

We are studying different commitment strategies and protocols in multiagent systems, and the possibility of carrying out contracts without external enforcement. We have studied the role of marginal costs as a basis for negotiation and questions of bounded rationality and deliberation scheduling when the exact computation of marginal costs is intractable. We have also analyzed the effect of asynchrony and message congestion among negotiators and greater domain risk tolerance to enhance the negotiation process computationally. We are currently studying the usefulness of distributed versions of a variety of combinatorial optimization algorithms from the AI and OR communities. Some other research issues we address are: using machine learning techniques to alternate between different negotiation strategies based on dynamic properties of the environment, cost-based constraint relaxation, anticipation of future contracts in an agent's negotiation strategy, fair on-line profit division schemes among agents, contracts involving multiple agents as opposed to just two, and optimal coalitions under computational resource bounds.

See also Coalition Formation, Electronic Commerce, and Automated Contracting.

Questions about this research may be directed to sandholm@cs.wustl.edu.

Selected publications