# A Multi-agent Based Negotiation for Supply Chain Network Using Game Theory

Fang Yu, Toshiya Kaihara, Nobutada Fujii

► To cite this version:

Fang Yu, Toshiya Kaihara, Nobutada Fujii. A Multi-agent Based Negotiation for Supply Chain Network Using Game Theory. International Conference on Advances in Production Management Systems (APMS), Sep 2011, Stavanger, Norway. pp.299-308, 10.1007/978-3-642-33980-6_34. hal-01524237

HAL Id: hal-01524237

https://inria.hal.science/hal-01524237

Submitted on 17 May 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A multi-agent based negotiation for supply chain network using game theory

Fang Yu, Toshiya Kaihara, and Nobutada Fujii

Graduate School of System Informatics, Kobe University
1-1 Rokkodai, Nada, Kobe, Hyogo, 657-8501, Japan
yufang@kaede.cs.kobe-u.ac.jp, kaihara@kobe-u.ac.jp, nfujii@phoenix.kobe-u.ac.jp

**Abstract.** This paper focuses on the single-issue negotiation between Manufacture Agent (MA) and Material Supplier Agent (MSA) of the supply chain. MSA resorts to find partners to cooperate when it cannot finish the order independently. A two stage negotiation protocol is proposed. The cooperative game is combined with MA-Stackelberg game to resolve the negotiation problem. It is used to establish the coalitions. Then, the final determined coalition negotiates with MA to reach an agreement using the Stackelberg game. Protocols without concession and with concession are respectively discussed. Simulations and comparisons are provided to verify the effectiveness and superiority of the proposed protocol.

**Keywords:** Supply chain, negotiation, game theory, concession

## 1 Introduction

Negotiation is the process of arriving at a state that is mutually agreeable to a set of agents, that ranges from situations where resources must be allocated to agents to situations involving agent-to-agent bargaining. There are many negotiations among MAs, MSAs and CAs (Customer Agent) in Supply Chain Network (SCN) model. Game theory has become a primary methodology used in SCN-related problems. Primary methodological tools for dealing with these problems are Nash game and Stackelberg game, which focus on the simultaneous and sequential decision-making of multiple players, respectively[2]. The applications of game theory in Supply Chain Management (SCM) were surveyed by [1] and [2]. The reviews consist respectively of game theoretical techniques and SCM topics.

This paper focuses on the resource allocation of the negotiation using game theory. The negotiations between one MA and multiple MSAs are discussed. It is assumed that MSAs only accept the order which is in their abilities. They are compelled to reject the order against their will when the materials MA orders are too large to be provided by themselves. In general, MA decomposes the order into pieces and allocates them to multiple MSAs to resolve this problem. This research tries to find another way to resolve this problem which can maintain the integrity of the order. We focus on the side of MSAs and devote our efforts to let MSAs find partners to build coalitions when the order is out of their abilities. A two stage negotiation protocol is proposed. The coalition formation problem of the MSAs is modeled as a cooperative game in the first stage. Theories
of coalition formation were presented in [3-5]. In the second stage, the final delaoong terminated coalition negotiates with MA to reach an agreement using Stackelberg game ([6, 7]). MA announces his strategy to the MSAs at first, and then MSA chooses his best response to MA's decision. Thus, the problem can be modeled as finding the Stackelberg equilibrium ([8, 9]). A two-stage protocol is proposed, which resolves the problem when the supplier cannot complete the order independently. It maintains the integrity of the order, and reduces the cost and workload of MA.

This paper is organized as following. Section 2 describes the SCN model used in this paper and gives a two-stage negotiation protocol. Each stage of negotiations is discussed in detail in section 3 and in section 4. Simulations and analysis are discussed in section 5 to verify the effectiveness and feasibility of the proposed protocol. In conclusion, we have commented on contributions and the direction of future work research.

## 2 Two-stage negotiation protocol

All organizations of the SCN in this study are divided into three groups based on the multi-agent methodology: MSA, MA and CA. The model of the SCN is shown in Fig. 1(a). Discussion is provided only on the negotiations between one MA and multiple MSAs are discussed. The negotiations between one MA and

