GENERATING PARETO-OPTIMAL OFFERS IN BILATERAL AUTOMATED NEGOTIATION WITH ONE-SIDE UNCERTAIN IMPORTANCE WEIGHTS

摘要

Pareto efficiency is a seminal condition in the bargaining problem which leads autonomous agents to a Nash-equilibrium. This paper investigates the problem of the generating Pareto-optimal offers in bilateral multi-issues negotiation where an agent has incomplete information and the other one has perfect information. To this end, at first, the bilateral negotiation is modeled by split the pie game and alternating-offer protocol. Then, the properties of the Pareto-optimal offers are investigated. Finally, based on properties of the Pareto-optimal offers, an algorithmic solution for generating near-optimal offers with incomplete information is presented. The agent with incomplete information generates near-optimal offers in O(n log n). The results indicate that, in the early rounds of the negotiation, the agent with incomplete information can generate near-optimal offers, but as time passes the agent can learn its opponents preferences and generate Pareto-optimal offers. The empirical analysis also indicates that the proposed algorithm outperform the smart random trade-offs (SRT) algorithm.