In the simultaneous submission method, both agents simultaneously submit issues that do not need to be subject to negotiation, thereby narrowing the number of issues to be negotiated. Table 1 shows an example of narrowing issues using the simultaneous submission method. Each agent submits to the mediator a list of issues in the negotiation domain space, which, from their perspective, do not need to be subject to negotiation. Among the submitted issues, for issues submitted by only one agent, the option that the other agent prefers is decided upon. For issues that both agents have submitted as unnecessary, the mediator randomly decides from the options, and an agreement is determined. Issues that neither party submits become a subject for the main negotiation.

Issue	Agent		Determination Method
	A	B	for Agreeing on an Option
Destination			Main negotiation
Travel expense	×		Agent B chooses
Travel method			Main negotiation
Accommodation	×	×	Select randomly
Meals		×	Agent A chooses

This process is finished after one round of submissions, and messages exchanged for narrowing the issues do not go back and forth multiple times. Further, the number of issues in the negotiation domain space is very small compared with the domain size. Therefore, it is possible to narrow down issues with a small computational cost. However, because an agreement for issues that both agents submit as unnecessary is decided randomly, there is a possibility that win–win alternatives of agreement that would have been convenient for both agents are lost. In addition, because both agents make their submissions simultaneously, they are unable to surmise each other’s intentions or make deals such as gaining the right to decide on one issue by allowing the other agent to decide on another issue.

3. Narrowing Issues Using the Pre-Negotiation

WResearchers also propose a method for determining how to narrow the issues before the main negotiation using pre-negotiation. During the pre-negotiation, negotiation is performed for each issue in the negotiation domain space, in a domain where the options are “subject to the main negotiation”, “Agent A chooses”, and “Agent B chooses”. This pre-negotiation domain is shown in Table 2. In the pre-negotiation method, negotiations are performed in the domain using the alternating offers protocol, as usual, and the alternatives of agreements are decided upon.

Issue	Option
Destination	Main negotiation
	Agent A chooses
	Agent B chooses
Travel expense	Main negotiation
	Agent A chooses
	Agent B chooses
⋮	⋮

Based on the consensus reached during pre-negotiations, the issues that will not be the main negotiation subjects are decided. For example, consider the case where the following agreement was obtained in the pre-negotiation: [Travel destination: Main negotiation, Travel expense: Agent B, Travel method: Main negotiation, Accommodation: Agent A, Meals: Agent A]. In such a case, Agent A chooses the issues “accommodation” and “meals”, whereas Agent B chooses the issue “travel expense”. The remaining issues, “travel destination” and “travel method” are the main negotiation subjects. Notably, if no agreement is reached during the pre-negotiation, the narrowing of issues does not occur, and all issues will be negotiated during the main negotiation phase. The domain size of the pre-negotiation method is ${(a+1)}^n$ , where a is the number of agents participating in the negotiation, and n is the number of issues. If the number of options $k_i$ for each issue in the original domain is greater than 3, the pre-negotiation domain would be smaller than the original domain, making pre-negotiation easier. Compared with the simultaneous submission method, where the mediator makes a random decision for issues submitted as unnecessary by both agents, in this method, the selection is always made by either agent. This allows agents to strategize during the narrowing process; for example, an agent could forgo the right to decide on some issues in exchange for the right to decide on an issue it considers relevant. Thus, the pre-negotiation method makes it easier for both agents to reach a win-win agreement.

4. Narrowing of Options

Each agent submits to the mediator a list of all options in an issue that were not narrowed during the issue-narrowing phase to be excluded from the negotiation. Then, the mediator narrows from the negotiation domain space all options common to the lists submitted by all participating agents and discloses them to the agents. Table 3 shows an example of narrowing options. Options commonly submitted by both agents are eliminated, and the negotiation domain space is narrowed.

Issue	Option	Agent		Option Eliminated
		A	B	Option
Travel destination	Hokkaido	×	×	×
	Tokyo	×	×	×
	Kyoto
Travel method	Flight	×
	Train		×
	Ferry	×	×	×

When narrowing options, the options that agents want to decide whether to delete are at most ${\displaystyle \sum _{i=1\underset{}{\overset{}{n}}{k}_i}^{}}$ , where n is the number of issues, and $k_i$ is the number of options for each issue in the original domain. This computational cost is less than the domain size. Therefore, the computational cost for narrowing the options is very small because the lists are submitted to the mediator only once. In addition, the only information an agent must submit to the mediator is “whether an option may be deleted”. The only information the other agent can know is regarding “the options that both agents agreed to delete” and “the options that an opposing agent agreed to delete, but that this agent did not agree to”. In other words, the other agent cannot know more information unless it increases the options it agrees to delete. Therefore, each agent can efficiently narrow the options in the negotiation domain space while maintaining privacy.