<figure><img src="image_2.png" /><figcaption>Fig. 1. The model setting and flowchart of the negotiation</figcaption></figure>

multiple MSAs, where the quantity of the order required by MA is too large for MSA to complete independently, are discussed in this study. MA broadcasts an order ($M_k, Q_k, PA_k(0), TD$) when inventory material is requested, where $M_k$ is the material MA wants to order, $Q_k$ is the quantity of $M_k, PA_k(0)$ is the initial price of $M_k$ of MA, $TD$ is the due time. It wants to find the optimal MSA with the lowest price. It is assumed in the proposed model that MSAs accept only orders which are able to fulfill. In the real market, the order frequently happens out of the abilities of MSAs. They will be compelled to reject the order against
their will in that case. In order to resolve this problem, researchers tend to decompose the order and then allocate it to multiple MSAs. This study tries to find another way to resolve this problem which can maintain the integrity of the order. Efforts are devoted to let MSAs combine with each other as a coalition and then negotiate with MA to acquire the order. A two-stage negotiation protocol is proposed as follows:

**Stage1:** Negotiation among MSAs (Sect. 4). MSAs evaluate the order and check whether it can be finished by themselves. If they can do it, they can go to the second stage of negotiation directly; if they cannot, then they can negotiate with the other MSAs to build a coalition. A cooperative game is used for the coalition formation. At the end, the final determined coalitions or MSA enter(s) into the second stage.

**Stage2:** Negotiation between MA and MSA or final coalition (Sect. 5). MA negotiates with the final coalition to find the Stackelberg equilibrium.

The flowchart is shown in Fig. 1(b). The first stage is used for preparation. There are MSAs which cannot complete the order by themselves. Thus, they should find partners to build a coalition. The final negotiation about the price is started at the second stage.

# 3 Negotiations among MSAs

MSA starts to negotiate with other MSAs in the SCN to establish a coalition if it cannot complete the order by itself. The way to establish coalitions, determination of the final coalition, and profit allocation are discussed in the following sections, respectively. The n-person cooperative game is introduced to build the coalitions.

## 3.1 Coalition formation

A cooperative n-person game ([4]) is a pair $(N,v)$ where $N = 1, ..., n$ denotes the set of players (MSAs), $v$ is the characteristic function and $v(S)$ defines the amounts of profit of players in set $S$ which they could win if a coalition is formed. $S=(S_1,...,S_N)$ denotes all partitions (coalition structure), $S_i=(s_{i1},...,s_{im})$ is the coalition structure of MSA $i$ ($m = 2^n - 1$), and $s_{ij}$ is one of the possible coalition of MSA $i$. Let $S_i^* = \{s_{ij} | v(s_{ij}) = \max_{s_{ij} \in S_i} v(s_{ij}), i \in N\}$ be the optimal coalition set of the game $(N,v)$. A feasible payoff profile is defined as a vector of $u_i$ such that $\sum_{i \in S_i} u_i = v(S_i)$.

Each player $i \in N$ seeks to maximize its utility function $u_i$ by belonging to a coalition. Therefore, the search for optimal coalition can be converted into the calculation of the core of the game. A cooperative game is applied into the SCN negotiation as in the following. Firstly, some useful definitions are given:

$$PR_{ik} = (1 + \alpha_i) * C_{ik} \qquad (1)$$

$$IV_{ik}(TD) = IV_{ik}(TC) + \gamma_{ik} * (TD - TC) \qquad (2)$$

$$PC_{ijk} = (1/|s_{ij}|) \sum_{i \in s_{ij}} PR_{ik} * (1 - \sigma_j) \qquad (3)$$

