Strategic Negotiation in Multiagent Environments (Intelligent Robotics and Autonomous Agents) [Hardcover]

Sarit Kraus (Author)

Book Description

Series: Intelligent Robotics and Autonomous Agents series | Publication Date: September 1, 2001

As computers advance from isolated workstations to linked elements in complex communities of systems and people, cooperation and coordination via intelligent agents become increasingly important. Examples of such communities include the Internet, electronic commerce, health institutions, electricity networks, and digital libraries.Sarit Kraus is concerned here with the cooperation and coordination of intelligent agents that are self-interested and usually owned by different individuals or organizations. Conflicts frequently arise, and negotiation is one of the main mechanisms for reaching agreement. Kraus presents a strategic-negotiation model that enables autonomous agents to reach mutually beneficial agreements efficiently in complex environments. The model, which integrates game theory, economic techniques, and heuristic methods of artificial intelligence, can be automated in computer systems or applied to human situations. The book provides both theoretical and experimental results.

Editorial Reviews

Review

"Emotional machines may seem to be the stuff of fantasy. But mechanisms for understanding and exhibiting emotions may be essential if we are to improve that way that computers and humans interact. This comprehensive collection of essays presents the state of the art on this fascinating and challenging research topic. I recommend it to anyone who wants to understand how and why computers will eventually understand what it feels like to have a bad day at the office."--Michael Wooldridge, Department of Computer Science, University of Liverpool

"In this book, Sarit Kraus gives a comprehensive overview of more than a decade of world-class research in automated negotiation. Rigorous, detailed, and illustrated by many practical examples, this book should be on the shelf of everyone who wants to really understand what agents and negotiation are all about."--Michael Wooldridge, Department of Computer Science, University of Liverpool

"A sound theoretical foundation is critically important for the deployment of robust, effective multiagent systems. This book presents, in a formally precise and incisive fashion, a line of research that contributes to just such a foundation. The work constitutes a major contribution to the underlying theory of multiagent negotiation."--Jeffrey S. Rosenschein, Institute of Computer Science, Hebrew University of Jerusalem, Israel

"Sarit Kraus has been for many years a pioneer in the formal theory and strategy of negotiation among multiple agents."--Benjamin Grosof, Sloan School of Management, MIT

"Strategic Negotiation in Multiagent Environments is the best comprehensive source on modern approaches to negotiation from the perspective of multiagent systems. Computers and Thought Award winner Sarit Kraus has been researching negotiation theory for years, and she has done a superb job of pulling together the fruits of that work in a form accessible to any reasonably sophisticated researcher or practitioner. This book belongs in the collection of anyone seriously pursuing interests in dynamic multiagent systems."--Les Gasser, Graduate School of Library and Information Science, University of Illinois at Urbana-Champaign

About the Author

Sarit Kraus is Professor of Mathematics and Computer Science at Bar-Ilan University, Israel, and Professor of Computer Science in the Institute for Advanced Computer Studies at the University of Maryland, College Park. She is the coauthor of Heterogeneous Agent Systems (MIT Press, 2000).

Product Details

• Hardcover: 280 pages
• Publisher: The MIT Press; 1st edition (September 1, 2001)
• Language: English
• ISBN-10: 0262112647
• ISBN-13: 978-0262112642
• Product Dimensions: 9.3 x 6.6 x 0.9 inches
• Shipping Weight: 1.3 pounds (View shipping rates and policies)
• Average Customer Review: 4.0 out of 5 stars  See all reviews (1 customer review)
• Amazon Best Sellers Rank: #2,615,708 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

2 of 2 people found the following review helpful:

4.0 out of 5 stars A prelude to automated negotiation, January 26, 2004

By 

Dr. Lee D. Carlson (Baltimore, Maryland USA) - See all my reviews
(VINE VOICE)    (HALL OF FAME REVIEWER)    (REAL NAME)   

Amazon Verified Purchase

This review is from: Strategic Negotiation in Multiagent Environments (Intelligent Robotics and Autonomous Agents) (Hardcover)

