Efficient issue-grouping approach for multiple interdependent issues negotiation between exaggerator agents

•We propose a reasonable approach to reducing computational cost.•Our method decomposes the contract space into several independent sub-spaces.•We demonstrate that our protocol allows optimal outcomes with high-scalability.•We employ the limitation of strong votes to our proposed method.

Many real-world negotiations involve multiple interdependent issues, which makes an agent's utility functions complex, with nonlinear shapes and multiple optima. Traditional negotiation mechanisms were designed for linear utilities, and do not fare well in nonlinear contexts. One of the main challenges in developing effective nonlinear negotiation protocols is scalability; it can be extremely difficult to find high-quality solutions when there are many issues, due to computational intractability. One reasonable approach to reducing computational cost, while maintaining good quality outcomes, is to decompose the contract space into several largely independent sub-spaces. In this paper, we propose a method based on this concept. A mediator finds sub-contracts in each sub-space based on votes from the agents, and combines the sub-contracts to produce the final agreement. We demonstrate, experimentally, that our protocol allows high-optimality outcomes with greater scalability than previous efforts. We also demonstrate a method for addressing the potential problem of strategic non-truthful voting by the agents.