Efficient Automated Negotiation Approach for Non-monotonic Utility Based on Tree Representations

Automated negotiations take place when the negotiating function is performed among intelligent agents. Despite the fact that current human-to-human negotiation appears to involve extremely complex multiple issues, each automated negotiation setting is simple. Specifically, the structure of issues is independent and flat in the existing automated negotiation framework. In this paper, we propose realistic negotiation frameworks for non-monotonic utility functions. Monotonicity of the utility functions is an important characteristic because, if the utility function is monotone, the issues are independent and not interdependent. When the issues are independent, it is useful to separate out the issues and reach a distinct agreement for each sequentially. In addition, we propose an automated mediation protocol for multiple non-monotonic issues negotiation. This mediation protocol is constructed from the communications between agents and a mediator. The procedures of the mediation protocol consist of Recognizing the Grouping issues, Announcement, Bidding, Awarding, and Expediting. In the experiments, we demonstrate that the proposed method results in good outcomes and greater scalability. Additionally, we demonstrate that suitable mediation strategy leads to better outcomes and scalability. The relationship between selfish agents and the quality of solutions is also discussed.