The automation of trading and negotiation is becoming more important with each passing year in the twenty-first century. The New York Stock Exchange, the Chicago Board of Trade, NASDAQ, and Web-based businesses like Amazon and Ebay are facing pressure to automate not only their purchasing, but also their abilities to negotiate business deals on part of their customers. In addition, recently issues with electricity and bandwidth marketing will entail a reliable and efficient method of automated bargaining in order to ensure reliable electrical grids and efficient bandwidth allocations. The automation in all of these areas will need to be trustworthy, efficient, and profitable for both the customer and the company if it is to be a viable part of business life.

This book outlines a mathematical theory of negotiation, and combines concepts from game theory, mathematical economics, and artificial intelligence in order to build strategic negotiation models, and discusses their empirical validation. The author bases her model on the Rubenstein model of alternating offers, wherein intelligent agents exchange offers until they reach an agreement or until one of them opts out of the negotiations. She concentrates specifically on the abilities of intelligent agents to coordinate their activities with other agents and to cooperate with them. These agents are assumed to be self-interested, rational, and autonomous. They do not share a common goal and each has its own set of preferences and acts according to them. Because of space constraints, only the first four chapters will be reviewed here.

In the introduction to the book, the author reviews some of the basic concepts from game theory, such as the extensive and strategic representations of a game. The coalitional representation is left to the references. Then, in chapter 2, she discusses in some detail the Rubenstein model of alternating offers, wherein there are N agents the need to reach an agreement on a particular issue, and the agents can only take actions at certain times determined in advance and known to the agents. There is no decision-regret, and the agents are provided with utility functions. The goal is then to find simple strategies that could be recommended to all agents so that no agent could benefit by an alternate strategy.

The author turns to negotiations about data allocation in chapter 3, where servers are autonomous and self-interested, can share documents, and need to make decisions where to locate data available to them. She assumes that the agents prefer any agreement in a given time period over the continuation of the negotiation process indefinitely, assumes losses of unused information, and only considers utility functions with fixed losses per unit time and a discount rate constant in time. The negotiation process is considered in cases of complete information, in which the servers know the expected usage of each dataset, but not the future usage, and in cases of incomplete information, where the expected usage is not, but only the past usage. Recognizing that the allocation problem is NP-complete in these cases, she brings in various techniques from optimization theory and artificial intelligence to deal with it. Simulations using hill-climbing, are shown to give better results than backtracking or genetic algorithms. She also gives a literature survey on distributed file allocation and with various other techniques for the incomplete information case.

In chapter 4, the author discusses bilateral negotiations for resources. In this scenario, one agent has access to a resource and is using it during the negotiation process, while another agent is waiting to use the resource. Cases of both complete and incomplete information are treated, along with cases of multiple encounters. The case of resource allocation is different than that of data allocation in that in resource allocation each agent always prefers a larger portion of the resource. Also, one of the agents loses over time while the other gains in resource allocation. The author discusses an interesting example dealing with the sharing of resources between NASA and ESA, and which illustrates the theorem that an agreement will be reached in the first or second period. This result is also different from the data allocation case, where in the latter, agreement is always reached in the first time period. The case of incomplete information is studied using the notion of "sequential equilibrium." This requires that an agent's strategy in each time period will be optimal given its opponents' strategies and its beliefs, and the history up the given time period. Three conditions are imposed on the sequence of strategies and the agent's system of beliefs that serve to characterize sequential equilibrium. The author again compares this with the data allocation, and concludes that for resource allocation with incomplete information, there is less incentive for telling the truth. The author then addresses the situation where the agents can meet several times in order to carry out the negotiation. She points out the use of "pooling" and "separating" equilibria in analyzing the situations of multiple encounters. An agent can have different utility functions, giving the agents different "types". If all these types select the same strategy in all states, this is a pooling equilibrium. If it is not, it is a separating equilibrium, and then it is possible to identify the agent's type from its actions. It is shown, as expected, that the negotiations in the multiple encounter case end no later than the second time period. Here again, the author uses the NASA and ESA robot examples to illustrate the results she derives for multiple encounters. She also shows the results of simulations to validate the agent's performance in situations of multiple encounters. Brief discussion is devoted to extensions of this model, including two agents with more than two encounters, multiple resources, and cases where there are more than two types of agents. For the case of many resources, the author concludes that the agent holding the resource will not stop negotiating with one agent and initiate a new negotiation process with another agent for a different resource. Other approaches to the resource allocation problem follow.