Automated bilateral negotiation with incomplete information in the e-marketplace.

Automated negotiation is a basic element in multi-agent systems (MAS), which helps autonomous agents to find a mutual agreement by resolving conflicts. Research on automated negotiation can highly affect the quality of e-marketplaces where autonomous agents buy/sell on behalf of their owners. Pareto-efficiency is a seminal property of the negotiation outcome (an outcome is Pareto-optimal if there is no other outcome that makes an agent better off without making the other agent worse off). Unfortunately, reaching to a Pareto-optimal agreement is a complex problem, particularly when agents negotiate over multiple issues (such as price, warranty and delivery) with incomplete information about each other’s preferences. Although an extensive academic research has explored the single issue negotiation, much less research investigated the multi-issues negotiation with incomplete information. So far, using fuzzy similarity with smart trade-offs was a useful approach to generate near Pareto-optimal offers in multi-issues negotiation. In this approach, a pool of random offers helps an agent to find the most similar one with the last received offers. However, this approach has a high time-complexity. The main purpose of this thesis is to generate Pareto-optimal offers in multi issues bilateral negotiation with incomplete information. To study this problem,at first, negotiations should be grounded on a model that governs the interactions and determines relation between agents. Given this background, the following objectives are considered to be carried out in this study: (i) forming a multi-issues bilateral negotiation model by adapting existing single-issue models. (ii) generating Pareto-optimal offers with one-side incomplete information. (iii) generating Pareto-optimal offers with both-sides incomplete information. To fulfill the first objective, each negotiation issue is modeled by a split the pie of size 1 game where the total negotiation is a nonzero- sum game. In addition, the well-known alternating-offers protocol is used to govern the interactions. To generate Pareto-optimal offer with one-side incomplete information, at first,an algorithm is presented to generate multi-issue offers with perfect (complete)information. This algorithm is called maximum greedy trade-offs (MGT) and can generate offers at given aspiration-level (target utility) in O(n). The MGT algorithm is useful to explore the properties of the Pareto-optimal offers. This algorithm comes with some corollaries that form a learning approach in one-side incomplete problem. The advantage of the MGT algorithm is that it does not need the exact opponent’s preferences to generate Pareto-optimal offers, instead, it works with a greedy sequence. An agent with incomplete information can find an estimation of the optimal offer in early rounds of the negotiation, however as time passes, it can likely generate Pareto-optimal offer by learning the greedy greedy sequence. In this case, the agent with incomplete information can learn the greedy sequence in O(n log n). In one-side incomplete information problem, comparison between MGT algorithm and smart random trade-offs (SRT) algorithm indicates that MGT outperforms SRT. Finally, the problem of finding Pareto-optimal offers in both sides with incomplete information is investigated. In this case, agents need to be tailored by a learning capability that explores the opponent’s preferences. To this end, we have developed an incremental learning approach using soft-computing techniques to learn opponent’s preferences in multi-issue negotiation with incomplete information. In this learning approach, firstly, the size of possible preferences is reduced by encoding the uncertain preferences into a series of fuzzy membership functions. Then, the process of searching the best fuzzy preferences that articulates the opponent’s intention is conducted by genetic algorithm. Whenever an agent receives an offer it forms a constraint and updates the fitness of individuals in the given population of preferences based on the degree of the constraint satisfaction. Experimental results show that our learning approach can estimate the opponent’s preferences effectively. Moreover, results indicate that agents equipped by this learning capability can generate Pareto-efficient offers by MGT algorithm. Results, in both-sides incomplete information problem, indicate that MGT out performs SRT. The reason is that, SRT algorithm is sensitive to the accuracy of the learned preferences while MGT algorithm can generate Pareto-optimal offers even with an approximation of the learned preferences.

Preview PDF FSKTM 2011 24R.pdf Download (593kB) | Preview

Actions (login required)

View Item