A Preliminary Analysis of Computational Complexity of the Threshold Adjusting Mechanism in Multi-issue Negotiations

In this paper, we propose a threshold adjusting mechanism in complex negotiations among software agents. The mechanism reduces computational complexity to find agreements that produce higher social welfare. Multi-issue negotiation protocols have been studied widely and represent a promising field since most negotiation problems in the real world involve interdependent multiple issues. We have proposed negotiation protocols where a bidding-based mechanism is used to find social-welfare maximizing deals. The threshold adjusting mechanism proposed here reduces the number of candidate bids. The preliminary experimental results show that the threshold adjusting mechanism can reduce the computational cost while keeping enough optimality.