Negotiation among self-interested computationally limited agents

In multiagent systems, computational agents search for and make contracts on behalf of the real world parties that they represent. This dissertation analyses negotiations among agents that try to maximize payoff without concern of the global good. Such a self-interested agent will choose the best negotiation strategy for itself. Accordingly, the interaction protocols need to be designed normatively so that the desired local strategies are best for the agents--and thus the agents will use them--then certain desirable social outcomes follow. The normative approach allows the agents to be constructed by separate designers and/or to represent different parties. Game theory also takes a normative approach, but full rationality of the agents is usually assumed. This dissertation focuses on situations where computational limitations restrict each agent\u27s rationality: in combinatorial negotiation domains computational complexity precludes enumerating and evaluating all possible outcomes. The dissertation contributes to: automated contracting, coalition formation, and contract execution. The contract net framework is extended to work among self-interested, computationally limited agents. The original contract net lacked a formal model for making bidding and awarding decisions, while in this work these decisions are based on marginal approximations of cost calculations. Agents pay each other for handling tasks. An iterative scheme for anytime task reallocation is presented. Next it is proven that a leveled commitment contracting protocol enables contracts that are impossible via classical full commitment contracts. Three new contract types are presented: clustering, swaps and multiagent contracts. These can be combined into a new type, CSM-contract, which is provably necessary and sufficient for reaching a globally optimal task allocation. Next, contracting implications of limited computation are discussed, including the necessity of local deliberation scheduling, and tradeoffs between computational complexity and monetary risk when an agent can participate in multiple simultaneous negotiations. Finally, issues in distributed asynchronous implementation are discussed. A normative theory of coalitions among self-interested, computationally limited agents is developed. It states which agents should form coalitions and which coalition structures are stable. These analytical prescriptions depend on the performance profiles of the agents\u27 problem solving algorithms and the unit cost of computation. The prescriptions differ significantly from those for fully rational agents. The developed theory includes a formal application independent domain classification for bounded rational agents, and relates it precisely to two traditional domain classifications of fully rational agents. Experimental results are presented. Unenforced exchange methods are particularly desirable among computational agents because litigation is difficult. A method for carrying out exchanges without enforcement is presented. It is based on splitting the exchange into chunks that are delivered one at a time. Two chunking algorithms are developed, as well as a nontrivial sound and complete quadratic chunk sequencing algorithm. Optimal stable strategies for carrying out the exchange are derived. The role of real-time is also analyzed, and deadline methods are developed that do not themselves require enforcement. All of these analyses are carried out for isolated exchanges as well as for exchanges where reputation effects prevail. Finally, it is argued that the unenforced exchange method hinders unfair renegotiation. The developed methods in all three subareas are domain independent. The possibility of scaling to large problem instances was shown experimentally on an ${\cal N}P$-complete distributed vehicle routing problem. The large-scale problem instance was collected from five real-world dispatch centers. (Abstract shortened by UMI.