An Extended Alternating-Offers Bargaining Protocol for Automated Negotiation in Multi-agent Systems

摘要

Depending on the protocol type, a negotiation can be categorized as an auction, a contract-net protocol, or a voting or bargaining scheme. While most research focuses on auctions because the strategy is simple, bargaining is still an important way of negotiation. This is because 1. auctions only allow negotiation for price, not other attributes (delivery time, payment method, delivery method, etc.); 2. auctions usually are scheduled in advance and with time restrictions, but some buyers/sellers may not want to wait until an auction opens or finalizes; 3. in some cases, many social factors are important, e.g., trusteeships, friendships, etc., which auctions cannot easily accommodate; 4. most auctions extract the surplus for the benefit of the auctioneer, especially if there is a significant number of bidders. Generally, the bargaining model in Multi-Agent Systems (MAS) adopts the classical alternating-offers model. Currently, there are many variants of this model, such as a model with time deadline (Krauss, Wilkenfeld and Zlotkin 1995; Sandholm and Vulkan 1999), with various information levels (complete/incomplete, symmetric/ asymmetric), with risk of breakdown (one party walks out before negotiation ends), etc. Most of the theoretical foundations have been studied by game theorists (Nash 1950; Rubinstein 1982). However, there is one important limitation of the game-theoretic approach, i.e., searching the solution in exhaustive fashion. Considering the limitation of computational power, many heuristic techniques are adopted to develop new models, namely heuristic-based negotiation models, characterized by learning mechanisms such as Bayesian learning (Zeng and Sycara 1998), influence diagrams (Mudgal and Vassileva 2000), evolutionary algorithm (van Bragt, Gerding and LaPoutre 2000). Using these models, the negotiators can make decisions faster to find a good solution, although not necessarily the best one. In addition, some researchers have proposed an argumentation-based model that focuses on natural-language-like negotiation (Hulstijn, Dastani and van der Torre 2001; Jennings et al. 2001; Sycara 1989). The main idea of this work is to provide more flexibility in the negotiation process, such as to allow a negotiator to persuade their opponents to change their perceptions.