# Multi-Issue Negotiation Protocol with Pre-Domain Narrowing
## 1 Introduction  
Consensus building among agents has attracted increased attention in recent studies on multi-agent systems. Because autonomous agents act independently according to the goals and preferences of their user (owner), conflicts among agents can occur. Therefore, there is a need for technology that efficiently resolves conflict situations and makes agreements among agents while also maintaining their independence and privacy. To achieve this, automated negotiation is attracting attention [1; 2; 3]. Agents are also employed in negotiations when a human negotiator is starting a crucial task. They can assist humans in finding and making an agreement during negotiations in real life. They can apply to real-world scenarios, such as e-markets [4; 5], cooperative behavior among robots [6], and flexible supply chain networks [7]. Therefore, the development of automated negotiating agents requires further study considering their potential in applications. A basic automated negotiation problem is the multi-issue bargaining problem, wherein some agents negotiate, attempting to make an agreement. The negotiation domain is shared among agents comprising multiple issues, with each issue having multiple options. Each agent has its preference and aims to maximize its utility in making an agreement. In such a problem, where agents' preferences differ, if an agent discloses its preferences, exploitation may occur, whereby other agents' acquisition utilities are unilaterally enhanced. Because of this, agents prefer not to disclose their preferences during negotiation. In a multi-issue negotiation problem, the problem size, which is the same as the domain size, is expressed by \(\sum\limits_{i=1}^{n}k_{i}\), where \(n\) is the number of issues and \(k_{i}\) is the number of options for the \(i\)th issue. Therefore, as the number of issues and number of options for each issue increase, the utility space the agent must search through during negotiation widens. In other words, the larger the domain, the more time the processes require, thereby decreasing the negotiation efficiency. Some negotiation protocols have been proposed wherein a mediator collects the utility information of each agent and creates multiple alternatives of agreements to handle large-scale multi-issue negotiation [8; 9; 10; 11]. However, in such protocols, a limitation is placed on agents' privacy because all agents have to disclose their private information by following the mediator and pre-decided negotiation rules. In addition, few existing works attempt to define multistage negotiation protocols for narrowing the domain through the negotiations among agents without the mediator. To realize efficient negotiations, there is a need to narrow down the domain space before the actual negotiations are performed and narrow down the negotiation domain space by an efficient negotiation protocol. Moreover, the protocol would be more likely to be adopted if the narrowing phase increases the utility and social welfare each agent could obtain. In this study, we propose a novel automated negotiation protocol for efficient negotiation in large-scale domain problems. The protocol is designed to decrease the amount of information that agents must disclose to other agents or mediators during a negotiation. In the proposed protocol, the negotiation session is divided into two phases: the \"negotiation domain space-narrowing phase\" and \"main negotiation phase\". The negotiation domain space-narrowing phase is further divided into the narrowing of issues and the narrowing of options for each issue. We propose two methods for narrowing issues. The first is for each agent to inform the mediator of the issues it does not prioritize. The second is to narrow the number of issues through negotiation among agents. Regarding the narrowing of options, each agent submits to the mediator a list of options that it deems unnecessary for negotiation, and the mediator narrows the options based on the lists.