Negotiation Protocol with Pre-Domain Narrowing

Negotiation Protocol with Pre-Domain Narrowing: History

Please note this is an old version of this entry, which may differ significantly from the current revision.

Subjects: Computer Science, Artificial Intelligence

Contributor:

Yuta Hosokawa

Consensus building among agents is crucial in multi-agent system because each agent acts independently according to its utility function, and conflict among agents can occur. Therefore, automated negotiation is an essential technology for efficiently resolving conflicts and forming consensuses while also keeping agents' privacy. As the domain to be negotiated is large, the computational cost of reaching a consensus increases and the agreement rate decreases. 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 negotiations. 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 predecided negotiation rules.
In this study, we propose a negotiation protocol with a predomain-narrowing phase to enable efficient negotiations in large-scale domains and can keep private information that agents should not disclose to their opponents and mediator. The proposed protocol divides the negotiation process into a predomain-narrowing phase and the main negotiation phase. In the proposed protocol, the parts subject to negotiation are first narrowed in upon, and then the main negotiation is performed. We also propose two narrowing methods: issue- and option-narrowing. Further, we propose naive agent strategies considering the predomain-narrowing phase. We perform comparative simulation experiments between the baseline negotiation protocol without a domain-narrowing phase and the proposed negotiation protocol with the predomain-narrowing phase. The experimental results show that the proposed protocol achieves higher agreement rates in less negotiation time than the baseline.

Automated Negotiation
Pre-negotiation
Domain Narrowing
Multi-agent System

1. Introduction

We propose a negotiation pre-narrowing protocol to enable efficient negotiation in a large negotiation domain space. In this protocol, we introduce a negotiation domain space-narrowing phase, where issues and options are narrowed before the main negotiation. By narrowing the negotiation domain space before the main negotiation, the computational cost of searching for offers in a large negotiation domain space is reduced. In addition, it is possible to prevent inconvenient agreements during the main negotiation by eliminating options from which each agent would obtain little utility in advance. We assume that the issues are independent to work effectively in multi-issue negotiation because each agent needs to calculate the narrowing issues and options with high computational costs considering the dependencies among issues.

Figure 1 shows the outline of the proposed protocol. A negotiation domain space-narrowing phase is newly set up before the main negotiation phase, where regular negotiations are performed. In the negotiation domain space-narrowing phase, issues are narrowed down in the first step, and then options within each issue are narrowed. In the first step, it is decided which issues will not be a subject in the main negotiation, and agreements on these issues are concluded in advance. In the next step, for each issue, options to be excluded as major negotiation subjects are decided. We propose two methods for narrowing issues: the “simultaneous submission method” and “pre-negotiation method”.

Figure 1. Outline of negotiation domain space pre-narrowing protocol.

2. Narrowing Issues Using the Simultaneous Submission Method

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.

Table 1. An example of issue-narrowing using the simultaneous submission method (“×” represents an unnecessary issue).

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

We 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.

Table 2. An example of Pre-negotiation.

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.

Table 3. An example of narrowing options (× represents elimination).

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

\sum_{i = 1}^{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

We design naive agent strategies considering the negotiation domain space for the proposed pre-narrowing protocol. In the main negotiation phase of our 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 we 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, we 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, we consider a method of submitting a list of issues that are unlikely to disadvantage the submitter. Here, the minimum utility

U_{m i n}

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_{m i n}

or greater.

For a given issue

I_{i}

, we 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

w_{i} \times \frac{1}{k_{i}} \sum_{j = 1}^{k_{i}} e v a l (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

w_{i} \times min_{j} e v a l (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, we rearrange the issues as

I_{o_{1}}, I_{o_{2}}, \dots, I_{o_{n}}

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:

U_{e x p e c t e d} = \sum_{i = 1}^{m} (w_{o_{i}} \times min_{j} e v a l (v_{j}^{o_{i}})) + \sum_{i = m + 1}^{n} (w_{o_{i}} \times \frac{1}{k_{o_{i}}} \sum_{j = 1}^{k_{o_{i}}} e v a l (v_{j}^{o_{i}}))

The maximum m within the range where the expected utilities do not fall below

U_{m i n}

is determined, and the list of issues

I_{o_{1}}, I_{o_{2}}, \dots, I_{o_{m}}

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.

\begin{matrix} U_{p r e} (\vec{b}) = & \sum_{i \in (I s s u e c h o s e n b y o n e s e l f)} (w_{i} \times max_{j} e v a l (v_{j}^{i})) \\ + \sum_{i \in (I s s u e c h o s e n b y o p p o n e n t)} (w_{i} \times min_{j} e v a l (v_{j}^{i})) \\ + \sum_{i \in (I s s u e t o b e d e t e r m i n e d i n t h e m a i n n e g o t i a t i o n)} (w_{i} \times \frac{1}{k_{i}} \sum_{j = 1}^{k_{i}} e v a l (v_{j}^{i})) \end{matrix}

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.

U_{t a r g e t} (t) = 1 - (1 - U_{m i n}) \times t

where

U_{m i n}

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_{m i n}

at the end of the negotiation. At a given time t, an agent accepts an opponent’s proposal if the utility is

U_{t a r g e t} (t)

or greater; otherwise, it replies with a counterproposal that has a utility of

U_{t a r g e t} (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 study, we use the same parameter

U_{m i n}

for narrowing issues. To ultimately obtain a utility of

U_{m i n}

or greater in the main negotiation, it is advisable to eliminate all options whose evaluation values are

e v a l (v_{j}^{i}) < U_{m i n}

. 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:

e v a l (v_{j}^{i}) < \frac{U_{m i n} - \sum_{k \in (I s s u e s s u b j e c t e d t o n a r r o w i n g)} (w_{k} \times e v a l (v_{s e l e c t e d}^{k}))}{\sum_{k \in (I s s u e s n o t s u b j e c t e d t o n a r r o w i n g)} w_{k}}

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_{m i n}

or greater.

This entry is adapted from the peer-reviewed paper 10.3390/app13106186

© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.