Scalability Evaluation of Secure Computations for Multi-Issue Negotiation

In multi-issue negotiation problems within multi-agent systems, it is essential to preserve the privacy of each agent's utility information. Fujita, Ito, and Klein proposed a negotiation protocol based on local search, in which the utility values for each intermediate candidate agreement are concealed using an additive secret sharing scheme. While their protocol aims to protect privacy, the sequence of candidate agreements and their transitions are explicitly revealed during the negotiation process, leaving room for inferring partial utility information. To overcome this limitation, the authors previously extended the protocol to realize fully private hill-climbing-based negotiation under multi-party secure computation (MPC), concealing all intermediate information and revealing only the final agreement. This earlier work was presented at WICT-DM 2024. Building on that foundation, the present study focuses on evaluating the scalability of privacy-preserving negotiation in multi-agent settings, and introduces an extension to support Simulated Annealing (SA) as a representative heuristic method. The proposed protocol securely executes all computations—including candidate generation, utility evaluation, and acceptance decisions—under MPC without revealing any intermediate candidate agreements or comparison results. We evaluate its scalability in negotiations with 2 to 17 agents using a personal computing environment (Apple M3 Pro laptop). The results show that the protocol successfully completes negotiation with 17 agents in approximately 10,659 seconds while maintaining agreement quality. A timer-based breakdown further reveals that random number generation and array updates dominate the execution cost, accounting for more than 70% in large-agent settings, whereas utility computation and acceptance decisions contribute only marginally. These findings demonstrate that MPC can be applied to large-scale multi-agent negotiations with acceptable overhead, and also indicate that future performance improvements should focus on optimizing the identified bottlenecks.