$$u(s_{ij}) = \sum_{i \in s_{ij}} (PC_{ijk} - C_{ik}) * Q_{ik} \qquad (4)$$
where $PR_{ik}$ is the price of $M_k$ of MSA $i$, $\alpha_i$ is the percentage of profit of MSA $i$ want to gain, $C_{ik}$ is the production cost of MSA $i$ for $M_k$, $IV_{ik}(TD)$ is the inventory level of $M_k$ of $i$, $\gamma_{ik}$ is the productivity of $M_k$ of $i$, $TC$ is the current time, $|s_{ij}|$ is the number of members in $s_{ij}$, $PC_{ijk}$ is the price of $M_k$ of coalition $s_{ij}$, $\sigma_j$ is the discount of coalition $s_{ij}$, $Q_k$ is the quantity of $M_k$ that MA ordered, $Q_{ik}$ is the quantity of $M_k$ of $i$ acquired in coalition $s_{ij}$.

## 3.2 Coalition determination

Each MSA $i$ expects to maximize its profit. Thus, the determination of the final coalition of each MSA $i$ is transformed into finding the optimal coalition set $S^*$. We have discussed before that the search for optimal coalition can be converted into the calculation of the core of the game. Therefore, the determination of the final coalition is equivalent to calculating the core of the game. It can be resolved by finding a solution to the following problem:

