In this work we look at automated contracting among computationally bounded self-interested agents. We study inherently distributed combinatorial problems - resource and task allocation and scheduling among agents with different levels of autonomy, e.g.. 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 have devised an optimal method for carrying out contracts in cyberspace where external enforcement is not guaranteed. 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 have developed a leveled commitment contracting protocol that provably improves the efficiency of deals even if agents try to manipulate the protocol. This protocol has been adopted in several research groups in academia, and is currently being patented and licensed through BusinessBots, Inc, a startup company in Palo Alto, CA.
We have also devised contract types that provably lead to the optimal task allocation among agents, and can be used as an anytime task (re)allocation scheme in real-time settings. This work is being patented and licensed through BusinessBots, Inc.
We have also devised and analyzed the optimal manipulations that an agent can use in markets based on classical general equilibrium theory.
We are currently studying limited anticipation of future contracts in an agent's negotiation strategy, fair on-line profit division schemes among agents, and the time-quality tradeoff in complex contracting settings.
See also Coalition Formation and Negotiation among Computationally Bounded Self-interested Agents.
Questions about this research may be directed to sandholm@cs.wustl.edu.Sandholm, T. 1998. Contract Types for Satisficing Task Allocation: I Theoretical Results, AAAI Spring Symposium Series: Satisficing Models, Sanford University, Stanford, CA, March 23-25.
Andersson, M and Sandholm, T. 1998. Contract Types for Satisficing Task Allocation: II Experimental Results, AAAI Spring Symposium Series: Satisficing Models, Sanford University, Stanford, CA, March 23-25.
Sandholm, T. 1997. Necessary and Sufficient Contract Types for Optimal Task Allocation. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan. Poster presentation. (Acceptance rate 47%)
Sandholm, T. and Lesser, V. 1997. Issues in Automated Negotiation and Electronic Commerce: Extending the Contract Net Framework. In Readings in Agents, Huhns, M. and Singh, M. (eds.), Morgan Kaufmann Publishers, October.
Sandholm, T. and Ygge, F. 1997. On the Gains and Losses of Speculation in Equilibrium Markets. 15th International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan. (Acceptance rate 24%)
Sandholm, T. and Lesser, V. 1996. Advantages of a Leveled Commitment Contracting Protocol. Thirteenth National Conference on Artificial Intelligence (AAAI-96), Portland, OR, pp. 126-133. (Acceptance rate 31%)
Sandholm, T. 1996. Limitations of the Vickrey Auction in Computational Multiagent Systems. Second International Conference on Multiagent Systems (ICMAS-96), Keihanna Plaza, Kyoto, Japan, December, pp. 299-306. (Acceptance rate 28%)