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

Rating:
Summary: A prelude to automated negotiation
Review: 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.