$$ \arg \max_{s_{ij} \in S_i} u(s_{ij}) = \arg \max_{s_{ij} \in S_i} \sum_{i' \in s_{ij}} (PC_{ijk} - C_{i'k}) * Q_{i'k} \quad (5) $$

$$ \text{s.t.} \quad \sum_{i' \in s_{ij}} IV_{i'k}(TD) \geq Q_k \quad (6) $$

$$ \sum_{i' \in s_{ij}} Q_{i'k} = Q_k. \quad (7) $$

The optimal coalition $S_i^*$ of each MSA $i$ can be reached, but the coalition is determined only if all MSAs in $s_{ij}$ reach an agreement. An agreement is reached between MSA $i$ and $j$ only if MSA $i$ asks $j$ to be a partner and vice-versa at the same time. All MSAs in coalition $S_i^*$ must have maximal profits because they are all selfish. The coalition $S_i^*$ with the maximal value of $u$ is determined as the final coalition $SF_i$ of MSA $i$ after the agreement is reached.

## 3.3 Profit allocation

The profit allocation among the members after the coalition gets the order is discussed in this section. It is easy to do it when the order just meets the demands of all members. However, what should be done when the order is not enough to fulfill the total supply of the coalition? In other words, if $\sum_{i \in SF_i} IV_{ik}(TD)$ is greater than $Q_k$, what can be done? As we know, each player in the coalition has main interests in its individual benefit and tries to maximize its own profit. Thus, we should assign the profit impartially. For this purpose, we present the following allocation rule:

**Rule:** The MSA who contributes more to the coalition, gains more.

Therefore, we allocate the profit among the members according to their contributions to the coalition. Let $\pi_i$ be the profit of player $i$, and $\pi_{s_{ij}}=(\pi_1, \dots, \pi_m)$ denotes a profit allocation of the coalition $s_{ij}$. To be efficient, one must have $\sum_{i \in s_{ij}} \pi_i = u(s_{ij})$. We can get that $\pi_i = u(s_{ij})Q_{ik}/Q_k$ according to the rule. It means that the profit allocation depends on the allocation of the order quantity among the players in the coalition. The order is allocated according to the ability (productivity) to be fair:
$$Q_{ik} = IV_{ik}(TD)Q_k / \sum_{i \in s_{ij}} IV_{ik}(TD). \qquad (8)$$

# 4 Negotiation between MA and the final coalition

## 4.1 Protocol without concession

The negotiation between MA and SF$_i$ starts to reach an agreement on the price of M$_k$ after SF$_i$ is determined. However, the target of SF$_i$ is contrary to MA's. Each individual wishes to maximize the utility of himself. On one hand, SF$_i$ aims to maximize its payoff by increasing the price; on the other hand, MA tries to maximize its profit by reducing the price in order to lower the production cost and therefore to minimize the total payment. We have:

$$PF_{ik}[t] = PF_{ik}[t-1] - (PF_{ik}[t-1] - PFI_{ik})TS/(TN-t) \qquad (9)$$

$$PM_k[t] = PM_k[t-1] + (PMA_k - PM_k[t-1])TS/(TN-t) \qquad (10)$$

where PF$_{ik}$[t] is the price of M$_k$ of SF$_i$ at t and PF$_{ik}$[0]=PC$_{ijk}$ where j = arg max$_{s_{ij} \in S_i}$ u(s$_{ij}$); PFI$_k$ is the minimal price of M$_k$ of SF$_i$ and PFI$_k$ = {PC$_{ijk}$|a$_i$ = a$_{min}$}; PM$_k$[t] is the price of M$_k$ of MA at t; the maximal price PMA$_k$ and initial price PM$_k$[0] of M$_k$ from MA are given by the order; TN is the deadline of negotiation, TS is the negotiation step.

Stackelberg equilibrium applies when one of the players move before the other player and the player who moves firstly is assumed as the leader [2]. In the proposed model, MA first announces its strategy to the MSAs. Thus, the negotiation between MA and SF$_i$ can be seen as MA-Stackelberg game and the determination of the final strategy is transformed into finding the Stackelberg equilibrium of the game. The determination of the Stackelberg equilibrium can be transformed into finding the optimal proposal and so to maximize the profits of MA (u$_{MA}$) and SF* (u$_{SF}$$_i$). In other word, the purpose is to maximize the total profit of the whole SCN (u$_{SCN}$). Thus, the problem of finding the Stackelberg equilibrium can be transformed into solving the following problem:

$$\begin{aligned} \arg \max_{i} u_{SCN} &= u_{MA} + u_{SF_i} \\ &= (PS_k - FS_{ik}) * Q_k + \sum_{i' \in s_{ij}} (FS_{ik} - C_{i'k}) * Q_{i'k} \end{aligned} \qquad (11)$$

$$\text{s.t.} \quad FS_{ik} = \arg \max_{PM_k[t]} u_{MA} + u_{SF_i} \qquad (12)$$

$$FS_{ik} \geq PF_{ik}[t+1] \qquad (13)$$

where PS$_k$ is the selling price of M$_k$ of MA. The equilibriums can be reached by resolving (12), which means that the agreement between MA and SF$_i$ on the price of M$_k$ is FS$_{ik}$. The final supplier is determined by solving (11)-(13) and the negotiation terminates.

## 4.2 Protocol with concession

Sim et al. ([10, 11]) proposed a MDA model for designing negotiation agents that make adjustable rates of concession for a given market situation by considering
factors such as trading opportunity, competition, remaining trading time and eagerness. The effect of the remaining trading time is considered in this research. The concession strategies are given as followings based on Sim's:

1. For MA:

$$ \delta_k^M[r] = T_k^M(t_r, \tau, \varepsilon)(k_{max}^M - k^M[r-1]) \quad (14) $$

$$ T_k^M(t_r, \tau, \varepsilon) = (t_r/\tau)^{\frac{1}{\varepsilon}} \quad (15) $$

where $k^M$ is the value of attribute $k$ of MA, $k_{max}^M$ is the maximum value of attribute $k$ of MA, $\delta_k^M[r]$ is the spread of MA of attribute $k$ at round $r$, $\tau$ is the negotiation deadline. Different strategies in making concession related to the remaining trading time are classified as follows ([12]):

* $\varepsilon=0$: means agent is totally not interested in negotiating.

* $\varepsilon=1$: makes a constant rate of concession;

* $0 < \varepsilon < 1$: makes a smaller concession in early rounds and larger concession in later rounds;

2. For MSA i:

$$ \delta_{ik}^{S}[r] = T_{ik}^{S}(t_r, \tau, \varepsilon)(k_{i}^{S}[r-1] - k_{i,min}^{S}) \quad (16) $$

$$ T_{ik}^{S}(t_r, \tau, \varepsilon) = (t_r/\tau)^{\frac{1}{\varepsilon}} \quad (17) $$

where $k_i^S$ is the value of attribute $k$ of MSA $i$, $k_{i,min}^S$ is the minimum value of attribute $k$ of MSA $i$, $\delta_{ik}^S[r]$ is the spread of MSA $i$ of attribute $k$ at round $r$.

Equations (9) and (10) are reduced to:

$$ PM'[r] = PM'[r-1] + (r * TSTEP/TN)^{\frac{1}{\varepsilon}} (PMA'_{k} - PM'[r-1]) \quad (18) $$

$$ PF'_{ik}[r] = PF'_{ik}[r-1] - (r * TSTEP/TN)^{\frac{1}{\varepsilon}} (PF'_{ik}[r-1] - PFI'_{ik}). \quad (19) $$

Then, the equilibriums and final supplier(s) are determined by solving (11) - (13) where $PM_k[t]$ and $PF_{ik}[t]$ are respectively equal to $PM'_k[t]$ and $PF'_{ik}[t]$.

## 5 Simulations and analysis

It is supposed that there are 5 MSAs and one MA distribute in the SCN (the initial values of MSAs are shown in Table 1) and the MA is price prior. The parameters settings are: $\alpha_i=0.3$, $\alpha_{min}=0.2$, $\sigma_j=0.2$, $TN=60s$, $TS=2s$, $PMA_k=11$, $PMI_k=8.5$, $PS_k=15$, $TD=10$.

<table><caption>**Table 1.** Initial Information of MSAs</caption><thead><tr><th>Supplier</th><th>γ<sub>ik</sub></th><th>C<sub>ik</sub></th><th>PR<sub>ik</sub></th><th>Supplier</th><th>γ<sub>ik</sub></th><th>C<sub>ik</sub></th><th>PR<sub>ik</sub></th></tr></thead><tbody><tr><td>MSA<sub>1</sub></td><td>150</td><td>7.91</td><td>10.283</td><td>MSA<sub>4</sub></td><td>150</td><td>7.67</td><td>9.971</td></tr><tr><td>MSA<sub>2</sub></td><td>150</td><td>8.20</td><td>10.660</td><td>MSA<sub>5</sub></td><td>100</td><td>7.82</td><td>10.166</td></tr><tr><td>MSA<sub>3</sub></td><td>200</td><td>7.80</td><td>10.140</td><td></td><td></td><td></td><td></td></tr></tbody></table>

Firstly, the proposed protocol is compared with the greedy algorithm under three cases to verify the feasibility and superiority, where:

- Greedy algorithm: MA selects the MSA with the lowest price as the supplier. If the selected MSA cannot complete the order by itself, then MA splits the order and allocate the remaining quantity to other MSAs with the lowest price and so on;
- Case1: $Q=1000$, which means that in this case all the MSAs can complete the order by themselves;

- Case2: $Q=2000$, we can see from Table1 that some MSAs cannot complete the order by themselves, thus, they need to find partners;

- Case3: $Q=3000$, we can see from Table1 that no MSA can complete the order by itself.

The comparisons are shown in Table 2. All the MSAs in both protocols can complete the order by themselves in Case1, they choose the same supplier with the lowest price. Thus, the profits of both protocols are the same. The order is out of the abilities of some MSAs in Case2. The final suppliers of greedy algorithm and proposed protocol are {4,3} and {4,5}, respectively. The profit of the MA in the proposed protocol is higher than in the greedy algorithm. All MSAs in SCN cannot finish the order by themselves in Case3. The final suppliers of both protocols are the same, but the profit in the proposed protocol is still higher than in the greedy algorithm.

<table><caption>**Table 2.** Comparisons of greedy algorithm and proposed protocol under three cases</caption><thead><tr><th rowspan="2"></th><th colspan="2">Case1</th><th colspan="2">Case2</th><th colspan="2">Case3</th></tr><tr><th>Greedy</th><th>Proposed</th><th>Greedy</th><th>Proposed</th><th>Greedy</th><th>Proposed</th></tr></thead><tbody><tr><td>Suppliers</td><td>{4}</td><td>{4}</td><td>{4,3}</td><td>{4,5}</td><td>{4,3}</td><td>{4,3}</td></tr><tr><td>Profit of MA</td><td>4997.5</td><td>4997.5</td><td>9446.25</td><td>11044.25</td><td>14846.25</td><td>16586.63</td></tr></tbody></table>

**Analysis:** The greedy algorithm adopts the method of splitting the order and allocating it to multiple MSAs. It increases the workload of MA. The proposed protocol solves this problem from the side of the MSA. It tries to build coalitions and MA just announces the order and waits for the responses. The proposed protocol is much more superior to the greedy algorithm. It doesn't only maintain the integrity of the order, and reduces the workload of MA, but also increases the profit of MA. We can see from Table 2 that the proposed protocol improves the profit margins from 0 to 1598, and 1740.38 in three cases, respectively.

Secondly, the comparisons between the protocol without concession and with concession are provided where $\epsilon=0.3$. The results are shown in Fig. 2.

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Comparisons of the protocol without concession and with concession</figcaption></figure>

**Analysis:** It indicates that the protocol with concession reaches the same agreement with the protocol without concession, but it is faster than the protocol without concession. Furthermore, the concession rate is related to $\epsilon$.
# 6 Conclusion

In this paper, a multi-agent based negotiation protocol for supply chain network using game theory was discussed. A two stage negotiation protocol is proposed. Cooperative game was adopted in the first stage of negotiation for the coalition formation. The negotiation among the MSAs was transformed into the calculation of the core of the game. A MA-Stackelberg game was introduced for the negotiation between MA and the final coalition. Thus, the negotiation problem can be resolved by finding the Stackelberg equilibrium. Then, concession strategies were taken into account based on the proposed protocol. The main contributions of the proposed protocols are that the resolution of the problem when the supplier cannot fulfill the order independently and the maintenance of the integrity of the order. Comparisons verified that the proposed protocol had a better performance than the greedy algorithm and the protocol with concession is faster than the protocol without concession.

This paper only considered the single-attribute negotiation between one MA and multiple MSAs, we will study the multi-attribute negotiation between one MA and multiple MSAs in a future work. Furthermore, we will extend our negotiation protocol to the negotiations between multi-MA and multi-MSA which are much more complex. In this paper it was assumed that MA has price priority, but in real SCN, when the order is urgent, the time must be taken into account, thus, we will discuss the price and lead time dimensions, respectively.

# References

1. Cachon G.P., Netsssine S.: Game theory in supply chain analysis. In D. Simchi-levi, S.D. Wu, and Z. Shen, editors, Handbook of Quantitative supply chain analysis: modeling in the E-Business Eram. Kluwer, 13-66 (2004)

2. Leng M.M., Parlar M.: Game theoretic applications in supply chain management: a review. INFOR, 43(3), 187-220 (2005)

3. Willam A. G.: A theory of coalition formation. American Sociological Review, 26(3), 373-382 (1961)

4. Shenoy P.P, Lawrence: On coalition formation: a game-theoretical approach. International Journal of Game theory, 8(3), 133-164 (1979)

5. Nagarajan M., Sosic G.: Game-theoretic analysis of cooperation among supply chain agents: review and extensions. EUR J OPER RES, 187, 719-745 (2008)

6. Hennet J.C., Mahjoub S.: Toward the fair sharing of profit in a supply chain network formation. Internatioanl Journal Production Economics, 127, 112-120 (2010)

7. Fiestras-Janeiro M.G., Garcia-Jurado I., Meca A., and Mosquera M.A.: Cooperative game theory and inventory management. EUR J OPER RES, 210, 459-466 (2011)

8. Rezapour S. et al.: Strategic design of competing supply chain networks with foresight. ADV ENG SOFTW, 42, 130-141 (2011)

9. Lu J.C, Tsao Y.C, Charoensiriwath C.: Competition under manufacturer service and reatil price. Economic Modelling, 28, 1256-1264 (2011)

10. Sim K.M., Wong E.: Toward market-driven agents for electronic auction. IEEE T SYST MAN CY A, 31(6), 474-484 (2001)

11. Sim K.M.: Negotiation agents that make prudent compromises and are slightly flexible in reaching consensus. Computational Intelligence, 20(4), 643-662 (2004)

12. Ren F.H., Zhang M., Sim K.M.: Adaptive conceding strategies for automated trading agents in dynamic, open markets. DECIS SUPPORT SYST, 46, 704-716 (2009)