5. Naive Agent Strategies for the Negotiation Domain Space Narrowing

WResearchers design naive agent strategies considering the negotiation domain space for the proposed pre-narrowing protocol. In the main negotiation phase of ourthe protocol, existing agent strategies for multi-issue negotiations can be applied to the pre-domain narrowing phase. Moreover, the predomain-narrowing phase is a part that weresearchers newly introduced, so the utility functions cannot be used directly as they are. In addition, an agent strategy that is compatible with the predomain-narrowing narrowing phase is required. This naive agent should be based on time-dependent concessions and narrowing within the range of the value the agent can make a maximum concession. It should not consider the opponent’s modeling and future predictions. Therefore, weresearchers design a simple and effective strategy for each of the following: “narrowing issues using the simultaneous submission method”, “narrowing issues using the pre-negotiation method”, and “narrowing options”.

5.1. Strategy for Narrowing Issues Using the Simultaneous Submission Method

When using the simultaneous submission method for narrowing issues, agents submit a list of issues that do not need to be negotiated from their perspective to the mediator. The offer related to a submitted issue is selected by the other agent or mediator. Therefore, the agreement on the submitted issues is probably disadvantageous to the submitter. As a naive strategy for the simultaneous submission method, wresearchers consider a method of submitting a list of issues that are unlikely to disadvantage the submitter. Here, the minimum utility $U_{min}$ that the agent can concede will be used as a parameter, and narrowing down is performed within the range where the acquired utility is expected to be $U_{min}$  or greater. For a given issue $I_i$ , wresearchers assume that the probability of each option being selected follows a uniform distribution when deciding an alternative of agreement during the main negotiation; the expected utility is ${\displaystyle w_i\times \frac{1}{k_i}\sum _{j=1\underset{}{\overset{}{k_i}}eval(v_j^i)}^{}}$ . Moreover, if an agent submits an issue and the option that is most unfavorable to the agent is selected, the utility is ${\displaystyle w_i\times \underset{j}{min}eval(v_j^i)}$ . It can be considered that the smaller the difference between these values, the less likely it is that the agent will be disadvantaged. Therefore, wresearchers rearrange the issues as $I_o,I_o,\dots ,I_o$ in ascending order of the differences. Next, from these issues, the number of issues m to be submitted is decided. If m issues are decided upon and submitted according to the order above, the utilities expected to be obtained are as follows: The maximum m within the range where the expected utilities do not fall below $U_{min}$ is determined, and the list of issues $I_o,I_o,\dots ,I_o$  is submitted to the mediator.

5.2. Strategy for Narrowing Issues Using the Pre-Negotiation Method

When narrowing issues using the pre-negotiation method, each issue is negotiated in a domain where the options are “subject to the main negotiation”, “Agent A chooses”, and “Agent B chooses”. An agent needs to define its utility function for this pre-negotiation domain. In a naive strategy, the utility function for pre-negotiation is defined by the utility expected to be finally obtained. Whenever an agent has the right to choose an issue, it can always choose the option that maximizes its utility. In this case, the expected utility is the maximum. Meanwhile, when the other agent has the right to choose, the expected utility is set as the minimum value, under the assumption that the most unfavorable choice will be made. If an issue is to be a subject in the main negotiation, then assuming that the probability that each option is selected follows a uniform distribution, the average is taken to be the expected utility. Based on the above, Equation (4) is the utility function for pre-negotiation. In pre-negotiation, the concession strategy is achieved using a concession function wherein the target utility decreases with time. Equation (5) shows the relationship between time t during the pre-negotiation and the target utility. where $U_{min}$ is a parameter representing the lowest utility to which an agent is willing to make a concession. At the start of pre-negotiations, the target utility is the maximum value of 1. The target value then decreases linearly so that it reaches $U_{min}$  at the end of the negotiation. At a given time t, an agent accepts an opponent’s proposal if the utility is $U_{target{}_{}(t)}$ or greater; otherwise, it replies with a counterproposal that has a utility of $U_{target{}_{}(t)}$  or greater.

5.3. Strategy for Narrowing Options

When narrowing options, a list of all options in the issues that was not eliminated when narrowing the issues is submitted to the mediator. In the strategy for deciding a list in this restudy, weearch, researchers use the same parameter $U_{min}$ for narrowing issues. To ultimately obtain a utility of $U_{min}$ or greater in the main negotiation, it is advisable to eliminate all options whose evaluation values are $eval(v_j^i)<U_{min{}_{}}$

. However, for options where decisions have already been made in the issue-narrowing phase, the decisions cannot be changed. Therefore, the options to be submitted are the set of options $v_j^i$ whose evaluation values satisfy the following:

If all of these options were to be excluded from the scope of the main negotiation, the utility gained when an arbitrary agreement is reached will be $U_{min}$  or greater.